View source for Phylogenetic reconciliation

{{Short description|Technique in evolutionary study}}
[[File:Phylogenetic Reconciliation.svg|441x441px|thumb|A phylogenetic reconciliation between an upper [[phylogenetic tree]] (blue) and a lower one (red), annotated with the most often used evolutionary events (S, D, T, L) and their respective names in the contexts of [[phylogeography]], [[host (biology)|host]]/[[symbiosis|symbiont]] and [[gene]]/[[species]]. For instance, the S event is called [[allopatric speciation]] when reconciling geographical areas and species, [[cospeciation]] between host and symbiont, and [[speciation]] for gene and species, but always corresponds to the same co-diversification pattern.]]

In [[phylogenetics]], '''reconciliation''' is an approach to connect the history of two or more [[coevolution|coevolving]] biological entities. The general idea of reconciliation is that a [[phylogenetic tree]] representing the evolution of an entity (e.g. [[sequence homology|homologous]] [[gene]]s or [[Symbiosis|symbionts]]) can be drawn within another phylogenetic tree representing an encompassing entity (respectively, species, hosts) to reveal their interdependence and the evolutionary events that have marked their shared history. The development of reconciliation approaches started in the 1980s, mainly to depict the coevolution of a gene and a genome, and of a host and a symbiont, which can be mutualist, commensalist or parasitic. It has also been used for example to [[Inferring horizontal gene transfer|detect horizontal gene transfer]], or understand the dynamics of [[genome evolution]].

Phylogenetic reconciliation can account for a diversity of evolutionary trajectories of what makes life's history, intertwined with each other at all scales that can be considered, from molecules to populations or cultures. A recent avatar of the importance of interactions between levels of organization is the [[holobiont]] concept, where a macro-organism is seen as a complex partnership of diverse species. Modeling the evolution of such complex entities is one of the challenging and exciting direction of current research on reconciliation.

==Phylogenetic trees as nested structures==
[[File:Intertwined phylogenies at multiple levels.svg|thumb|Some of the levels of biological organization commonly conceptualized as [[phylogenetic tree]]s and to which phylogenetic reconciliation has been applied.]]

Phylogenetic trees are intertwined at all levels of organization, integrating conflicts and dependencies within and between levels. Macro-organism populations migrate between continents, their [[microbe]] [[symbiont]]s switch between populations, the genes of their symbionts transfer between microbe species, and domains are exchanged between genes.
This list of organization levels is not representative or exhaustive, but gives a view of levels where reconciliation methods have been used. 
As a generic method, reconciliation could take into account numerous other levels. For instance, it could consider the [[syntenic]] organization of genes,<ref name=duchemin_decostar:_2017>{{Cite journal|pmid = 28402423| year=2017 | last1=Duchemin | first1=W. | last2=Anselmetti | first2=Y. | last3=Patterson | first3=M. | last4=Ponty | first4=Y. | last5=Bérard | first5=S. | last6=Chauve | first6=C. | last7=Scornavacca | first7=C. | last8=Daubin | first8=V. | last9=Tannier | first9=E. | title=DeCoSTAR: Reconstructing the Ancestral Organization of Genes or Genomes Using Reconciled Phylogenies | journal=Genome Biology and Evolution | volume=9 | issue=5 | pages=1312–1319 | doi=10.1093/gbe/evx069 | pmc=5441342 }}</ref> the interacting history of transposable elements and species,<ref name=Loreto2008>{{Cite journal|pmid = 18431403| year=2008 | last1=Loreto | first1=E. L. | last2=Carareto | first2=C. M. | last3=Capy | first3=P. | title=Revisiting horizontal transfer of transposable elements in Drosophila | journal=Heredity | volume=100 | issue=6 | pages=545–554 | doi=10.1038/sj.hdy.6801094 | s2cid=32424144 | doi-access=free }}</ref> the evolution of a protein complex across species.<ref name=denise_diversification_2019>{{Cite journal|pmid = 31323028| year=2019 | last1=Denise | first1=R. | last2=Abby | first2=S. S. | author3=Rocha EPC | title=Diversification of the type IV filament superfamily into machines for adhesion, protein secretion, DNA uptake, and motility | journal=PLOS Biology | volume=17 | issue=7 | pages=e3000390 | doi=10.1371/journal.pbio.3000390 | pmc=6668835 | doi-access=free }}</ref> The scale of evolutionary events considered can go from population events such as geographical diversification to nucleotids levels one inside genes,<ref name=Felsenstein2004>Felsenstein J (2004) Inferring Phylogenies. Oxford University Press</ref> including for instance chromosome levels events inside genomes such as whole genome duplication.<ref name=zwaenepoel_ancient_2019>{{Cite journal|pmid = 31004147| year=2019 | last1=Zwaenepoel | first1=A. | last2=Van De Peer | first2=Y. | title=Inference of Ancient Whole-Genome Duplications and the Evolution of Gene Duplication and Loss Rates | journal=Molecular Biology and Evolution | volume=36 | issue=7 | pages=1384–1404 | doi=10.1093/molbev/msz088 | hdl=1854/LU-8612728 | hdl-access=free }}</ref>

Phylogenies have been used for representing the diversification of life at many [[Biological organisation|levels of organization]]: macro-organisms,<ref name="PBagowski2010">{{Cite journal|pmid = 21286315| year=2010 | last1=Bagowski | first1=C. P. | last2=Bruins | first2=W. | last3=Te Velthuis | first3=A. J. | title=The nature of protein domain evolution: Shaping the interaction network | journal=Current Genomics | volume=11 | issue=5 | pages=368–376 | doi=10.2174/138920210791616725 | pmc=2945003 }}</ref> their [[Cell (biology)|cells]] throughout [[Embryonic development|development]],<ref name=Nair2014>{{Cite journal|pmid = 25104072| year=2014 | last1=Nair | first1=N. U. | last2=Lin | first2=Y. | last3=Manasovska | first3=A. | last4=Antic | first4=J. | last5=Grnarova | first5=P. | last6=Sahu | first6=A. D. | last7=Bucher | first7=P. | last8=Moret | first8=B. M. | title=Study of cell differentiation by phylogenetic analysis using histone modification data | journal=BMC Bioinformatics | volume=15 | issue=1 | page=269 | doi=10.1186/1471-2105-15-269 | pmc=4138389 | doi-access=free }}</ref> [[Microorganism|micro-organisms]] through [[marker gene]]s,<ref name=Woese1990>{{Cite journal|pmid = 2112744| year=1990 | last1=Woese | first1=C. R. | last2=Kandler | first2=O. | last3=Wheelis | first3=M. L. | title=Towards a natural system of organisms: Proposal for the domains Archaea, Bacteria, and Eucarya | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=87 | issue=12 | pages=4576–4579 | doi=10.1073/pnas.87.12.4576 | pmc=54159 | bibcode=1990PNAS...87.4576W | doi-access=free }}</ref> [[chromosome]]s,<ref name=Dobzhansky1938>{{Cite journal|pmid = 17246876| year=1938 | last1=Dobzhansky | first1=T. | last2=Sturtevant | first2=A. H. | title=Inversions in the Chromosomes of Drosophila Pseudoobscura | journal=Genetics | volume=23 | issue=1 | pages=28–64 | doi=10.1093/genetics/23.1.28 | pmc=1209001 }}</ref> [[protein]]s,<ref name=Zuckerkandl1965>{{Cite journal|pmid = 5876245| year=1965 | last1=Zuckerkandl | first1=E. | last2=Pauling | first2=L. | title=Molecules as documents of evolutionary history | journal=Journal of Theoretical Biology | volume=8 | issue=2 | pages=357–366 | doi=10.1016/0022-5193(65)90083-4 | bibcode=1965JThBi...8..357Z }}</ref> [[protein domain]]s,<ref name=PBagowski2010/> and can also be helpful to understand the evolution of human culture elements such as [[language]]s<ref name=Gray2010>{{Cite journal|pmid = 21041216| year=2010 | last1=Gray | first1=R. D. | last2=Bryant | first2=D. | last3=Greenhill | first3=S. J. | title=On the shape and fabric of human history | journal=Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences | volume=365 | issue=1559 | pages=3923–3933 | doi=10.1098/rstb.2010.0162 | pmc=2981918 }}</ref> or [[fairy tale]]s.<ref name=Tehrani2013>{{Cite journal|pmid = 24236061| year=2013 | last1=Tehrani | first1=J. J. | title=The phylogeny of Little Red Riding Hood | journal=PLOS ONE | volume=8 | issue=11 | pages=e78871 | doi=10.1371/journal.pone.0078871 | pmc=3827309 | bibcode=2013PLoSO...878871T | doi-access=free }}</ref>
At each of these levels, phylogenetic trees describe different stories made of specific diversification events, which may or may not be shared among levels. Yet because they are structurally nested (similar to [[matryoshka doll]]s) or functionally dependent, the evolution at a particular level is bound to those at other levels.

Phylogenetic reconciliation is the identification of the links between levels through the comparison of at least two associated trees. Originally developed for two trees, reconciliations for more than two levels have been recently constructed (see section [[#Explicit modeling of three or more levels|Explicit modeling of three or more levels]]). As such, reconciliation provides evolutionary scenarios that reveal conflict and cooperation among evolving entities. These links may be unintuitive, for instance, genes present in the same genome may show uncorrelated evolutionary histories while some genes present in the genome of a symbiont may show a strong coevolution signal with the host phylogeny. Hence, reconciliation can be a useful tool to understand the constraints and evolutionary strategies underlying the assemblage that forms a [[holobiont]].

Because all levels essentially deal with the same object, a [[phylogenetic tree]], the same models of reconciliation&mdash;in particular those based on [[gene duplication|duplication]]-[[gene transfer|transfer]]-[[gene loss|loss]] events, which are central to this article&mdash;can be transposed, with slight modifications, to any pair of connected levels:<ref name=wieseke_unifying_2013>{{cite arXiv |last1=Wieseke |first1=Nicolas |last2=Bernt |first2=Matthias |last3=Middendorf |first3=Martin |title=Unifying Parsimonious Tree Reconciliation |date=30 July 2013 |class=q-bio.QM |eprint=1307.7831}}</ref> an "inner", "lower", or "associate" entity (e.g. gene, symbiont species, population) evolves inside an "upper", or "host" one (respectively species, host, or geographical area).
The upper and lower entities are partially bound to the same history, leading to similarities in their phylogenetic trees, but the associations can change over time, become more or less strict or switch to other partners.

==History==

The principle of phylogenetic reconciliation was introduced in 1979<ref name=goodman_fitting_1979>{{cite journal | doi=10.2307/2412519 | jstor=2412519 | title=Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences | last1=Goodman | first1=Morris | last2=Czelusniak | first2=John | last3=Moore | first3=G. William | last4=Romero-Herrera | first4=A. E. | last5=Matsuda | first5=Genji | journal=Systematic Zoology | year=1979 | volume=28 | issue=2 | pages=132–163 }}</ref> to account for differences between genes and species-level phylogenies. In a parsimonious setting, two evolutionary events, gene duplication and gene loss were invoked to explain the discrepancies between a gene tree and a species tree. It also described a score on gene trees knowing the species tree and an aligned sequence by using the number of gene duplication, loss, and nucleotide replacement for the evolution of the aligned sequence, an approach still central today with new models of reconciliation and phylogeny inference.<ref name=morel_generax_2019>{{Cite journal|pmid = 32502238| year=2020 | last1=Morel | first1=B. | last2=Kozlov | first2=A. M. | last3=Stamatakis | first3=A. | last4=Szöllősi | first4=G. J. | title=GeneRax: A Tool for Species-Tree-Aware Maximum Likelihood-Based Gene Family Tree Inference under Gene Duplication, Transfer, and Loss | journal=Molecular Biology and Evolution | volume=37 | issue=9 | pages=2763–2774 | doi=10.1093/molbev/msaa141 | pmc=8312565 }}</ref>

The term ''reconciliation'' has been used by [[Wayne Maddison]] in 1997,<ref name=maddison_1997>Wayne P. Maddison (1997) Gene Trees in Species Trees, Systematic Biology, 46(3) 523-536.</ref> as a reverse concept of "phylogenetic discord" resulting from gene level evolutionary events.

Reconciliation was then developed jointly for the [[coevolution]] of host and symbiont and the [[Allopatric speciation|geographic diversification of species]]. In both settings, it was important to model a horizontal event that implied parallel branches of the host tree: [[host switch]] for host and symbiont and species dispersion from one area to another in [[biogeography]]. Unlike for genes and genomes, the coevolution of host and symbiont and the explanation of species diversification by geography are not always the [[null hypothesis]]. A visual depiction of the two phylogenies in a [[tanglegram]] can help assess such coevolution, although it has no statistical obvious interpretation.<ref name=vienne_tanglegrams_2019>{{Cite journal|pmid = 30351416| year=2019 | last1=De Vienne | first1=D. M. | title=Tanglegrams Are Misleading for Visual Evaluation of Tree Congruence | journal=Molecular Biology and Evolution | volume=36 | issue=1 | pages=174–176 | doi=10.1093/molbev/msy196 }}</ref>

Character methods, such as [[Brooks Parsimony Analysis]],<ref name=brooks_81>{{cite journal | doi=10.2307/2413247 | jstor=2413247 | title=Hennig's Parasitological Method: A Proposed Solution | last1=Brooks | first1=Daniel R. | journal=Systematic Zoology | year=1981 | volume=30 | issue=3 | pages=229–249 }}</ref> were proposed to test coevolution and reconstruct scenarios of coevolution. In these methods, one of the trees is forgotten except for its leaves, which are then used as a character evolving on the second tree.
First models for reconciliation, taking explicitly into account the two topologies and using a mechanistic event-based approach, were proposed for host and symbiont and biogeography.<ref name=nelson_platnick_1981>{{cite journal | doi=10.2307/2413040 | jstor=2413040 | last1=Sneath | first1=P. H. A. | title=Reviewed work: Systematics and Biogeography: Cladistics and Vicariance. II., Gareth Nelson, Norman Platnick | journal=Systematic Zoology | year=1982 | volume=31 | issue=2 | pages=208–217 }}</ref><ref name=ronquist_process_1990>{{cite journal | doi=10.2307/2992354 | jstor=2992354 | title=Process and Pattern in the Evolution of Species Associations | last1=Ronquist | first1=Fredrik | last2=Nylin | first2=Soren | journal=Systematic Zoology | year=1990 | volume=39 | issue=4 | pages=323–344 }}</ref> Debates followed, as the methods were not yet completely sound but integrated useful information in a new framework.<ref name=page_component_1990>{{Cite journal|pmid = 34933509| year=1990 | author1=Page RDM | title=Component Analysis: A Valiant Failure? | journal=Cladistics | volume=6 | issue=2 | pages=119–136 | doi=10.1111/j.1096-0031.1990.tb00532.x | s2cid=86307275 }}</ref>

Costs for each event and a dynamic programming technique considering all pairs of host and symbiont nodes were then introduced into a host and symbiont approach, both of which still underlie most of the current reconciliation methods for host and symbiont as well as for species and genes.<ref name=charleston_jungles_1998>{{Cite journal|pmid = 9621683| year=1998 | last1=Charleston | first1=M. A. | title=Jungles: A new solution to the host/Parasite phylogeny reconciliation problem | journal=Mathematical Biosciences | volume=149 | issue=2 | pages=191–223 | doi=10.1016/s0025-5564(97)10012-8 }}</ref>

Reconciliation returned to the framework it was introduced in, gene and species. After character models were considered for horizontal gene transfer,<ref name=hein_heuristic_1993>{{cite journal | doi=10.1007/BF00182187 | title=A heuristic method to reconstruct the history of sequences subject to recombination | year=1993 | last1=Hein | first1=Jotun | journal=Journal of Molecular Evolution | volume=36 | issue=4 | page=396 | bibcode=1993JMolE..36..396H | s2cid=16346458 }}</ref> a new reconciliation model, following and improving the dynamic programming approach presented for host and symbiont, effectively introduced horizontal gene transfer to gene and species reconciliation on top of the duplication and loss model.<ref name=hallet_efficient_2001>{{cite book | doi=10.1145/369133.369188 | chapter=Efficient algorithms for lateral gene transfer problems | title=Proceedings of the fifth annual international conference on Computational biology - RECOMB '01 | year=2001 | last1=Hallett | first1=M. T. | last2=Lagergren | first2=J. | pages=149–156 | isbn=1581133537 | s2cid=5804061 }}</ref>
 
The progressive development of phylogenetic reconciliation was thus possible through exchanges between multiple research communities studying phylogenies at the host and symbiont, gene and species, or biogeography levels. This story and its modern developments have been reviewed several times, generally focusing on specific pairs of levels, with a few exceptions.<ref name=page_maps_1994>{{cite journal | doi=10.1093/sysbio/43.1.58 | title=Maps Between Trees and Cladistic Analysis of Historical Associations among Genes, Organisms, and Areas | year=1994 | last1=Page | first1=R. D. M. | journal=Systematic Biology | volume=43 | pages=58–77 }}</ref><ref name=wieseke_unifying_2013/> New developments start to bring the different frameworks together with new integrative models.

==Pocket Gophers and their chewing lices: a classical example==

[[File:Gophers and lices tanglegrams and reconciliation scenarios.svg|thumb|left|[[Tanglegram]] and two proposed reconciliation scenarios for [[Geomyidae|pocket gophers]] and their chewing lice  symbionts. For the host, O. stands for ''[[Orthogeomys]]'', G. for ''[[Geomys]]'' and T. for ''[[Thomomys]]''; for the symbiont, G. stands for ''[[Geomydoecus]]'' and T. for ''[[Thomoydoecus]]''.]]

Pocket gophers ([[Geomyidae]]) and their chewing lice ([[Trichodectidae]]) form a well studied system of host and symbiont coevolution.<ref name=hafner_phylogenetic_1988>{{Cite journal|pmid = 3347269| year=1988 | last1=Hafner | first1=M. S. | last2=Nadler | first2=S. A. | title=Phylogenetic trees support the coevolution of parasites and their hosts | journal=Nature | volume=332 | issue=6161 | pages=258–259 | doi=10.1038/332258a0 | bibcode=1988Natur.332..258H | s2cid=4236760 }}</ref> The phylogeny of host and symbiont and the matching of the leaves of their trees are depicted on the left. For the host, O. stands for ''[[Orthogeomys]]'', G. for ''[[Geomys]]'' and T. for ''[[Thomomys]]''; for the symbiont, G. stands for ''[[Geomydoecus]]'' and T. for ''[[Thomoydoecus]]''.
Reconciling the two trees means giving a scenario with evolutionary events and matching on the ancestral nodes depicting the coevolution of the two trees. The events considered in this system are the events of the DTL model: duplication, transfer (or host switch), loss, and cospeciation, the null event of coevolution.
Two scenarios were proposed in two studies,<ref name=page_parallel_1994>{{cite journal |last1=Page |first1=Roderic D.M. |title=Parallel Phylogenies: Reconstructing the History of Host-Parasite Assemblages |journal=Cladistics |date=June 1994 |volume=10 |issue=2 |pages=155–173 |doi=10.1111/j.1096-0031.1994.tb00170.x|doi-access=free }}</ref><ref name=ronquist_reconstructing_1995>{{Cite journal|pmid = 34920597| year=1995 | last1=Ronquist | first1=F. | title=Reconstructing the History of Host-Parasite Associations Using Generalised Parsimony | journal=Cladistics | volume=11 | issue=1 | pages=73–89 | doi=10.1111/j.1096-0031.1995.tb00005.x | s2cid=86298930 | doi-access=free }}</ref> using two different frameworks which could be deemed as pre-dynamic programming DTL<ref>DTL stands for ""Duplication, horizontal Transfer and Loss</ref> reconciliation.
In modern DTL reconciliation frameworks, costs are assigned to events. The two scenarios were then shown to correspond to [[Maximum parsimony (phylogenetics)|maximum parsimonious]] reconciliation with different cost assignments.<ref name=charleston_jungles_1998/>
The scenario A uses 6 cospeciations, 2 duplications, 3 losses and 2 host switches to reconcile the two trees, while scenario B uses 5 cospeciations, 3 duplications, 3 losses and 2 host switches. The cost of a scenario is the sum of the cost of its events. For instance, with a cost of 0 for cospeciation, 2 for duplication, 1 for loss and 3 for host switch, scenario A has a cost of <math>6 \times 0 + 1\times 2 + 3\times 1+ 1 \times 3 = 8</math> and scenario B of <math>5\times 0 + 1 \times 2 + 3 \times 1 + 2 \times 3=11</math>, and so according to a parsimonious principle, scenario A would be deemed more likely (scenario A stays more likely as long as the cost of cospeciation is less than the cost of duplication).

==Development of Phylogenetic Reconciliation Models==
[[File:Phylogenetic reconciliation summary.svg|thumb|Graphical overview of reconciliation events, inputs, outputs, and computational difficulties.<ref name=Phylogenetic-reconciliation-summary>This table is intended to serve as illustration to the 2-Level reconciliation section of Menet et al. (2022) Phylogenetic reconciliation. PLoS Comput Biol 18(11): e1010621.[[:doi:10.1371/journal.pcbi.1010621]] and can be read along with it. Adding the horizontal Transfer event adds new, more parsimonious solutions compared to the previous DL model (A). With this new event, costs must be assigned to D, T and L events, and different costs give different solutions (B). Not all scenarios including transfers are time feasible. Some might include time constraints incompatible with the upper tree (C). Transfer can go from a species to one of its descendant via a sister lineages that went extinct (D). In biogeography, a tree like structure can be constructed to account for the possible migrations between different geographical areas (E). In some cases, an exponential number of scenarios might be most parsimonious, for example when two equivalent patterns have the same cost (F). The lower tree can be unrooted (G),  multifurcating (H), or given as a sample of potential trees (I) and reconciliation can be used to resolve those uncertainties to get a binary rooted lower tree. Reconciliation score can also be used to help construct an upper tree (J). Dynamic programming is limited by the fact that it assumes independence between sister lineages, which makes it unable to consider replacing transfers or gene conversion (K), as well as  Failure to diverge (L) and Incomplete Lineage Sorting (M), two population level events.</ref>]]

Models and methods used today in phylogeny are the result of several decades of research, made progressively complex, driven by the nature of the data and the quest for biological realism on one side, and the limits and progresses of mathematical and algorithmic methods on the other.

===Pre-reconciliation models: characters on trees===
Character methods can be used when there is no tree available for one of the levels, but only values for a character at the leaves of a phylogenetic tree for the other level. A model defines the events of character value change, their rate, probabilities or costs. For instance, the character can be the presence of a host on a symbiont tree,<ref name=brooks_81/> the geographical region on a species tree,<ref name=Wiley1988>{{cite journal | doi=10.2307/2992373 | jstor=2992373 | title=Parsimony Analysis and Vicariance Biogeography | last1=Wiley | first1=E. O. | journal=Systematic Zoology | year=1988 | volume=37 | issue=3 | pages=271–290 }}</ref> the number of genes on a genome tree,<ref name=csuros_streamlining_2009>{{Cite journal|pmid = 19570746| year=2009 | last1=Csurös | first1=M. | last2=Miklós | first2=I. | title=Streamlining and large ancestral genomes in Archaea inferred with a phylogenetic birth-and-death model | journal=Molecular Biology and Evolution | volume=26 | issue=9 | pages=2087–2095 | doi=10.1093/molbev/msp123 | pmc=2726834 }}</ref> or nucleotides in a sequence.<ref name=Felsenstein2004/>
Such methods thus aim at [[ancestral reconstruction|reconstructing ancestral characters]] at internal nodes of the tree.<ref name="Groussin2016">{{cite book | doi=10.1016/B978-0-12-800049-6.00166-9 | chapter=Ancestral Reconstruction: Theory and Practice | title=Encyclopedia of Evolutionary Biology | year=2016 | last1=Groussin | first1=M. | last2=Daubin | first2=V. | last3=Gouy | first3=M. | last4=Tannier | first4=E. | pages=70–77 | isbn=9780128004265 | url=https://hal.archives-ouvertes.fr/hal-01334934/file/ancestralrec_resubmission.pdf }}</ref>

Although these methods have produced results on genome evolution, the utility of a second tree appears with very simple examples. If a symbiont has recently acquired the ability to spread in a group of species and thus it is present in most of them, character methods will wrongly indicate that the common ancestor of the hosts already had the symbiont. In contrast, a comparison of the symbiont and host trees would show discrepancies revealing horizontal transfers.

===The origins of reconciliation: the Duplication Loss model and the Lowest Common Ancestor mapping===
[[Gene duplication|Duplication]] and [[Human evolutionary genetics#Gene loss|loss]] were invoked first to explain the presence of multiple copies of a gene in a genome or its absence in certain species.<ref name=Zuckerkandl1965/> It is possible with those two events to reconcile any two trees,<ref name=goodman_fitting_1979/> i.e. to map the nodes and branches of the lower and upper trees, or equivalently to give a list of evolutionary events explaining the discrepancies between the upper tree and the lower tree.
A most parsimonious Duplication and Loss (DL) reconciliation is computed through the [[lowest common ancestor|Lowest Common Ancestor]] (LCA) mapping: proceeding from the leaves to the [[Phylogenetic tree#Rooted tree|root]], each [[Tree (data structure)#Terminology|internal node]] is mapped to the lowest common ancestor of the mapping of its two children.

===A Markovian model for reconciliation===

The LCA mapping in the DL model follows a [[Maximum parsimony (phylogenetics)|parsimony principle]]: no event should be invoked if it is not necessary. However the use of this principle is debated,<ref name=Felsenstein2004/> and it is commonly admitted that it is more accurate in molecular evolution to fit a probabilistic model as a [[random walk]], which does not necessarily produce parsimonious scenarios.
A [[Birth–death process|birth and death Markovian model]] is such a model that can generate a lower tree "inside" a fixed upper one from root to leaves.<ref name=arvestad_bayesian_2003>{{Cite journal|pmid = 12855432| year=2003 | last1=Arvestad | first1=L. | last2=Berglund | first2=A. C. | last3=Lagergren | first3=J. | last4=Sennblad | first4=B. | title=Bayesian gene/Species tree reconciliation and orthology analysis using MCMC | journal=Bioinformatics | volume=19 | issue=Suppl 1 | pages=i7-15 | doi=10.1093/bioinformatics/btg1000 }}</ref>
[[Statistical inference]] provides a framework to find most likely scenarios, and in that case, a [[Maximum likelihood estimation|maximum likelihood]] reconciliation of two trees is also a parsimonious one. In addition, it is possible with such a framework to sample scenarios, or integrate over several possible scenarios in order to test different hypotheses, for example to explore the space of lower trees. Moreover, probabilistic models can be integrated into larger models, as probabilities simply multiply when assuming independence, for instance combining sequence evolution and DL reconciliation.<ref name="Arvestad_gene_2004">{{cite book | doi=10.1145/974614.974657 | chapter=Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution | title=Proceedings of the eighth annual international conference on Computational molecular biology - RECOMB '04 | year=2004 | last1=Arvestad | first1=Lars | last2=Berglund | first2=Ann-Charlotte | last3=Lagergren | first3=Jens | last4=Sennblad | first4=Bengt | pages=326–335 | isbn=1581137559 | s2cid=12364792 }}</ref>

===Introducing horizontal transfer ===

[[File:Phylogenetic reconciliation DL and DTL.svg|thumb|Phylogenetic reconciliations in Duplication Loss and Duplication Transfer Loss]]

Host switch, i.e. inheritance of a symbiont from a kin lineage, is a crucial event in the evolution of parasitic or symbiotic relationships between species. This horizontal transfer also models migration events in [[biogeography]] and became of interest for the reconciliation of gene and species trees when it appeared that many discrepancies could not simply be explained by duplication and loss and that [[horizontal gene transfer]] (HGT) was a major evolutionary process in micro-organisms evolution. 
This switching, or horizontal transfer, pattern can also model [[Genetic admixture|admixture]] or [[introgression]].<ref name=yu_maximum_2014>{{Cite journal|pmid = 25368173| year=2014 | last1=Yu | first1=Y. | last2=Dong | first2=J. | last3=Liu | first3=K. J. | last4=Nakhleh | first4=L. | title=Maximum likelihood inference of reticulate evolutionary histories | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=111 | issue=46 | pages=16448–16453 | doi=10.1073/pnas.1407950111 | pmc=4246314 | bibcode=2014PNAS..11116448Y | doi-access=free }}</ref>
It is considered in character methods, without information from the symbiont phylogeny.<ref name=brooks_81/><ref name=csuos_count:_2010>{{Cite journal|pmid = 20551134| year=2010 | last1=Csurös | first1=M. | title=Count: Evolutionary analysis of phylogenetic profiles with parsimony and likelihood | journal=Bioinformatics | volume=26 | issue=15 | pages=1910–1912 | doi=10.1093/bioinformatics/btq315 | doi-access=free }}</ref>
On top of the DL model, horizontal transfer enables new and very different reconciliation scenarios.

===The simple yet powerful dynamic programming approach===

The LCA reconciliation method yields a unique solution, which has been shown to be optimal for the problem of minimizing the weighted number of events, whatever the relative weights of duplication and loss.<ref name=Chauve2009>Chauve C and El-Mabrouk N (2009) New Perspectives on Gene Family Evolution: Losses in Reconciliation and a Link with Supertrees. RECOMB 5541:46-58</ref> In contrast, with Duplication, horizontal Transfer and Loss (DTL), there can be several equally parsimonious reconciliations. For instance, a succession of duplications and losses can be replaced by a single transfer. One of the first ideas to define a computational problem and approach a resolution was, in a host/symbiont framework, to maximize the number of [[Cospeciation|co-speciations]] with a heuristic algorithm.<ref name=page_parallel_1994/>
Another solution is to give relative costs to the events and find a scenario that minimizes the sum of the costs of its events.<ref name=charleston_jungles_1998/> 
In the probabilistic model frameworks, the equivalent task consists of assigning rates or probabilities to events and search for maximum likelihood scenarios, or sample scenarios according to their likelihood. All these problems are solved with a [[dynamic programming]] approach. This dynamic programming method involves traversing the two trees in a [[Tree traversal|postorder]].
Proceeding from the leaves and then going up in the two trees, for each couple of internal nodes (one for each tree), the cost of a most parsimonious DTL reconciliation is computed.<ref name=charleston_jungles_1998/>

In a parsimony framework, costs of reconciling a lower subtree rooted at <math>l</math> with an upper subtree rooted at <math>U</math> is initialized for the leaves with their matching:

<div class="center"><math>
\begin{align}
  c(U,l) = 0 \mbox{ if } l \in U \mbox{ else } c(U,l) = \infty\\
\end{align}
</math></div>

And then inductively, denoting <math>l^{\prime}, l^{\prime \prime}</math> the children of <math>l, U^{\prime},U^{\prime \prime}</math> the children of <math>U, c^S,c^D,c^T,c^L </math> the costs associated with speciation, duplication, horizontal transfer and loss, respectively (with <math>c^S</math> often fixed to 0),

<div class="center"><math>

  c(U,l) = \min \begin{cases}

    c^S + \min( c(U^{\prime},l^{\prime})+c(U^{\prime \prime},l^{\prime \prime}), c(U^{\prime \prime},l^{\prime}) + c(U^{\prime},l^{\prime \prime}), c(U^{\prime},l) + c^L, c(U^{\prime \prime},l) + c^L )\\
    c^D + c(U,l^{\prime}) + c(U,l^{\prime \prime})\\
    c^T + \min( \min_{V}(c(V,l^{\prime})) +c(U,l^{\prime \prime}), \min_{V}(c(V,l^{\prime \prime}))+c(U,l^{\prime})) 
\end{cases}
</math></div>

The costs <math>\min_V(c(V,l^{\prime}))</math> and <math>\min_V(c(V,l^{\prime \prime}))</math>, because they do not depend on <math>U</math>, can be computed once for all <math>U</math>, hence achieving quadratic [[Computational complexity|complexity]] to compute <math>c</math> for all couples of <math>U</math> and <math>l</math>. The cost of losses only appears in association with other events because in parsimony, a loss can always be associated with the preceding event in the tree.

The induction behind the use of dynamic programming is based on always progressing in the trees toward the roots. However some combinations of events that can happen consecutively can make this induction ill-defined. 
One such combination consists of a transfer followed immediately by a loss in the donor lineage (TL). Restricting the use of this TL event repairs the induction.<ref name=Doyon2010>Doyon J, Scornavacca C, Gorbunov K, Szöllősi G, Ranwez V et al. (2010) An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers. RECOMB-CG</ref> With an unlimited use, it is necessary to use or add other known methods to solve systems of equations like [[Fixed point (mathematics)|fixed point methods]],<ref name=szollosi_efficient_2013>{{Cite journal|pmid = 23925510| year=2013 | last1=Szöllõsi | first1=G. J. | last2=Rosikiewicz | first2=W. | last3=Boussau | first3=B. | last4=Tannier | first4=E. | last5=Daubin | first5=V. | title=Efficient exploration of the space of reconciled gene trees | journal=Systematic Biology | volume=62 | issue=6 | pages=901–912 | doi=10.1093/sysbio/syt054 | pmc=3797637 }}</ref> or numerical solving of differential equations.<ref name=ree_maximum_2008/> In 2016, only two out of seven of the most commonly used parsimony reconciliation programs did handle TL events,<ref name=jacox_eccetera:_2016>{{Cite journal|pmid = 27153713| year=2016 | last1=Jacox | first1=E. | last2=Chauve | first2=C. | last3=Szöllősi | first3=G. J. | last4=Ponty | first4=Y. | last5=Scornavacca | first5=C. | title=EcceTERA: Comprehensive gene tree-species tree reconciliation using parsimony | journal=Bioinformatics | volume=32 | issue=13 | pages=2056–2058 | doi=10.1093/bioinformatics/btw105 | doi-access=free }}</ref> although their consideration can drastically change the result of a reconciliation.<ref name=doyon_models_2011>{{Cite journal|pmid = 21949266| year=2011 | last1=Doyon | first1=J. P. | last2=Ranwez | first2=V. | last3=Daubin | first3=V. | last4=Berry | first4=V. | title=Models, algorithms and programs for phylogeny reconciliation | journal=Briefings in Bioinformatics | volume=12 | issue=5 | pages=392–400 | doi=10.1093/bib/bbr045 | doi-access=free }}</ref>

Unlike LCA mapping, DTL reconciliation typically yields several scenarios of minimal cost, in some cases an exponential number. The strength of the dynamic programming approach is that it enables to compute a minimum cost of coevolution of the input upper and lower tree in [[Time complexity|quadratic time]],<ref name=bansal_efficient_2012>{{Cite journal|pmid = 22689773| year=2012 | last1=Bansal | first1=M. S. | last2=Alm | first2=E. J. | last3=Kellis | first3=M. | title=Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss | journal=Bioinformatics | volume=28 | issue=12 | pages=i283-91 | doi=10.1093/bioinformatics/bts225 | pmc=3371857 }}</ref> and to get a most parsimonious scenario through [[backtracking]].
It can also be transposed to a probabilistic framework to compute the likelihood of coevolution and get a most likely reconciliation, replacing costs with rates, minimums by sums and sums by products.<ref name=szollosi_phylogenetic_2012>{{Cite journal|pmid = 23043116| year=2012 | last1=Szöllosi | first1=G. J. | last2=Boussau | first2=B. | last3=Abby | first3=S. S. | last4=Tannier | first4=E. | last5=Daubin | first5=V. | title=Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative timing of speciations | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=109 | issue=43 | pages=17513–17518 | doi=10.1073/pnas.1202997109 | pmc=3491530 | bibcode=2012PNAS..10917513S | doi-access=free }}</ref>
Moreover, through multiple backtracks, the approach is suitable for enumerating all parsimonious solutions or to sample scenarios, optimal and sub-optimal, according to their likelihood.

===Estimation of event costs and rates===

[[File:Phylogenetic reconciliation events costs.svg|thumb|Different cost assignments can give different most parsimonious solutions.]]

Dynamic programming per se is only a partial solution and does not solve several problems raised by reconciliation.
Defining a most parsimonious DTL reconciliation requires assigning costs to the different kinds of events (D, T and L). Different cost assignments can yield different reconciliation scenarios, so there is a need for a way to choose those costs.
There is a diversity of approaches to do so. CoRe-PA<ref name=merkle_parameter-adaptive_2010>{{Cite journal|pmid = 20122236| year=2010 | last1=Merkle | first1=D. | last2=Middendorf | first2=M. | last3=Wieseke | first3=N. | title=A parameter-adaptive dynamic programming approach for inferring cophylogenies | journal=BMC Bioinformatics | volume=11 | issue=Suppl 1 | pages=S60 | doi=10.1186/1471-2105-11-S1-S60 | pmc=3009534 | doi-access=free }}</ref> explores in a recursive manner the space of cost vectors, searching for a good matching with the event frequencies in reconciliations.
ALE<ref name=szollosi_phylogenetic_2012/> uses the same idea in a probabilistic framework to estimate the event rates by maximum likelihood.
Alternatively, COALA<ref name=baudet_cophylogeny_2015>{{Cite journal|pmid = 25540454| year=2015 | last1=Baudet | first1=C. | last2=Donati | first2=B. | last3=Sinaimeri | first3=B. | last4=Crescenzi | first4=P. | last5=Gautier | first5=C. | last6=Matias | first6=C. | last7=Sagot | first7=M. F. | title=Cophylogeny reconstruction via an approximate Bayesian computation | journal=Systematic Biology | volume=64 | issue=3 | pages=416–431 | doi=10.1093/sysbio/syu129 | pmc=4395844 }}</ref> is a preprocess using [[approximate Bayesian computation]] with sequential [[Monte Carlo method|Monte Carlo]]: simulation and statistic rejection or acceptance of parameters with successive refinement.

In the parsimony framework, it is also possible to divide the space of possible event costs into areas of costs which lead to the same [[Pareto efficiency|Pareto optimal solution]].<ref name=libeskind-hadas_pareto-optimal_2014>{{Cite journal|pmid = 24932009| year=2014 | last1=Libeskind-Hadas | first1=R. | last2=Wu | first2=Y. C. | last3=Bansal | first3=M. S. | last4=Kellis | first4=M. | title=Pareto-optimal phylogenetic tree reconciliation | journal=Bioinformatics | volume=30 | issue=12 | pages=i87-95 | doi=10.1093/bioinformatics/btu289 | pmc=4058917 }}</ref>
Pareto optimal reconciliations are such that no other reconciliation has a strictly inferior cost for one type of event (duplication, transfer or loss), and less or equal for the others.

It is possible as well to rely on external considerations in order to choose the event costs. For example, the software Angst<ref name=david_rapid_2011>{{Cite journal|pmid = 21170026| year=2011 | last1=David | first1=L. A. | last2=Alm | first2=E. J. | title=Rapid evolutionary innovation during an Archaean genetic expansion | journal=Nature | volume=469 | issue=7328 | pages=93–96 | doi=10.1038/nature09649 | bibcode=2011Natur.469...93D | hdl=1721.1/61263 | s2cid=4420725 | hdl-access=free }}</ref> chooses the costs that minimize the variation of genome size, in number of genes, between parent and children species.

===The problem of temporal feasibility===

[[File:Phylogenetic reconciliation time unfeasibility.svg|thumb|Not all scenarios including transfers are time feasible, some might include time constraints incompatible with the species tree.]]

The dynamic programming method works for dated (internal nodes are totally ordered) or undated upper trees. However, with undated trees, there is a temporal feasibility issue. Indeed, a horizontal transfer implies that the donor and the receiver are contemporaneous, therefore implying a time constraint on the tree. In consequence, two horizontal transfers may be incompatible, because they imply contradicting time constraints.
The dynamic programming approach can not easily check for such incompatibilities. If the upper tree is undated, finding a temporally feasible most parsimonious reconciliation is [[NP-hardness|NP-hard]].<ref name=hallett_efficient_2001>{{cite book |last1=Hallett |first1=M. T. |last2=Lagergren |first2=J. |title=Proceedings of the fifth annual international conference on Computational biology |chapter=Efficient algorithms for lateral gene transfer problems |date=2001 |pages=149–156 |doi=10.1145/369133.369188|isbn=1581133537 |s2cid=5804061 }}</ref><ref name=tofigh_simultaneous_2011>{{Cite journal|pmid = 21233529| year=2011 | last1=Tofigh | first1=A. | last2=Hallett | first2=M. | last3=Lagergren | first3=J. | title=Simultaneous identification of duplications and lateral gene transfers | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=8 | issue=2 | pages=517–535 | doi=10.1109/TCBB.2010.14 | s2cid=16462428 | url=http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-10969 }}</ref><ref name=ovadia_co_2011>{{Cite journal|pmid = 20715926| year=2011 | last1=Ovadia | first1=Y. | last2=Fielder | first2=D. | last3=Conow | first3=C. | last4=Libeskind-Hadas | first4=R. | title=The co phylogeny reconstruction problem is NP-complete | journal=Journal of Computational Biology | volume=18 | issue=1 | pages=59–65 | doi=10.1089/cmb.2009.0240 }}</ref> It is [[Parameterized complexity|fixed parameter tractable]], which means that there are algorithms running in time bounded by an exponential of the number of transfers in the output scenarios.<ref name=tofigh_simultaneous_2011/>
Some solutions imply [[Integer programming|integer linear programming]]<ref name=wieseke_cophylogenetic_2015>{{Cite journal|pmid = 26671795| year=2015 | last1=Wieseke | first1=N. | last2=Hartmann | first2=T. | last3=Bernt | first3=M. | last4=Middendorf | first4=M. | title=Cophylogenetic Reconciliation with ILP | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=12 | issue=6 | pages=1227–1235 | doi=10.1109/TCBB.2015.2430336 | s2cid=2291208 }}</ref> or [[branch and bound]] exploration.<ref name=wieseke_unifying_2013/>
If the upper tree is dated, then there is no incompatibility issue because horizontal transfers can be constrained to never go backward in time. Finding a coherent optimal reconciliation is then solved in [[Time complexity#Polynomial time|polynomial time]]<ref name=tofigh_simultaneous_2011/> or with a speed-up in RASCAL,<ref name=drinkwater_improved_2014>{{Cite journal |last1=Drinkwater |first1=Benjamin |last2=Charleston |first2=Michael A. |title=An improved node mapping algorithm for the cophylogeny reconstruction problem |journal=Coevolution |date=2 January 2014 |volume=2 |issue=1 |pages=1–17 |doi=10.1080/23256214.2014.906070|doi-access=free }}</ref><ref name=drinkwater_rascal_2016>{{Cite journal|pmid = 26828619| year=2016 | last1=Drinkwater | first1=B. | last2=Charleston | first2=M. A. | title=RASCAL: A Randomized Approach for Coevolutionary Analysis | journal=Journal of Computational Biology | volume=23 | issue=3 | pages=218–227 | doi=10.1089/cmb.2015.0111 | url=https://figshare.com/articles/journal_contribution/22948736 }}</ref> by testing only a fraction of node mappings.

Most of the software taking undated trees does not look for temporal feasibility, except Jane,<ref name=conow_jane_2010>{{Cite journal|pmid = 20181081| year=2010 | last1=Conow | first1=C. | last2=Fielder | first2=D. | last3=Ovadia | first3=Y. | last4=Libeskind-Hadas | first4=R. | title=Jane: A new tool for the cophylogeny reconstruction problem | journal=Algorithms for Molecular Biology | volume=5 | page=16 | doi=10.1186/1748-7188-5-16 | pmc=2830923 | doi-access=free }}</ref> which explores the space of total orders via a genetic algorithm, or, in a post process, Notung,<ref name=durand_hybrid_2006>{{Cite journal|pmid = 16597243| year=2006 | last1=Durand | first1=D. | last2=Halldórsson | first2=B. V. | last3=Vernot | first3=B. | title=A hybrid micro-macroevolutionary approach to gene tree reconstruction | journal=Journal of Computational Biology | volume=13 | issue=2 | pages=320–335 | doi=10.1089/cmb.2006.13.320 | url=https://figshare.com/articles/journal_contribution/6097109 }}</ref> and Eucalypt,<ref name=donati_eucalypt_2015>{{Cite journal|pmid = 25648467| year=2015 | last1=Donati | first1=B. | last2=Baudet | first2=C. | last3=Sinaimeri | first3=B. | last4=Crescenzi | first4=P. | last5=Sagot | first5=M. F. | title=EUCALYPT: Efficient tree reconciliation enumerator | journal=Algorithms for Molecular Biology | volume=10 | issue=1 | page=3 | doi=10.1186/s13015-014-0031-3 | pmc=4310143 | doi-access=free }}</ref> which searches inside the set of optimal solutions for time consistent ones. 
Other methods work as supplementary layers to reconciliations, correcting reconciliations<ref name="ma_dtl-rnb_2018">{{Cite journal|pmid = 26955051| year=2018 | last1=Ma | first1=W. | last2=Smirnov | first2=D. | last3=Forman | first3=J. | last4=Schweickart | first4=A. | last5=Slocum | first5=C. | last6=Srinivasan | first6=S. | last7=Libeskind-Hadas | first7=R. | title=DTL-RNB: Algorithms and Tools for Summarizing the Space of DTL Reconciliations | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=15 | issue=2 | pages=411–421 | doi=10.1109/TCBB.2016.2537319 | s2cid=4566350 | doi-access=free }}</ref> or returning a subset of feasible transfers,<ref name=chauve_maxtic_2017>{{Cite journal |last1=Chauve |first1=Cédric |last2=Rafiey |first2=Akbar |last3=Davín |first3=Adrián A. |last4=Scornavacca |first4=Celine |last5=Veber |first5=Philippe |last6=Boussau |first6=Bastien |last7=Szöllősi |first7=Gergely J. |last8=Daubin |first8=Vincent |last9=Tannier |first9=Eric |title=MaxTiC: Fast ranking of a phylogenetic tree by Maximum Time Consistency with lateral gene transfers |date=14 April 2017 |doi=10.1101/127548|s2cid=21910535 }}</ref> which can be used to date a species tree.<ref name=chauve_maxtic_2017/><ref name=davin_gene_2018>{{Cite journal|pmid = 29610471| year=2018 | last1=Davín | first1=A. A. | last2=Tannier | first2=E. | last3=Williams | first3=T. A. | last4=Boussau | first4=B. | last5=Daubin | first5=V. | last6=Szöllősi | first6=G. J. | title=Gene transfers can date the tree of life | journal=Nature Ecology & Evolution | volume=2 | issue=5 | pages=904–909 | doi=10.1038/s41559-018-0525-3 | pmc=5912509 | bibcode=2018NatEE...2..904D }}</ref>

===Expanding phylogenies: Transfers from the dead===

[[File:Phylogenetic reconciliation Transfer from the dead.svg|thumb|Transfer can go from a species to one of its descendant via a sister lineages that went extinct.]]

In phylogenetics in general, it is important to keep in mind that the extant and ancestral species that are represented in any phylogeny are only a sparse sample of the species that currently exist or ever have existed. This is why one can safely assume that all transfers that can be detected using phylogenetic methods have originated in lineages that are, strictly speaking, absent from a studied phylogeny.<ref name=szollosi_lateral_2013>{{Cite journal|pmid = 23355531| year=2013 | last1=Szöllosi | first1=G. J. | last2=Tannier | first2=E. | last3=Lartillot | first3=N. | last4=Daubin | first4=V. | title=Lateral gene transfer from the dead | journal=Systematic Biology | volume=62 | issue=3 | pages=386–397 | doi=10.1093/sysbio/syt003 | pmc=3622898 }}</ref> Accounting for extinct or unsampled biodiversity in phylogenetic studies can give a better understanding of these processes.<ref name=davin2019>{{Cite journal|pmid = 31566657| year=2020 | last1=Davín | first1=A. A. | last2=Tricou | first2=T. | last3=Tannier | first3=E. | last4=De Vienne | first4=D. M. | last5=Szöllősi | first5=G. J. | title=Zombi: A phylogenetic simulator of trees, genomes and sequences that accounts for dead linages | journal=Bioinformatics | volume=36 | issue=4 | pages=1286–1288 | doi=10.1093/bioinformatics/btz710 | pmc=7031779 }}</ref> Originally, DTL reconciliation methods did not recognize this phenomenon and only allowed for transfer between contemporaneous branches of the tree, hence ignoring most plausible solutions. However, methods working on undated upper trees can be seen as implicitly handling the unknown diversity by allowing transfers "to the future" from the point of view of one phylogeny, that is, the donor is more ancient than the recipient. A transfer to the future can be translated into a speciation to unknown species, followed by a transfer from unknown species.
ALE<ref name=szollosi_lateral_2013/> in its dated version explicitly takes the unknown diversity into account by adding a [[Moran process]] of speciation/extinctions of species to the dated birth/death model of gene evolution. 
Transfers from the dead are also handled in a parsimonious setting by Tera and ecceTERA,<ref name=scornavacca_joint_2015>{{Cite journal|pmid = 25380957| year=2015 | last1=Scornavacca | first1=C. | last2=Jacox | first2=E. | last3=Szöllősi | first3=G. J. | title=Joint amalgamation of most parsimonious reconciled gene trees | journal=Bioinformatics | volume=31 | issue=6 | pages=841–848 | doi=10.1093/bioinformatics/btu728 | pmc=4380024 }}</ref><ref name=jacox_eccetera:_2016/> showing that considering these transfers improves the capacity to reconstruct gene trees using reconciliation, and with a more explicit model<ref name=weiner_improved_2021>{{cite journal |last1=Weiner |first1=Samson |last2=Bansal |first2=Mukul S. |title=Improved Duplication-Transfer-Loss Reconciliation with Extinct and Unsampled Lineages |journal=Algorithms |date=5 August 2021 |volume=14 |issue=8 |pages=231 |doi=10.3390/a14080231|doi-access=free }}</ref> and in a probabilistic setting, in ALE undated.<ref name=szollosi_genome-scale_2015>{{Cite journal|pmid = 26323765| year=2015 | last1=Szöllősi | first1=G. J. | last2=Davín | first2=A. A. | last3=Tannier | first3=E. | last4=Daubin | first4=V. | last5=Boussau | first5=B. | title=Genome-scale phylogenetic analysis finds extensive gene transfer among fungi | journal=Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences | volume=370 | issue=1678 | doi=10.1098/rstb.2014.0335 | pmc=4571573 }}</ref>

===The specificity of biogeography: a tree like structure for the "evolution" of areas===

[[File:Phylogenetic reconciliation and geography.svg|thumb|In biogeography, a tree like structure can be constructed to account for the possible migrations between different geographical areas.]]

In biogeography, some applications of reconciliation approaches consider as an upper tree an area [[cladogram]] with defined ancestral nodes. For instance, the root can be [[Pangaea]] and the nodes contemporary [[continents]]. Sometimes, internal nodes are not ancestral areas but the unions of the areas of their children, to account for the possibility of species evolving along the lower tree to inhabit one or several areas. In this case, the evolutionary events are migration, where one species colonizes a new area, [[allopatric speciation]], or vicariance, equivalent to [[co-speciation]] in host/symbiont comparisons.
Even though this approach does not always give a tree (if the unions AB and BC of leaves A, B, C exist, a child can have several parents), and this structure is not associated with time (it is possible for a species to go from A to AB by migration, as well as from AB to A by extinction), reconciliation methods&mdash;with events and dynamic programming&mdash;can infer evolutionary scenarios between the upper geographical structure and the lower species tree. Diva<ref name=ronquist_dispersal-vicariance_1997>Ronquist F (1997) Phylogenetic approaches in coevolution and biogeography. Zoologica Scripta 26:313--322</ref> and Lagrange<ref name=ree_likelihood_2005>{{Cite journal|pmid = 16396171| year=2005 | last1=Ree | first1=R. H. | last2=Moore | first2=B. R. | last3=Webb | first3=C. O. | last4=Donoghue | first4=M. J. | title=A likelihood framework for inferring the evolution of geographic range on phylogenetic trees | journal=Evolution; International Journal of Organic Evolution | volume=59 | issue=11 | pages=2299–2511 | doi=10.1111/j.0014-3820.2005.tb00940.x | s2cid=23245573 | doi-access=free }}</ref><ref name=ree_maximum_2008>{{Cite journal|pmid = 18253896| year=2008 | last1=Ree | first1=R. H. | last2=Smith | first2=S. A. | title=Maximum likelihood inference of geographic range evolution by dispersal, local extinction, and cladogenesis | journal=Systematic Biology | volume=57 | issue=1 | pages=4–14 | doi=10.1080/10635150701883881 | s2cid=14205291 | doi-access=free }}</ref> are two reconciliation models constructing such a tree-like structure and then applying reconciliation, the first with a parsimony principle, the second in a probabilistic framework. Additionally, BioGeoBEARS<ref name=matzke_probabilistic_2013>{{Cite journal|pmid = 25123369| year=2014 | last1=Matzke | first1=N. J. | title=Model selection in historical biogeography reveals that founder-event speciation is a crucial process in Island Clades | journal=Systematic Biology | volume=63 | issue=6 | pages=951–970 | doi=10.1093/sysbio/syu056 | doi-access=free }}</ref> is a biogeography inference package that reimplemented DIVA and Lagrange models and allows for new options, like distant dependent transfers<ref name="van_dam_evaluating_2016">{{cite journal | doi=10.1111/jbi.12727 | title=Evaluating the influence of connectivity and distance on biogeographical patterns in the south-western deserts of North America | year=2016 | last1=Van Dam | first1=Matthew H. | last2=Matzke | first2=Nicholas J. | journal=Journal of Biogeography | volume=43 | issue=8 | pages=1514–1532 | bibcode=2016JBiog..43.1514V | s2cid=87276317 }}</ref> and discussion on statistical model selection.<ref name=matzke_probabilistic_2013/>

===Graphical output===
With two trees and multiple evolutionary events linking them to represent, viewing reconciled trees is a challenging but necessary question in order to make reconciliation studies more accessible. Some reconciliation software include annotation of the evolutionary events on the lower trees,<ref name=durand_hybrid_2006/> while others,<ref name=conow_jane_2010/><ref name=santichaivekin_eMPRess_2020>{{Cite journal|pmid = 33216126| year=2021 | last1=Santichaivekin | first1=S. | last2=Yang | first2=Q. | last3=Liu | first3=J. | last4=Mawhorter | first4=R. | last5=Jiang | first5=J. | last6=Wesley | first6=T. | last7=Wu | first7=Y. C. | last8=Libeskind-Hadas | first8=R. | title=EMPRess: A systematic cophylogeny reconciliation tool | journal=Bioinformatics | volume=37 | issue=16 | pages=2481–2482 | doi=10.1093/bioinformatics/btaa978 | doi-access=free }}</ref><ref name=donati_eucalypt_2015/><ref name=merkle_parameter-adaptive_2010/> and specific packages, in DL<ref name=sennblad_primetv_2007>{{Cite journal|pmid = 17484781| year=2007 | last1=Sennblad | first1=B. | last2=Schreil | first2=E. | last3=Berglund Sonnhammer | first3=A. C. | last4=Lagergren | first4=J. | last5=Arvestad | first5=L. | title=Primetv: A viewer for reconciled trees | journal=BMC Bioinformatics | volume=8 | page=148 | doi=10.1186/1471-2105-8-148 | pmc=1891116 | doi-access=free }}</ref> or DTL,<ref name=chevenet_SylvX_2016>{{Cite journal|pmid = 26515823| year=2016 | last1=Chevenet | first1=F. | last2=Doyon | first2=J. P. | last3=Scornavacca | first3=C. | last4=Jacox | first4=E. | last5=Jousselin | first5=E. | last6=Berry | first6=V. | title=SylvX: A viewer for phylogenetic tree reconciliations | journal=Bioinformatics | volume=32 | issue=4 | pages=608–610 | doi=10.1093/bioinformatics/btv625 | doi-access=free }}</ref> trace the lower tree embedded in the upper one. One difficulty in this regard is the variety of output formats for the different reconciliation software. A common standard, recphyloxml,<ref name=duchemin_recphyloxml:_2018>{{Cite journal|pmid = 29762653| year=2018 | last1=Duchemin | first1=W. | last2=Gence | first2=G. | last3=Arigon Chifolleau | first3=A. M. | last4=Arvestad | first4=L. | last5=Bansal | first5=M. S. | last6=Berry | first6=V. | last7=Boussau | first7=B. | last8=Chevenet | first8=F. | last9=Comte | first9=N. | last10=Davín | first10=A. A. | last11=Dessimoz | first11=C. | last12=Dylus | first12=D. | last13=Hasic | first13=D. | last14=Mallo | first14=D. | last15=Planel | first15=R. | last16=Posada | first16=D. | last17=Scornavacca | first17=C. | last18=Szöllosi | first18=G. | last19=Zhang | first19=L. | last20=Daubin | first20=V. | title=RecPhyloXML: A format for reconciled gene trees | journal=Bioinformatics | volume=34 | issue=21 | pages=3646–3652 | doi=10.1093/bioinformatics/bty389 | pmc=6198865 }}</ref> has been established and endorsed by part of the community, and a viewer is available, able to display reconciliation in multi level systems.<ref name=penel_thirdkind_2022>{{Cite journal|pmid = 35139153| year=2022 | last1=Penel | first1=S. | last2=Menet | first2=H. | last3=Tricou | first3=T. | last4=Daubin | first4=V. | last5=Tannier | first5=E. | title=Thirdkind: Displaying phylogenetic encounters beyond 2-level reconciliation | journal=Bioinformatics | volume=38 | issue=8 | pages=2350–2352 | doi=10.1093/bioinformatics/btac062 }}</ref>

==Addressing Additional Practical Considerations==

Applying DTL reconciliation to biological data raises several problems related to uncertainty and confidence levels of input and output. Concerning the output, the uncertainty of the answer calls for an exploration of the whole solution space. Concerning the input, phylogenetic reconciliation has to handle uncertainties in the resolution or rooting of the upper or lower trees, or even to propose roots or resolutions according to their confidence.

===Exploring the space of reconciliations===

[[File:Phylogenetic reconciliation exponential number of solutions.svg|thumb|An exponential number of scenarios might be most parsimonious, for example when two equivalent patterns have the same cost.]]

Dynamic programming makes it possible to sample reconciliations, uniformly among optimal ones<ref name=bansal_reconciliation_2013>{{Cite journal|pmid = 24033262| year=2013 | last1=Bansal | first1=M. S. | last2=Alm | first2=E. J. | last3=Kellis | first3=M. | title=Reconciliation revisited: Handling multiple optima when reconciling with duplication, transfer, and loss | journal=Journal of Computational Biology | volume=20 | issue=10 | pages=738–754 | doi=10.1089/cmb.2013.0073 | pmc=3791060 }}</ref> or according to their likelihood. 
It is also possible to enumerate them in time proportional to the number of solutions,<ref name=donati_eucalypt_2015/> a number which can quickly become intractable (even only for optimal ones). Finding and presenting structure among the multitude of possible reconciliations has been at the center of recent methodological developments, especially for host and symbiont aimed methods. Several works have focused on representing a set of reconciliations in a compact way, from a uniform sample of optimal ones<ref name=bansal_reconciliation_2013/> or by constructing a graph summarizing the optimal solutions.<ref name=scornavacca_representing_2013 >{{Cite journal|pmid = 23600816| year=2013 | last1=Scornavacca | first1=C. | last2=Paprotny | first2=W. | last3=Berry | first3=V. | last4=Ranwez | first4=V. | title=Representing a set of reconciliations in a compact way | journal=Journal of Bioinformatics and Computational Biology | volume=11 | issue=2 | doi=10.1142/S0219720012500254 | s2cid=17688742 | url=https://hal-lirmm.ccsd.cnrs.fr/lirmm-00818801/file/article_graphDTL.pdf }}</ref> This can be achieved by giving support values to specific events based on all optimal (or suboptimal) reconciliations,<ref name=nguyen_support_2013>{{Cite journal|pmid = 24124449| year=2013 | last1=Nguyen | first1=T. H. | last2=Ranwez | first2=V. | last3=Berry | first3=V. | last4=Scornavacca | first4=C. | title=Support measures to estimate the reliability of evolutionary events predicted by reconciliation methods | journal=PLOS ONE | volume=8 | issue=10 | pages=e73667 | doi=10.1371/journal.pone.0073667 | pmc=3790797 | bibcode=2013PLoSO...873667N | doi-access=free }}</ref> or with the use of a consensus reconciled tree.<ref name=kundu_impact_2018>{{Cite journal|pmid = 30367593| year=2018 | last1=Kundu | first1=S. | last2=Bansal | first2=M. S. | title=On the impact of uncertain gene tree rooting on duplication-transfer-loss reconciliation | journal=BMC Bioinformatics | volume=19 | issue=Suppl 9 | page=290 | doi=10.1186/s12859-018-2269-0 | pmc=6101088 | doi-access=free }}</ref><ref name=ma_dtl-rnb_2018/> In a DL model, it is possible to define a median reconciliation, based on shared events and to compute it in polynomial time.<ref name=huber_medians_2018>Huber K, Moulton V, Sagot M-F, Sinaimeri B (2018) Geometric medians in reconciliation spaces of phylogenetic trees. Information Processing Letter. 136: 96–101</ref>
EMPRess<ref name=santichaivekin_eMPRess_2020/> can group similar reconciliations through clustering,<ref name=mawhorter_hierarchical_2019>{{Cite journal|pmid = 31775628| year=2019 | last1=Mawhorter | first1=R. | last2=Libeskind-Hadas | first2=R. | title=Hierarchical clustering of maximum parsimony reconciliations | journal=BMC Bioinformatics | volume=20 | issue=1 | page=612 | doi=10.1186/s12859-019-3223-5 | pmc=6882150 | doi-access=free }}</ref> with all pairwise distance between reconciliations computable in polynomial time (independently of the number of most parsimonious reconciliations).<ref name=santichaivekin_efficient_2019>{{Cite journal|pmid = 31842734| year=2019 | last1=Santichaivekin | first1=S. | last2=Mawhorter | first2=R. | last3=Libeskind-Hadas | first3=R. | title=An efficient exact algorithm for computing all pairwise distances between reconciliations in the duplication-transfer-loss model | journal=BMC Bioinformatics | volume=20 | issue=Suppl 20 | page=636 | doi=10.1186/s12859-019-3203-9 | pmc=6915856 | doi-access=free }}</ref> With the same aim, Capybara<ref name=wang_capybara_2020>{{Cite journal|pmid = 32556075| year=2020 | last1=Wang | first1=Y. | last2=Mary | first2=A. | last3=Sagot | first3=M. F. | last4=Sinaimeri | first4=B. | title=Capybara: Equivalence ClAss enumeration of coPhylogenY event-BAsed ReconciliAtions | journal=Bioinformatics | volume=36 | issue=14 | pages=4197–4199 | doi=10.1093/bioinformatics/btaa498 | doi-access=free }}</ref> defines equivalence classes among reconciliations, efficiently computing representatives for all classes, and outputs with linear delay a given number of reconciliations (first optimal ones, then sub optimal).
The space of most parsimonious reconciliation can be expanded or reduced when increasing or decreasing horizontal transfer allowed distance,<ref name=donati_eucalypt_2015/> which is easily done by dynamic programming.

===Inferring phylogenetic trees with reconciliation===
====Reconciliation and input uncertainty====

Reconciliation works with two fixed trees, a lower and an upper, both assumed correct and rooted. However, those trees are not first hand data. 
The most frequently used data for phylogenetics consists in aligned nucleotidic or proteic sequences. 
Extracting DNA, sequencing, assembling and annotating genomes, recognizing homology relationships among genes and producing multiple alignments for phylogenetic reconstruction are all complex processes where errors can ultimately affect the reconstructed tree.<ref name=boussau_genomes_2010>{{Cite journal|pmid = 19880211| year=2010 | last1=Boussau | first1=B. | last2=Daubin | first2=V. | title=Genomes as documents of evolutionary history | journal=Trends in Ecology & Evolution | volume=25 | issue=4 | pages=224–232 | doi=10.1016/j.tree.2009.09.007 | bibcode=2010TEcoE..25..224B }}</ref>
Any topology or rooting error can be misinterpreted and cause systematic bias. For instance, in DL reconciliations, errors on the lower tree bias the reconciliation toward more duplication events closer to the root and more losses closer to the leaves.<ref name=hahn_bias_2007>{{Cite journal|pmid = 17634151| year=2007 | last1=Hahn | first1=M. W. | title=Bias in phylogenetic tree reconciliation methods: Implications for vertebrate genome evolution | journal=Genome Biology | volume=8 | issue=7 | pages=R141 | doi=10.1186/gb-2007-8-7-r141 | pmc=2323230 | doi-access=free }}</ref>

On the other hand, reconciliation, as a macro evolutionary model, can work as a supplementary layer to the micro evolutionary model of sequence evolution, resolving [[polytomy|polytomies]] (nodes with more than two children) or rooting trees, or be intertwined with it through integrative models in order to get better phylogenies.

Most of the works in this direction focus on gene/species reconciliations, nevertheless some first steps have been made in host/symbiont, such as considering [[Phylogenetic tree#Unrooted tree|unrooted]] symbiont trees<ref name=urbini_exploring_2019>{{Cite journal|pmid = 29993554| year=2018 | last1=Urbini | first1=L. | last2=Sinaimeri | first2=B. | last3=Matias | first3=C. | last4=Sagot | first4=M. F. | title=Exploring the Robustness of the Parsimonious Reconciliation Method in Host-Symbiont Cophylogeny | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=16 | issue=3 | pages=738–748 | doi=10.1109/TCBB.2018.2838667 | s2cid=51613681 | url=https://hal.inria.fr/hal-01842451/file/Robustness_Cophylogeny.pdf }}</ref> or dealing with polytomies in Jane.<ref name=conow_jane_2010/>

====Exploring the space of lower trees with reconciliation====

Reconciliation can easily take unrooted lower trees as input, which is a frequently used feature because trees inferred from molecular data are typically unrooted. It is possible to test all possible roots, or a thoughtful triple traversal of the unrooted tree allows to do it without additional time complexity.<ref name=Doyon2010/> In a duplication-loss model, the set of roots minimizing the costs are found close to one another, forming a "plateau",<ref name=gorecki_unrooted_2013>{{Cite journal|pmid = 23929875| year=2013 | last1=Górecki | first1=P. | last2=Eulenstein | first2=O. | last3=Tiuryn | first3=J. | title=Unrooted tree reconciliation: A unified approach | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=10 | issue=2 | pages=522–536 | doi=10.1109/TCBB.2013.22 | s2cid=13416908 }}</ref> a property which does not generalize to DTL.<ref name=urbini_exploring_2019/><ref name=kundu_impact_2018/>

[[File:Phylogenetic reconciliation tree uncertainty.svg|thumb|The lower tree can be unrooted, multifurcating, or given as a sample of potential trees and reconciliation can be used to resolve those uncertainties to get a binary rooted lower tree.]]

Reconciliation can also take as input [[Binary tree|non binary trees]], that is, with internal nodes with more than two children. Such trees can be obtained for example by contracting branches with low statistical support. Inferring a binary tree from a non binary tree according to reconciliation scores is solved in DL with efficient methods.<ref name=durand_hybrid_2006/><ref name=stolzer_inferring_2012>{{Cite journal|pmid = 22962460| year=2012 | last1=Stolzer | first1=M. | last2=Lai | first2=H. | last3=Xu | first3=M. | last4=Sathaye | first4=D. | last5=Vernot | first5=B. | last6=Durand | first6=D. | title=Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees | journal=Bioinformatics | volume=28 | issue=18 | pages=i409–i415 | doi=10.1093/bioinformatics/bts386 | pmc=3436813 }}</ref><ref name=lafond_efficient_2016>Lafond M and Noutahi E and El-Mabrouk N (2016) Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) 14:1--14:12</ref><ref name=Comte2019>{{Cite journal|pmid = 33085745| year=2020 | last1=Comte | first1=N. | last2=Morel | first2=B. | last3=Hasić | first3=D. | last4=Guéguen | first4=L. | last5=Boussau | first5=B. | last6=Daubin | first6=V. | last7=Penel | first7=S. | last8=Scornavacca | first8=C. | last9=Gouy | first9=M. | last10=Stamatakis | first10=A. | last11=Tannier | first11=E. | last12=Parsons | first12=D. P. | title=Treerecs: An integrated phylogenetic tool, from sequences to reconciliations | journal=Bioinformatics | volume=36 | issue=18 | pages=4822–4824 | doi=10.1093/bioinformatics/btaa615 | doi-access=free }}</ref><ref name=zheng_reconciliation_2012>{{cite arXiv | eprint=1201.3995 | last1=Zheng | first1=Yu | last2=Wu | first2=Taoyang | last3=Zhang | first3=Louxin | title=Reconciliation of Gene and Species Trees with Polytomies | year=2012 | class=q-bio.PE }}</ref> In DTL, the problem is [[NP-hardness|NP hard]].<ref name=kordi_complexity_2015>{{Cite journal|pmid = 28055898| year=2017 | last1=Kordi | first1=M. | last2=Bansal | first2=M. S. | title=On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=14 | issue=3 | pages=587–599 | doi=10.1109/TCBB.2015.2511761 | s2cid=4458502 }}</ref> Heuristics<ref name=lai_fast_2017>{{cite book | doi=10.1007/978-3-319-67979-2_16 | chapter=Fast Heuristics for Resolving Weakly Supported Branches Using Duplication, Transfers, and Losses | title=Comparative Genomics | series=Lecture Notes in Computer Science | year=2017 | last1=Lai | first1=Han | last2=Stolzer | first2=Maureen | last3=Durand | first3=Dannie | volume=10562 | pages=298–320 | isbn=978-3-319-67978-5 }}</ref> and exact fixed parameter tractable algorithms<ref name=kordi_complexity_2015/><ref name=jacox_resolution_2017>{{Cite journal|pmid = 28073758| year=2017 | last1=Jacox | first1=E. | last2=Weller | first2=M. | last3=Tannier | first3=E. | last4=Scornavacca | first4=C. | title=Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses | journal=Bioinformatics | volume=33 | issue=7 | pages=980–987 | doi=10.1093/bioinformatics/btw778 | doi-access=free }}</ref><ref name=kordi_exact_2019>{{Cite journal|pmid = 28622673| year=2019 | last1=Kordi | first1=M. | last2=Bansal | first2=M. S. | title=Exact Algorithms for Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=16 | issue=4 | pages=1077–1090 | doi=10.1109/TCBB.2017.2710342 | s2cid=54606569 | doi-access=free }}</ref> are possible solutions.

Another way to handle uncertainty in lower trees is to take as input a sample of alternative lower trees instead of a single one. For example, in the paper that gave reconciliation its name,<ref name=goodman_fitting_1979/> it was proposed to consider all most likely lower trees, and choose from these trees the best one according to their DL costs, a principle also used by TreeFix-DTL.<ref name=bansal_improved_2015>{{Cite journal|pmid = 25481006| year=2015 | last1=Bansal | first1=M. S. | last2=Wu | first2=Y. C. | last3=Alm | first3=E. J. | last4=Kellis | first4=M. | title=Improved gene tree error correction in the presence of horizontal gene transfer | journal=Bioinformatics | volume=31 | issue=8 | pages=1211–1218 | doi=10.1093/bioinformatics/btu806 | pmc=4393519 }}</ref>
The sample of lower trees can similarly reflect their likelihood according to the aligned sequences, as obtained from Bayesian [[Markov chain Monte Carlo]] methods as implemented for example in Phylobayes.<ref name=lartillot_bayesian_2004>{{Cite journal|pmid = 15014145| year=2004 | last1=Lartillot | first1=N. | last2=Philippe | first2=H. | title=A Bayesian mixture model for across-site heterogeneities in the amino-acid replacement process | journal=Molecular Biology and Evolution | volume=21 | issue=6 | pages=1095–1109 | doi=10.1093/molbev/msh112 | doi-access=free }}</ref> AngST,<ref name=david_rapid_2011/> ALE<ref name=szollosi_efficient_2013/> and ecceTERA<ref name=scornavacca_joint_2015/> use "amalgamation", an extension of the DTL dynamic programming that is able to efficiently traverse a set of alternative lower trees instead of a single tree.

A local search in the space of lower trees guided by a joint likelihood, on the one hand from multiple sequence alignments and on the other hand from reconciliation with the upper tree, is achieved in Phyldog with a DL model<ref name=boussau_genome-scale_2013>{{Cite journal|pmid = 23132911| year=2013 | last1=Boussau | first1=B. | last2=Szöllosi | first2=G. J. | last3=Duret | first3=L. | last4=Gouy | first4=M. | last5=Tannier | first5=E. | last6=Daubin | first6=V. | title=Genome-scale coestimation of species and gene trees | journal=Genome Research | volume=23 | issue=2 | pages=323–330 | doi=10.1101/gr.141978.112 | pmc=3561873 }}</ref> and in GeneRax with DTL.<ref name=morel_generax_2019/> In a DL model with sequence evolution and relaxed [[molecular clock]], the lower tree space can be explored with an MCMC.<ref name=akerborg_simultaneous_2009>{{Cite journal|pmid = 19299507| year=2009 | last1=Akerborg | first1=O. | last2=Sennblad | first2=B. | last3=Arvestad | first3=L. | last4=Lagergren | first4=J. | title=Simultaneous Bayesian gene tree reconstruction and reconciliation analysis | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=106 | issue=14 | pages=5714–5719 | doi=10.1073/pnas.0806251106 | pmc=2667006 | bibcode=2009PNAS..106.5714A | doi-access=free }}</ref> MowgliNNI<ref name=nguyen_reconciliation_2013>{{Cite journal|pmid = 23566548| year=2013 | last1=Nguyen | first1=T. H. | last2=Ranwez | first2=V. | last3=Pointet | first3=S. | last4=Chifolleau | first4=A. M. | last5=Doyon | first5=J. P. | last6=Berry | first6=V. | title=Reconciliation and local gene tree rearrangement can be of mutual profit | journal=Algorithms for Molecular Biology | volume=8 | issue=1 | page=12 | doi=10.1186/1748-7188-8-12 | pmc=3871789 | doi-access=free }}</ref> can modify the input gene tree at poorly supported nodes to increase DTL score, while TreeSolve resolves the multifurcations added by collapsing poorly supported nodes.<ref name=kordi_treesolve_2020>{{cite book | doi=10.1007/978-3-030-42266-0_10 | chapter=Tree ''Solve'': Rapid Error-Correction of Microbial Gene Trees | title=Algorithms for Computational Biology | series=Lecture Notes in Computer Science | year=2020 | last1=Kordi | first1=Misagh | last2=Bansal | first2=Mukul S. | volume=12099 | pages=125–139 | isbn=978-3-030-42265-3 | s2cid=210171366 }}</ref>

Finally, integrative models&mdash;mixing sequence evolution and reconciliation&mdash;can compute a joint likelihood via dynamic programming (for both reconciliation and gene sequences evolution),<ref name=szollosi_efficient_2013/> use Markov chain Monte Carlo to include molecular clock to estimate branch lengths, in a DL model<ref name=arvestad_bayesian_2003/> or with a relaxed molecular clock,<ref name=akerborg_simultaneous_2009/> and in a DTL model.<ref name=sjostrand_bayesian_2014>{{Cite journal|pmid = 24562812| year=2014 | last1=Sjöstrand | first1=J. | last2=Tofigh | first2=A. | last3=Daubin | first3=V. | last4=Arvestad | first4=L. | last5=Sennblad | first5=B. | last6=Lagergren | first6=J. | title=A Bayesian method for analyzing lateral gene transfer | journal=Systematic Biology | volume=63 | issue=3 | pages=409–420 | doi=10.1093/sysbio/syu007 | doi-access=free }}</ref> These models have been applied in gene/species frameworks, not yet in host/symbiont or biogeography contexts.

====Inferring upper trees using reconciliation====

Inferring an upper tree from a set of lower trees is a long-standing question related to the [[supertree]] problem.<ref name=warnow_supertree_2018>{{cite arXiv | eprint=1805.03530 | last1=Warnow | first1=Tandy | title=Supertree Construction: Opportunities and Challenges | year=2018 | class=q-bio.PE }}</ref> It is particularly interesting in the case of gene/species reconciliation where many (typically thousands of) gene trees are available from [[Lists of sequenced genomes|complete genome sequences]]. Supertree methods attempt to assemble a species tree based on sets of trees which may differ in terms of contemporary species sets and topology, but usually without consideration for the biological process explaining these differences. However, some supertree approaches are statistically consistent for the reconstruction of the species tree if the gene trees are simulated under a DL model. This means that if the number of input lower trees generated from the true upper tree via the DL model grows toward infinity, given that there are no additional errors, the output upper tree converges almost surely to the true one. This has been shown in the case of a [[quartet distance]],<ref name=legried_polynomial-time_2020>{{Cite journal|pmid = 33325781| year=2021 | last1=Legried | first1=B. | last2=Molloy | first2=E. K. | last3=Warnow | first3=T. | last4=Roch | first4=S. | title=Polynomial-Time Statistical Estimation of Species Trees Under Gene Duplication and Loss | journal=Journal of Computational Biology | volume=28 | issue=5 | pages=452–468 | doi=10.1089/cmb.2020.0424 }}</ref> and with a generalised [[Robinson-Foulds metric|Robinson Foulds]] multicopy distance,<ref name=molloy_fastmulrfs_2020>{{Cite journal|pmid = 32657396| year=2020 | last1=Molloy | first1=E. K. | last2=Warnow | first2=T. | title=FastMulRFS: Fast and accurate species tree estimation under generic gene duplication and loss models | journal=Bioinformatics | volume=36 | issue=Suppl_1 | pages=i57–i65 | doi=10.1093/bioinformatics/btaa444 | pmc=7355287 }}</ref><ref name=chaudhary_inferring_2013>{{Cite journal|pmid = 24180377| year=2013 | last1=Chaudhary | first1=R. | last2=Burleigh | first2=J. G. | last3=Fernández-Baca | first3=D. | title=Inferring species trees from incongruent multi-copy gene trees using the Robinson-Foulds distance | journal=Algorithms for Molecular Biology | volume=8 | issue=1 | page=28 | doi=10.1186/1748-7188-8-28 | pmc=3874668 | doi-access=free }}</ref> with better [[Time complexity|running time]] but assuming gene trees do not contain [[bipartite graph|bipartitions]] contradicting the species tree, which seems rare under a DL model.

[[File:Phylogenetic reconciliation inferring upper tree.svg|thumb|A reconciliation score can be used to help construct an upper tree]]

Reconciliation can also be used for the inference of upper trees. This is a computationally hard problem: already resolving polytomies in a non binary upper tree with a binary lower one&mdash;minimizing a DL reconciliation score&mdash;is NP-hard.<ref name=zheng_reconciliation_2012/> In particular, reconstructing the species tree giving the best DL cost for several gene trees is NP-hard and 2-approximable.<ref name=ma_gene_2000>Ma B and Li M and Zhang L (2000) From Gene Trees to Species Trees. SIAM J. Comput., may, 729–752 24</ref> It is called the Gene Duplication problem or more generally Gene Tree parsimony. The problem was seen as a way to detect [[paralogy]] to get better species tree reconstruction.<ref>{{cite journal |last1=Guigo |first1=Roderic |last2=Muchnik |first2=Ilya |last3=Smith |first3=Temple F. |title=Reconstruction of Ancient Molecular Phylogeny |journal=Molecular Phylogenetics and Evolution |date=1 October 1996 |volume=6 |issue=2 |pages=189–213 |doi=10.1006/mpev.1996.0071 |pmid=8899723 |language=en |issn=1055-7903|doi-access=free |bibcode=1996MolPE...6..189G }}</ref><ref>{{cite journal |last1=Page |first1=Roderic D. M. |title=Extracting Species Trees From Complex Gene Trees: Reconciled Trees And Vertebrate Phylogeny |journal=Molecular Phylogenetics and Evolution |date=1 January 2000 |volume=14 |issue=1 |pages=89–106 |doi=10.1006/mpev.1999.0676 |pmid=10631044 |bibcode=2000MolPE..14...89P |url=https://doi.org/10.1006/mpev.1999.0676 |access-date=17 December 2022 |language=en |issn=1055-7903}}</ref> It is NP-hard, with interesting results on the problem complexity<ref name=zheng_reconciliation_2012/><ref name=bansal_note_2011>{{Cite journal|pmid = 20733245 |year = 2011 |last1 = Bansal |first1 = M. S. |last2 = Shamir |first2 = R. |title = A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem |journal = IEEE/ACM Transactions on Computational Biology and Bioinformatics |volume = 8 |issue = 3 |pages = 848–850 |doi = 10.1109/TCBB.2010.74 |s2cid = 7086924 }}</ref> and the behaviour of the model with different input size, structure and ILS presence.<ref name=maddison_inferring_2006>{{Cite journal|pmid = 16507521| year=2006 | last1=Maddison | first1=W. P. | last2=Knowles | first2=L. L. | title=Inferring phylogeny despite incomplete lineage sorting | journal=Systematic Biology | volume=55 | issue=1 | pages=21–30 | doi=10.1080/10635150500354928 | s2cid=13453831 | doi-access=free }}</ref> Multiple solutions exists, with ILP<ref name=chang_ILP_2011>{{Cite journal|pmid = 21342543| year=2011 | last1=Chang | first1=W. C. | last2=Burleigh | first2=G. J. | last3=Fernández-Baca | first3=D. F. | last4=Eulenstein | first4=O. | title=An ILP solution for the gene duplication problem | journal=BMC Bioinformatics | volume=12 | issue=Suppl 1 | pages=S14 | doi=10.1186/1471-2105-12-S1-S14 | pmc=3044268 | doi-access=free }}</ref> or heuristics,<ref name=page_genetree_1998>{{Cite journal|pmid = 9918954| year=1998 | last1=Page | first1=R. D. | title=GeneTree: Comparing gene and species phylogenies using reconciled trees | journal=Bioinformatics | volume=14 | issue=9 | pages=819–820 | doi=10.1093/bioinformatics/14.9.819 | doi-access=free }}</ref><ref name=wehe_duptree_2008>{{Cite journal|pmid = 18474508| year=2008 | last1=Wehe | first1=A. | last2=Bansal | first2=M. S. | last3=Burleigh | first3=J. G. | last4=Eulenstein | first4=O. | title=DupTree: A program for large-scale phylogenetic analyses using gene tree parsimony | journal=Bioinformatics | volume=24 | issue=13 | pages=1540–1541 | doi=10.1093/bioinformatics/btn230 | doi-access=free }}</ref> and with the possibility of a deep coalescence score.<ref name=chaudhary_igtp_2010>{{Cite journal|pmid = 21092314| year=2010 | last1=Chaudhary | first1=R. | last2=Bansal | first2=M. S. | last3=Wehe | first3=A. | last4=Fernández-Baca | first4=D. | last5=Eulenstein | first5=O. | title=IGTP: A software package for large-scale gene tree parsimony analysis | journal=BMC Bioinformatics | volume=11 | page=574 | doi=10.1186/1471-2105-11-574 | pmc=3002902 | doi-access=free }}</ref>

ODTL<ref name=szollosi_phylogenetic_2012/> takes as input gene trees and searches a maximum likelihood species tree according to a DTL model, with a [[hill-climbing]] search. The approach produces a species tree with internal nodes ordered in time, ensuring a time compatibility for the scenarios of transfer among lower trees {link section|The problem of temporal feasibility}.

Addressing a more general problem, Phyldog<ref name=boussau_genome-scale_2013/> searches for the maximum likelihood species tree, gene trees and DL parameters from multiple family alignments via multiple rounds of local search. It thus performs the exploration of both upper and lower trees at the same time. MixTreEM<ref name=ullah_species_2015>{{Cite journal|pmid = 25963975| year=2015 | last1=Ullah | first1=I. | last2=Parviainen | first2=P. | last3=Lagergren | first3=J. | title=Species Tree Inference Using a Mixture Model | journal=Molecular Biology and Evolution | volume=32 | issue=9 | pages=2469–2482 | doi=10.1093/molbev/msv115 | doi-access=free }}</ref> presents a faster solution.

==Limits of the two-level DTL model==
===A limit to dynamic programming: non independent evolution of children lineages===

[[File:Phylogenetic reconciliation non independent lineage.svg|thumb|Events such as replacing transfer or gene conversion can not be modeled with independent children lineages.]]

The dynamic programming framework, like usual birth and death models, works under the hypothesis of independent evolution of children lineages in the lower tree. However, this hypothesis does not hold if the model is complemented with several other documented evolutionary events, such as horizontal transfer with replacement of a homologous gene in the recipient lineage, or [[gene conversion]]. Horizontal transfer with replacement is usually modeled by a rearrangement of the upper tree, called Subtree Prune and Regraft (SPR). Reconciling under SPR is NP-hard, even in dated trees, and [[fixed-parameter tractable]] regarding the output size.<ref name=bordewich_spr_2005>Bordewich W and Semple C (2005) On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance. Annals of Combinatoris 8: 409-423</ref><ref name=hasic_gene_2019>{{Cite journal|pmid = 30767052| year=2019 | last1=Hasić | first1=D. | last2=Tannier | first2=E. | title=Gene tree species tree reconciliation with gene conversion | journal=Journal of Mathematical Biology | volume=78 | issue=6 | pages=1981–2014 | doi=10.1007/s00285-019-01331-w | arxiv=1703.08950 | s2cid=8476555 }}</ref>

Another way to model and infer replacing horizontal transfers is through maximum [[agreement forest]], where branches are cut in the lower and upper trees in order to get two identical (or statistically indistinguishable<ref name=abby_detecting_2010>{{Cite journal|pmid = 20550700| year=2010 | last1=Abby | first1=S. S. | last2=Tannier | first2=E. | last3=Gouy | first3=M. | last4=Daubin | first4=V. | title=Detecting lateral gene transfers by statistical reconciliation of phylogenetic forests | journal=BMC Bioinformatics | volume=11 | page=324 | doi=10.1186/1471-2105-11-324 | pmc=2905365 | doi-access=free }}</ref>) upper and lower forests. The problem is NP-hard,<ref name=hein_complexity_1996>Hein J, Jiang T, Wang L, Zhang K (1996) On the complexity of comparing evolutionary trees. Discrete Applied Mathematics 71:153--169</ref> but several approximations have been proposed.<ref name=rodrigues_maximum_2007>{{cite journal |last1=Rodrigues |first1=Estela M. |last2=Sagot |first2=Marie-France |last3=Wakabayashi |first3=Yoshiko |title=The maximum agreement forest problem: Approximation algorithms and computational experiments |journal=Theoretical Computer Science |date=April 2007 |volume=374 |issue=1–3 |pages=91–110 |doi=10.1016/j.tcs.2006.12.011|doi-access= |s2cid=16479722 }}</ref>
Replacing transfers can be considered on top of the DL model.<ref name=kordi_inferring_nodate>Kordi M (2019) Inferring Microbial Gene Family Evolution Using Duplication-Transfer-Loss Reconciliation: Algorithms and Complexity. Doctoral Dissertations. 2101.</ref> In the same vein, gene conversion can be seen as a "replacing duplication". In this latter case, a polynomial algorithm which does not use dynamic programming and is an extension of the LCA method can find all optimal solutions, including gene conversions.<ref name=hasic_gene_2019/>

===Integrating population levels: failure to diverge and Incomplete Lineage Sorting===

In host/symbiont frameworks, a single symbiont species is sometimes associated to several host species. This means that while a speciation or diversification has been observed in the host, the populations are indistinguishable in the symbiont.
This is handled for example by additional polytomies in the symbiont tree, possibly leading to [[Computational complexity theory#Intractability|intractable]] inference problems, because polytomies need to be resolved.
It is also modeled by an additional evolutionary event "failure to diverge" (Jane,<ref name=conow_jane_2010/> Amocoala<ref name=urbini_thesis_2017>Urbini L (2017) Models and algorithms to study the common evolutionary history of hosts and symbionts. Doctoral thesis, Université de Lyon</ref>).
Failure to diverge can be a way to allow "free" [[host switch]] in a population, a flow of symbionts between closely related hosts.
Following that vision, host switch allowed only for close hosts is considered in Eucalypt.<ref name=donati_eucalypt_2015/> This idea of horizontal flow between close populations can also be applied to gene/species frameworks, with a definition of species based on a gradient of gene flow between populations.<ref name=marin_genomic_2019>{{Cite journal|pmid = 32654283| year=2020 | last1=Marin | first1=J. | last2=Achaz | first2=G. | last3=Crombach | first3=A. | last4=Lambert | first4=A. | title=The genomic view of diversification | journal=Journal of Evolutionary Biology | volume=33 | issue=10 | pages=1387–1404 | doi=10.1111/jeb.13677 | s2cid=91543153 }}</ref>

[[File:Phylogenetic reconciliation ftd ils.svg|thumb|upright=2.0|Failure to diverge and Incomplete Lineage Sorting are two population level events resulting in a particular reconciliation pattern.]]

Failure to diverge is one way of introducing [[population dynamics]] in reconciliation, a framework mainly adapted to the multi-species level, where populations are supposed to be well differentiated. There are other population phenomena that limit this framework, one of them being [[Coalescent theory|deep coalescence]] of lineages, leading to [[Incomplete Lineage Sorting]] (ILS), which is not handled by the DTL model.<ref name=stolzer_inferring_2012/><ref name=szollosi_inference_2015>{{Cite journal|pmid = 25070970| year=2015 | last1=Szöllősi | first1=G. J. | last2=Tannier | first2=E. | last3=Daubin | first3=V. | last4=Boussau | first4=B. | title=The inference of gene trees with species trees | journal=Systematic Biology | volume=64 | issue=1 | pages=e42-62 | doi=10.1093/sysbio/syu048 | pmc=4265139 }}</ref> The multi species coalescent is a classical model of [[allele]] evolution along a species tree, with birth of alleles
and sorting of alleles at speciations, that takes into account population sizes and naturally encompasses ILS.<ref name=rannala_bayes_2003>{{Cite journal|pmid = 12930768| year=2003 | last1=Rannala | first1=B. | last2=Yang | first2=Z. | title=Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci | journal=Genetics | volume=164 | issue=4 | pages=1645–1656 | doi=10.1093/genetics/164.4.1645 | pmc=1462670 }}</ref><ref name=degnan_gene_2005>{{Cite journal|pmid = 15792224| year=2005 | last1=Degnan | first1=J. H. | last2=Salter | first2=L. A. | title=Gene tree distributions under the coalescent process | journal=Evolution; International Journal of Organic Evolution | volume=59 | issue=1 | pages=24–37 | doi=10.1111/j.0014-3820.2005.tb00891.x }}</ref><ref name=maddison_inferring_2006/><ref name=liu_species_2007>{{Cite journal|pmid = 17562474| year=2007 | last1=Liu | first1=L. | last2=Pearl | first2=D. K. | title=Species trees from gene trees: Reconstructing Bayesian posterior distributions of a species phylogeny using estimated gene tree distributions | journal=Systematic Biology | volume=56 | issue=3 | pages=504–514 | doi=10.1080/10635150701429982 | doi-access=free }}</ref><ref name=rannala_multi_2020>Rannala B and Edwards S and Leaché A and Yang Z (2020) Phylogenetics in the Genomic Era, 3.3:1--3.3:21</ref> 
In a reconciliation context, several attempts have been made in order to account for ILS without the complex integration of a population model. For example, ILS can be seen as a possible evolutionary pattern for the gene tree. In that case, children lineages are not independent of one another, leading to intractability results. ILS alone can be handled with LCA, but ILS + DL reconciliation is NP hard, even without transfers.<ref name=bork_computational_2017>{{Cite journal|pmid = 28316640| year=2017 | last1=Bork | first1=D. | last2=Cheng | first2=R. | last3=Wang | first3=J. | last4=Sung | first4=J. | last5=Libeskind-Hadas | first5=R. | title=On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model | journal=Algorithms for Molecular Biology | volume=12 | page=6 | doi=10.1186/s13015-017-0098-8 | pmc=5349084 | doi-access=free }}</ref>

Notung<ref name=stolzer_inferring_2012/> handles ILS by collapsing short branches of the species tree in polytomies and allowing ILS as a free diversification of gene trees on those polytomies. ecceTERA<ref name=chan_inferring_2017>{{Cite journal|pmid = 28801222| year=2017 | last1=Chan | first1=Y. B. | last2=Ranwez | first2=V. | last3=Scornavacca | first3=C. | title=Inferring incomplete lineage sorting, duplications, transfers and losses with reconciliations | journal=Journal of Theoretical Biology | volume=432 | pages=1–13 | doi=10.1016/j.jtbi.2017.08.008 | bibcode=2017JThBi.432....1C | s2cid=7854827 | url=https://hal.archives-ouvertes.fr/hal-02154862/file/Scornavacca_20.pdf }}</ref> binds the maximum size of connected parts of the species tree where ILS can happen, proposing a fixed parameter tractable algorithm in that parameter.

ILS and DL can be considered on an upper [[Phylogenetic network|network]] instead of a tree. This models in particular introgression, with the possibility to estimate model parameters.<ref name=du_unifying_2019>Du P and Ogilvie H A and Nakhleh L (2019) Unifying Gene Duplication, Loss, and Coalescence on Phylogenetic Networks. Bioinformatics Research and Applications. ISBRA 2019. Lecture Notes in Computer Science, vol 11490. Springer, Cham.</ref>

More integrative reconciliation models accounting for ILS have been proposed, including both DL and multispecies coalescent,<ref name=rasmussen_unified_2012>{{Cite journal|pmid = 22271778| year=2012 | last1=Rasmussen | first1=M. D. | last2=Kellis | first2=M. | title=Unified modeling of gene duplication, loss, and coalescence using a locus tree | journal=Genome Research | volume=22 | issue=4 | pages=755–765 | doi=10.1101/gr.123901.111 | pmc=3317157 }}</ref> with DLCoal. It is a probabilistic model with a parsimony translation,<ref name=wu_most_2013>{{Cite journal|pmid = 24310000| year=2014 | last1=Wu | first1=Y. C. | last2=Rasmussen | first2=M. D. | last3=Bansal | first3=M. S. | last4=Kellis | first4=M. | title=Most parsimonious reconciliation in the presence of gene duplication, loss, and deep coalescence using labeled coalescent trees | journal=Genome Research | volume=24 | issue=3 | pages=475–486 | doi=10.1101/gr.161968.113 | pmc=3941112 }}</ref> proposing two sequential LCA-type heuristics handled via an intermediate locus tree between gene and species.
However, outside of the gene/species reconciliation framework, ILS seems, for no particular reason, never considered in host/symbiont, nor in biogeography.

==Cophylogeny with more than two levels==
[[File:Three level phylogenetic reconciliation summary.svg|thumb|Illustration of input, output and events, of published methods which can be identified with 3-level methods.<ref name=Three-level-phylogenetic-reconciliation-summary>This table is intended to serve as illustration to the 3-Level reconciliation section of Menet et al. (2022) Phylogenetic reconciliation. PLoS Comput Biol 18(11): e1010621.[[:doi:10.1371/journal.pcbi.1010621]] and can be read along with it. Colors correspond to the different levels (similar but different colors if there are several trees at the same level). The legend gives an example of all these colours and shape codes. Multiple gene lineages can undergo joint events like whole genome duplication (A) or segmental events (B), some events might be more probable than others, like specific horizontal transfers with highway of transfers or hybridization (C). Cophylogenetic patterns can be compared, to see for instance if the common pattern of a host and a symbiont are not just the common pattern of the symbiont and the geography (D). Characters can evolve on reconciled phylogeny, like gene synteny (E), or two levels can be reconciled with the constraint of an upper one (F). Transfers can be upper dependent, which is more likely between two intermediate entities that belong to a same upper one (G). Three levels can be reconciled together, sequentially: the intermediate and the upper before adding the lower, or trying to find a joint most parsimonious scenario for the two reconciliations (H). These multi-level models can also be used to reconstruct an intermediate phylogeny (I).</ref>]]
A striking aspect of reconciliation is the common methodology handling different levels of organization: it is used for comparing domain and protein trees, gene and species trees, hosts and symbiont trees, population and geographic trees. However, now that scientists tend to consider that multi-level models of biological functioning bring a novel and game changing view of organisms and their environment,<ref name=ref_holobionte>{{Cite journal|pmid = 27822520| year=2016 | last1=Theis | first1=K. R. | last2=Dheilly | first2=N. M. | last3=Klassen | first3=J. L. | last4=Brucker | first4=R. M. | last5=Baines | first5=J. F. | last6=Bosch | first6=T. C. | last7=Cryan | first7=J. F. | last8=Gilbert | first8=S. F. | last9=Goodnight | first9=C. J. | last10=Lloyd | first10=E. A. | last11=Sapp | first11=J. | last12=Vandenkoornhuyse | first12=P. | last13=Zilber-Rosenberg | first13=I. | last14=Rosenberg | first14=E. | last15=Bordenstein | first15=S. R. | title=Getting the Hologenome Concept Right: An Eco-Evolutionary Framework for Hosts and Their Microbiomes | journal=mSystems | volume=1 | issue=2 | doi=10.1128/mSystems.00028-16 | pmc=5069740 }}</ref> the question is how to use reconciliation to bring phylogenetics to this holobiont era.

Coevolution of entities at different scales of evolution is at the basis of the holobiont idea: macro-organisms, micro-organisms and their genes all have a different history bound to a common functioning in a single ecosystem. Biological systems like the entanglement of host, symbionts and their genes imply functional and evolutionary dependencies between more than two levels.

===Examples of multi level systems with complex evolutionary inter-dependencies===
====Genes coevolving beyond genome boundaries====
The holobiont concept<ref name=margulis_symbiosis_1991>{{cite book |last1=Margulis |first1=L. S. |last2=Fester |first2=R. |title=Symbiosis as a Source of Evolutionary Innovation: Speciation and Morphogenesis |date=1991 |publisher=MIT Press |location=Cambridge, Mass. |isbn=9780262132695}}</ref> stresses the possibility of genes from different genomes to cooperate and coevolve.<ref name=bordenstein_host_2015>{{Cite journal|pmid = 26284777| year=2015 | last1=Bordenstein | first1=S. R. | last2=Theis | first2=K. R. | title=Host Biology in Light of the Microbiome: Ten Principles of Holobionts and Hologenomes | journal=PLOS Biology | volume=13 | issue=8 | pages=e1002226 | doi=10.1371/journal.pbio.1002226 | pmc=4540581 | doi-access=free }}</ref><ref name=rosenberg_role_2007>{{Cite journal|pmid = 17384666| year=2007 | last1=Rosenberg | first1=E. | last2=Koren | first2=O. | last3=Reshef | first3=L. | last4=Efrony | first4=R. | last5=Zilber-Rosenberg | first5=I. | title=The role of microorganisms in coral health, disease and evolution | journal=Nature Reviews. Microbiology | volume=5 | issue=5 | pages=355–362 | doi=10.1038/nrmicro1635 | s2cid=2967190 }}</ref><ref name=rosenberg_role_2008>{{Cite journal|pmid = 18549407| year=2008 | last1=Zilber-Rosenberg | first1=I. | last2=Rosenberg | first2=E. | title=Role of microorganisms in the evolution of animals and plants: The hologenome theory of evolution | journal=FEMS Microbiology Reviews | volume=32 | issue=5 | pages=723–735 | doi=10.1111/j.1574-6976.2008.00123.x | doi-access=free }}</ref> For instance, certain genes in a symbiont genome may provide a function to its host, like the production of a vital compound absent from available feeding sources. An iconic example is the case for blood-feeding or sap-feeding insects, which often depend on one or several bacterial symbionts to thrive on a resource that is abundant in sugar, but lacks essential amino-acids or vitamins.<ref name=moran_genomics_2008>{{Cite journal|pmid = 18983256| year=2008 | last1=Moran | first1=N. A. | last2=McCutcheon | first2=J. P. | last3=Nakabachi | first3=A. | title=Genomics and evolution of heritable bacterial symbionts | journal=Annual Review of Genetics | volume=42 | pages=165–190 | doi=10.1146/annurev.genet.41.110306.130119 }}</ref> Another example is the association of [[Fabaceae]] with [[Fabaceae#Biological nitrogen fixation|nitrogen-fixing bacteria]]. The compound beneficiary to the host is typically produced by a set of genes encoded in the symbiont genome, which throughout evolution, may be transferred to other symbionts, and/or in and out of the host genome. Reconciliation methods have the potential to reveal evolutionary links between portions of genomes from different species. A search for coevolving genes beyond the boundaries of the genomes in which they are encoded would highlight the basis for the association of organisms in the holobiont.

====Horizontal gene transfer routes depend on multiple levels====
In [[endosymbiont|intracellular mutualistic symbiont]] insect systems, multiple occurrences of horizontal gene transfers have been identified, whether from host to symbiont, symbiont to host or symbiont to symbiont.<ref name=lopez-madrigal_et_2017>{{Cite journal|pmid = 28961177| year=2017 | last1=López-Madrigal | first1=S. | last2=Gil | first2=R. | title=Et tu, Brute? Not Even Intracellular Mutualistic Symbionts Escape Horizontal Gene Transfer | journal=Genes | volume=8 | issue=10 | page=247 | doi=10.3390/genes8100247 | pmc=5664097 | doi-access=free }}</ref>

Transfers of endosymbiont genes involved in nutrition [[metabolic pathway|pathways]] beneficiary to the insect host have been shown to occur preferentially if the donor and recipient lineages share the same host.<ref name=penz_comparative_2012>{{Cite journal|pmid = 23133394| year=2012 | last1=Penz | first1=T. | last2=Schmitz-Esser | first2=S. | last3=Kelly | first3=S. E. | last4=Cass | first4=B. N. | last5=Müller | first5=A. | last6=Woyke | first6=T. | last7=Malfatti | first7=S. A. | last8=Hunter | first8=M. S. | last9=Horn | first9=M. | title=Comparative genomics suggests an independent origin of cytoplasmic incompatibility in Cardinium hertigii | journal=PLOS Genetics | volume=8 | issue=10 | pages=e1003012 | doi=10.1371/journal.pgen.1003012 | pmc=3486910 | doi-access=free }}</ref><ref name=nikoh_evolutionary_2014>{{Cite journal|pmid = 24982177| year=2014 | last1=Nikoh | first1=N. | last2=Hosokawa | first2=T. | last3=Moriyama | first3=M. | last4=Oshima | first4=K. | last5=Hattori | first5=M. | last6=Fukatsu | first6=T. | title=Evolutionary origin of insect-Wolbachia nutritional mutualism | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=111 | issue=28 | pages=10257–10262 | doi=10.1073/pnas.1409284111 | pmc=4104916 | bibcode=2014PNAS..11110257N | doi-access=free }}</ref><ref name=manzano-marin_serial_2019>{{Cite journal|pmid = 31624345| year=2020 | last1=Manzano-Marı n | first1=A. | last2=Coeur d'Acier | first2=A. | last3=Clamens | first3=A. L. | last4=Orvain | first4=C. | last5=Cruaud | first5=C. | last6=Barbe | first6=V. | last7=Jousselin | first7=E. | title=Serial horizontal transfer of vitamin-biosynthetic genes enables the establishment of new nutritional symbionts in aphids' di-symbiotic systems | journal=The ISME Journal | volume=14 | issue=1 | pages=259–273 | doi=10.1038/s41396-019-0533-6 | pmc=6908640 | bibcode=2020ISMEJ..14..259M }}</ref> This is also the case in insects with bacterial symbionts providing defensive protein<ref name=nakabachi_defensive_2013>{{Cite journal|pmid = 23850282| year=2013 | last1=Nakabachi | first1=A. | last2=Ueoka | first2=R. | last3=Oshima | first3=K. | last4=Teta | first4=R. | last5=Mangoni | first5=A. | last6=Gurgui | first6=M. | last7=Oldham | first7=N. J. | last8=Van Echten-Deckert | first8=G. | last9=Okamura | first9=K. | last10=Yamamoto | first10=K. | last11=Inoue | first11=H. | last12=Ohkuma | first12=M. | last13=Hongoh | first13=Y. | last14=Miyagishima | first14=S. Y. | last15=Hattori | first15=M. | last16=Piel | first16=J. | last17=Fukatsu | first17=T. | title=Defensive bacteriome symbiont with a drastically reduced genome | journal=Current Biology | volume=23 | issue=15 | pages=1478–1484 | doi=10.1016/j.cub.2013.06.027 | s2cid=1637956 | doi-access=free | bibcode=2013CBio...23.1478N }}</ref> or in obligate leaf nodule bacterial symbionts associated with plants.<ref name=pinto-carbo_evidence_2016>{{Cite journal|pmid = 26978165| year=2016 | last1=Pinto-Carbó | first1=M. | last2=Sieber | first2=S. | last3=Dessein | first3=S. | last4=Wicker | first4=T. | last5=Verstraete | first5=B. | last6=Gademann | first6=K. | last7=Eberl | first7=L. | last8=Carlier | first8=A. | title=Evidence of horizontal gene transfer between obligate leaf nodule symbionts | journal=The ISME Journal | volume=10 | issue=9 | pages=2092–2105 | doi=10.1038/ismej.2016.27 | pmc=4989318 | bibcode=2016ISMEJ..10.2092P }}</ref> In the human host, gene transfer has been shown to occur preferentially among symbionts hosted in the same organs.<ref name=jeong_horizontal_2019>{{Cite journal|pmid = 30976019| year=2019 | last1=Jeong | first1=H. | last2=Arif | first2=B. | last3=Caetano-Anollés | first3=G. | last4=Kim | first4=K. M. | last5=Nasir | first5=A. | title=Horizontal gene transfer in human-associated microorganisms inferred by phylogenetic reconstruction and reconciliation | journal=Scientific Reports | volume=9 | issue=1 | page=5953 | doi=10.1038/s41598-019-42227-5 | pmc=6459891 | bibcode=2019NatSR...9.5953J }}</ref>

A review of horizontal gene transfers in host/symbiont systems<ref name=wijayawardena_hosts_2013>{{Cite journal|pmid = 23759418| year=2013 | last1=Wijayawardena | first1=B. K. | last2=Minchella | first2=D. J. | last3=Dewoody | first3=J. A. | title=Hosts, parasites, and horizontal gene transfer | journal=Trends in Parasitology | volume=29 | issue=7 | pages=329–338 | doi=10.1016/j.pt.2013.05.001 }}</ref> stresses the importance of supporting HGTs with multiple evidence. Notably it is argued that transfers should be considered better supported when involving symbionts sharing a habitat, a geographical area, or the same host. One should, however, keep in mind that most of the diversity of hosts and symbionts is unknown and that transfers may have occurred in unsampled closely related species, hosts or symbionts.

The idea that gene transfer in symbionts is constrained by the host can also be used to investigate the host's phylogenetic history. For instance, based on phylogeographical studies, it is now accepted that the bacterium ''[[Helicobacter pylori]]'' has been associated with human populations since the [[Human evolution|origins of the human species]].<ref name=moodley_age_2012>{{Cite journal|pmid = 22589724| year=2012 | last1=Moodley | first1=Y. | last2=Linz | first2=B. | last3=Bond | first3=R. P. | last4=Nieuwoudt | first4=M. | last5=Soodyall | first5=H. | last6=Schlebusch | first6=C. M. | last7=Bernhöft | first7=S. | last8=Hale | first8=J. | last9=Suerbaum | first9=S. | last10=Mugisha | first10=L. | last11=Van Der Merwe | first11=S. W. | last12=Achtman | first12=M. | title=Age of the association between Helicobacter pylori and man | journal=PLOS Pathogens | volume=8 | issue=5 | pages=e1002693 | doi=10.1371/journal.ppat.1002693 | pmc=3349757 | doi-access=free }}</ref><ref name=achtman_how_2016>{{Cite journal|pmid = 27534956| year=2016 | last1=Achtman | first1=M. | title=How old are bacterial pathogens? | journal=Proceedings. Biological Sciences | volume=283 | issue=1836 | doi=10.1098/rspb.2016.0990 | pmc=5013766 }}</ref> An analysis of the genomes of ''Helicobacter pylori'' in Europe suggests that they are issued from a recombination between African and Asian ''Helicobacter pylori''. This strongly implies early contacts between the corresponding human populations.

Similarly, an analysis of HGTs in coronaviruses from different mammalian species using reconciliation methods has revealed frequent contact between viral lineages, which can be interpreted as frequent host switches.<ref name=fu_comprehensive_2020>{{cite bioRxiv | biorxiv =10.1101/2020.08.11.232520 | title=A Comprehensive Classification of Coronaviruses and Inferred Cross-Host Transmissions | year=2020 | last1=Fu | first1=Yiran | last2=Pistolozzi | first2=Marco | last3=Yang | first3=Xiaofeng | last4=Lin | first4=Zhanglin}}</ref>

====Cultural evolution====
The evolution of elements of [[human culture]], for instance [[language]]s and [[Folklore|folktale]]s, in association with human [[population genetics]], has been studied using concepts from phylogenetics. Although reconciliation has never been used in this framework, some of these studies encompass multiple levels of organization, each represented by a tree or the evolution of a character, with a focus on the coevolution of these levels.

Language trees can be compared with population trees in order to reveal vertically transmitted folktales, via a character model on this language tree.<ref name=da_silva_comparative_2015>{{Cite journal|pmid = 26909191| year=2016 | last1=Da Silva | first1=S. G. | last2=Tehrani | first2=J. J. | title=Comparative phylogenetic analyses uncover the ancient roots of Indo-European folktales | journal=Royal Society Open Science | volume=3 | issue=1 | page=150645 | doi=10.1098/rsos.150645 | pmc=4736946 | bibcode=2016RSOS....350645D }}</ref> Variants in each folktale's family, languages, genetic diversity, populations and geography can be compared two by two, to link folktale diversification with languages on one side and with geography on the other side.<ref name=ross_population_2013>{{Cite journal|pmid = 23390109| year=2013 | last1=Ross | first1=R. M. | last2=Greenhill | first2=S. J. | last3=Atkinson | first3=Q. D. | title=Population structure and cultural geography of a folktale in Europe | journal=Proceedings. Biological Sciences | volume=280 | issue=1756 | doi=10.1098/rspb.2012.3065 | pmc=3574383 }}</ref> As in genetics with symbionts sharing host promoting HGTs, linguistic barriers can foreclose the transmission of folktales or language elements.<ref name=bortolini_inferring_2017>{{Cite journal|pmid = 28784786| year=2017 | last1=Bortolini | first1=E. | last2=Pagani | first2=L. | last3=Crema | first3=E. R. | last4=Sarno | first4=S. | last5=Barbieri | first5=C. | last6=Boattini | first6=A. | last7=Sazzini | first7=M. | last8=Da Silva | first8=S. G. | last9=Martini | first9=G. | last10=Metspalu | first10=M. | last11=Pettener | first11=D. | last12=Luiselli | first12=D. | last13=Tehrani | first13=J. J. | title=Inferring patterns of folktale diffusion using genomic data | journal=Proceedings of the National Academy of Sciences of the United States of America | volume=114 | issue=34 | pages=9140–9145 | doi=10.1073/pnas.1614395114 | pmc=5576778 | bibcode=2017PNAS..114.9140B | doi-access=free }}</ref>

===Investigating three-level systems using two-level reconciliation===
Multi level reconciliation is not as developed as two-level reconciliation. One way to approach the evolutionary dependencies between more than two levels of organization is to try to use available standard two-level methods to give a first insight into a biological system's complexity.

<gallery class="center">
File:Phylogenetic reconciliation segmental events.svg|Multiple gene lineages can undergo joint events like segmental duplication, transfer or loss, or even whole genome duplication.
File:Phylogenetic reconciliation network.svg|Reconciliation can help identify highways of transfers and hybridizations.
File:Phylogenetic reconciliation coupled reconciliations.svg|Three levels can be reconciled together, sequentially: the intermediate in the upper before adding the lower, or trying to find a joint most parsimonious scenario for the two reconciliations.
File:Phylogenetic reconciliation multilevel comparison.svg|With more than two levels, the reconciliation of the lower and intermediate levels can be compared to the reconciliation of the lower and upper.
</gallery>

====Multi-gene events: implicit consideration of an intermediate level====

At the gene/species tree level, one typically deals with many different gene trees. In this case, the hypothesis that different gene families evolve independently is made implicitly. However, this does not need to be the case. For instance, duplication, transfer and loss can occur for segments of a genome spanning an arbitrary number of contiguous genes. It is possible to consider such multi-gene events using an intermediate guide for lower trees inside the upper one. For instance, one can compute the joint likelihood of multiple gene tree reconciliations with a dated species tree with duplication, loss and whole genome duplication<ref name=zwaenepoel_ancient_2019/> or in a parsimonious setting,<ref name=guigo_reconstruction_1996 >{{Cite journal|pmid = 8899723| year=1996 | last1=Guigó | first1=R. | last2=Muchnik | first2=I. | last3=Smith | first3=T. F. | title=Reconstruction of ancient molecular phylogeny | journal=Molecular Phylogenetics and Evolution | volume=6 | issue=2 | pages=189–213 | doi=10.1006/mpev.1996.0071 | doi-access=free | bibcode=1996MolPE...6..189G }}</ref><ref name=page_vertebrate_2001>{{Cite journal|pmid =  11928506| year=2002 | last1=Page | first1=R. D. | last2=Cotton | first2=J. A. | title=Vertebrate phylogenomics: Reconciled trees and gene duplications | journal=Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing | pages=536–547 | doi=10.1142/9789812799623_0050 | isbn=978-981-02-4777-5 | s2cid=5638166 }}</ref><ref name=burleigh_locating_2009>{{cite journal | doi=10.1089/cmb.2009.0139 | title=Locating Large-Scale Gene Duplication Events through Reconciled Trees: Implications for Identifying Ancient Polyploidy Events in Plants | year=2009 | last1=Burleigh | first1=J.G. | last2=Bansal | first2=M.S. | last3=Wehe | first3=A. | last4=Eulenstein | first4=O. | journal=Journal of Computational Biology | volume=16 | issue=8 | pages=1071–1083 | pmid=19689214 }}</ref><ref name=bansal_multiple_2008>{{Cite journal|pmid =  18586705| year=2008 | last1=Bansal | first1=M. S. | last2=Eulenstein | first2=O. | title=The multiple gene duplication problem revisited | journal=Bioinformatics | volume=24 | issue=13 | pages=i132-8 | doi=10.1093/bioinformatics/btn150 | pmc=2718628 }}</ref> and one definition of the problem is NP-hard.<ref name=fellows_multiple_1998>Michael R. Fellows, Michael T. Hallet, and Ulrike Stege. 1998. On the Multiple Gene Duplication Problem. In Proceedings of the 9th International Symposium on Algorithms and Computation (ISAAC '98). Springer-Verlag, Berlin, Heidelberg, 347–356.</ref> Similarly, the DL framework can be enriched with duplication and loss of chromosome segments instead of a single gene. However, DL reconciliation becomes intractable with that new possibility.<ref name=dondi_reconciling_2019>{{Cite journal|pmid = 30930955| year=2019 | last1=Dondi | first1=R. | last2=Lafond | first2=M. | last3=Scornavacca | first3=C. | title=Reconciling multiple genes trees via segmental duplications and losses | journal=Algorithms for Molecular Biology | volume=14 | page=7 | doi=10.1186/s13015-019-0139-6 | pmc=6425616 | doi-access=free }}</ref>

The link between two consecutive genes can also be modeled as an evolving character, subject to gain, loss, origination, breakage, duplication and transfer.<ref name=duchemin_decostar:_2017/> The evolution of this link appears as an additional level to species and gene trees, partly constrained by the gene/species tree reconciliation, partly evolving on its own, according to genome organization. It thus models the [[synteny]], or proximity between genes. At another scale, it can as well model the evolution of two domains belonging to a protein.

The detection of "highways of transfers", the preferential acquisition of groups of genes from a specific donor, is another example of non-independence of gene histories.<ref name=bansal_detecting_2011>{{Cite journal|pmid = 21899418| year=2011 | last1=Bansal | first1=M. S. | last2=Banay | first2=G. | last3=Gogarten | first3=J. P. | last4=Shamir | first4=R. | title=Detecting highways of horizontal gene transfer | journal=Journal of Computational Biology | volume=18 | issue=9 | pages=1087–1114 | doi=10.1089/cmb.2011.0066 | hdl=1721.1/69855 | hdl-access=free }}</ref> Similarly, multi-gene transfers can be detected.<ref name=kloub_systematic_2021>{{Cite journal|pmid = 33565580| year=2021 | last1=Kloub | first1=L. | last2=Gosselin | first2=S. | last3=Fullmer | first3=M. | last4=Graf | first4=J. | last5=Gogarten | first5=J. P. | last6=Bansal | first6=M. S. | title=Systematic Detection of Large-Scale Multigene Horizontal Transfer in Prokaryotes | journal=Molecular Biology and Evolution | volume=38 | issue=6 | pages=2639–2659 | doi=10.1093/molbev/msab043 | pmc=8136488 }}</ref> It has also led to methodological developments such as reconciliations using [[phylogenetic network]]s, seen as a tree augmented with transfer edges, which can be used to constrain transfers in a DTL model.<ref name=scornavacca_fast_2017>{{Cite journal|pmid = 28111320| year=2017 | last1=Scornavacca | first1=C. | author2=Mayol JCP | last3=Cardona | first3=G. | title=Fast algorithm for the reconciliation of gene trees and LGT networks | journal=Journal of Theoretical Biology | volume=418 | pages=129–137 | doi=10.1016/j.jtbi.2017.01.024 | bibcode=2017JThBi.418..129S | s2cid=37447907 | url=https://hal.archives-ouvertes.fr/hal-02154890/file/Scornavacca_27.pdf }}</ref> Networks can also be used to model [[introgression]] and [[incomplete lineage sorting]].<ref name=yu_fast_2012>{{Cite journal|pmid = 24564257| year=2013 | last1=Yu | first1=Y. | last2=Ristic | first2=N. | last3=Nakhleh | first3=L. | title=Fast algorithms and heuristics for phylogenomics under ILS and hybridization | journal=BMC Bioinformatics | volume=14 | issue=Suppl 15 | pages=S6 | doi=10.1186/1471-2105-14-S15-S6 | pmc=3852049 | doi-access=free }}</ref><ref name=yu_parsimonious_2013>{{Cite journal|pmid = 23736104| year=2013 | last1=Yu | first1=Y. | last2=Barnett | first2=R. M. | last3=Nakhleh | first3=L. | title=Parsimonious inference of hybridization in the presence of incomplete lineage sorting | journal=Systematic Biology | volume=62 | issue=5 | pages=738–751 | doi=10.1093/sysbio/syt037 | pmc=3739885 }}</ref><ref name=yu_maximum_2014/>

====Detecting coevolution in multiple pairs of levels====

It is a central question to understand the evolution of a holobiont to know what the levels are that coevolve with each other, for instance between host species, host genes, symbionts and symbiont genes. It is possible to approach the multiple inter-dependencies between all levels of evolution by multiple pairwise comparisons of two evolving entities.

Reconciliation of host and symbiont on one side and geography and symbiont on the other can also help to identify patterns of diversification of host and symbiont that reflect either coevolution or patterns that can be explained by a common geographical diversification.<ref name=nieberding_use_2010>{{Cite journal|pmid = 18346916| year=2008 | last1=Nieberding | first1=C. M. | last2=Durette-Desset | first2=M. C. | last3=Vanderpoorten | first3=A. | last4=Casanova | first4=J. C. | last5=Ribas | first5=A. | last6=Deffontaine | first6=V. | last7=Feliu | first7=C. | last8=Morand | first8=S. | last9=Libois | first9=R. | last10=Michaux | first10=J. R. | title=Geography and host biogeography matter for understanding the phylogeography of a parasite | journal=Molecular Phylogenetics and Evolution | volume=47 | issue=2 | pages=538–554 | doi=10.1016/j.ympev.2008.01.028 | bibcode=2008MolPE..47..538N | hdl=2268/9909 | hdl-access=free }}</ref><ref name=martinez-aquino_historical_2014>{{Cite journal|pmid = 24999998| year=2014 | last1=Martínez-Aquino | first1=A. | last2=Ceccarelli | first2=F. S. | last3=Eguiarte | first3=L. E. | last4=Vázquez-Domínguez | first4=E. | last5=De León | first5=G. P. | title=Do the historical biogeography and evolutionary history of the digenean Margotrema SPP. Across central Mexico mirror those of their freshwater fish hosts (Goodeinae)? | journal=PLOS ONE | volume=9 | issue=7 | pages=e101700 | doi=10.1371/journal.pone.0101700 | pmc=4084993 | bibcode=2014PLoSO...9j1700M | doi-access=free }}</ref><ref name=weckstein_biogeography_2004>{{Cite journal|pmid = 14965910| year=2004 | last1=Weckstein | first1=J. D. | title=Biogeography explains cophylogenetic patterns in toucan chewing lice | journal=Systematic Biology | volume=53 | issue=1 | pages=154–164 | doi=10.1080/10635150490265085 | doi-access=free }}</ref><ref name=fountain_cophylogenetics_2017>{{Cite journal|pmid = 28288943| year=2017 | last1=Fountain | first1=E. D. | last2=Pauli | first2=J. N. | last3=Mendoza | first3=J. E. | last4=Carlson | first4=J. | last5=Peery | first5=M. Z. | title=Cophylogenetics and biogeography reveal a coevolved relationship between sloths and their symbiont algae | journal=Molecular Phylogenetics and Evolution | volume=110 | pages=73–80 | doi=10.1016/j.ympev.2017.03.003 | doi-access=free | bibcode=2017MolPE.110...73F }}</ref>
Similarly, a study used reconciliation methods to differentiate the effect of diet evolution and [[phylogenetic inertia]] on the composition of mammalian [[Gut microbiota|gut microbiomes]]. By reconstructing ancestral diets and microbiome composition onto a mammalian phylogeny, the study revealed that both effects contribute but at different time scales.<ref name=groussin_unraveling_2017>{{Cite journal|pmid = 28230052| year=2017 | last1=Groussin | first1=M. | last2=Mazel | first2=F. | last3=Sanders | first3=J. G. | last4=Smillie | first4=C. S. | last5=Lavergne | first5=S. | last6=Thuiller | first6=W. | last7=Alm | first7=E. J. | title=Unraveling the processes shaping mammalian gut microbiomes over evolutionary time | journal=Nature Communications | volume=8 | page=14319 | doi=10.1038/ncomms14319 | pmc=5331214 | bibcode=2017NatCo...814319G }}</ref>

===Explicit modeling of three or more levels===
[[File:Three level reconciliation example.svg|thumb|A higher level of organization can structure two lower levels in the context of phylogenetic reconciliation.]]
In a model of a multi-level system as host/symbiont/genes, horizontal gene transfers should be more likely between two symbionts of a same host. This is invisible to a two-level gene tree/species tree or host/symbiont reconciliation: in some cases, looking at any combination of two levels can lead to missing an evolutionary scenario which can only be the most likely if the information from the three trees is considered together.

Trying to face the limitation of these uses of standard two-level reconciliations with systems involving inter-dependencies at multiple levels, a methodological effort has been undertaken in the last decade to construct and use multi-level models. This requires the identification of at least one "intermediate" level between the upper and the lower one.

<gallery class="center">
File:Phylogenetic reconciliation upper aware.svg|Two levels can be reconciled with the constraint of an upper one, for instance host and symbiont with geography.
File:Phylogenetic reconciliation intermediate character.svg|Characters can evolve on reconciled phylogenies, like gene synteny on a gene/species reconciliation.
File:Phylogenetic reconciliation inter intra transfer.svg|Transfers can be upper dependent, which is more likely between two intermediate entities that belong to a same upper one.
File:Phylogenetic reconciliation intermediate inference.svg|With 3-levels reconciliation models, the intermediate tree can be inferred from the lower and upper trees.
</gallery>

====Pre-reconciliation: characters onto reconciled trees====
A first step towards integrated three-level models is to consider phylogenetic trees at two levels and another level represented only with characters at the leaves of one of the trees.

For instance, a reconciliation of host and symbiont phylogenies can be informed by geographic data.<ref name=berry_geography-aware_2018>{{Cite journal|pmid = 29697894| year=2018 | last1=Berry | first1=V. | last2=Chevenet | first2=F. | last3=Doyon | first3=J. P. | last4=Jousselin | first4=E. | title=A geography-aware reconciliation method to investigate diversification patterns in host/Parasite interactions | journal=Molecular Ecology Resources | volume=18 | issue=5 | pages=1173–1184 | doi=10.1111/1755-0998.12897 | s2cid=25758856 }}</ref> Ancestral geographic locations of host and symbiont species obtained through a character inference method can then be used to constrain the host/symbiont reconciliation: ancestral hosts and symbionts can only be associated if they belong to the same geographical location.

At another scale, the evolution at the sub-gene level can be approached with a character method.<ref name=wu_evolution_2012>{{Cite journal|pmid = 21900599| year=2012 | last1=Wu | first1=Y. C. | last2=Rasmussen | first2=M. D. | last3=Kellis | first3=M. | title=Evolution at the subgene level: Domain rearrangements in the Drosophila phylogeny | journal=Molecular Biology and Evolution | volume=29 | issue=2 | pages=689–705 | doi=10.1093/molbev/msr222 | pmc=3258039 }}</ref> Here, parts of genes (e.g. the sequence coding for protein domains) is reconciled according to a DL model with a species tree, and the genes they belong to are mentioned as characters of these parts. Ancestral genes are then reconstructed a posteriori via merge and splits of gene parts.

====Two-level reconciliations informed by a third level====
As pointed out by several studies mentioned in {{section link||Horizontal transfer at multiple levels}}, an upper level can inform a reconciliation between an intermediate and lower one, notably for horizontal transfers.

Three-level models can take into account these assumptions to guide reconciliations between an intermediate tree and lower levels with the knowledge of an upper tree. The model can for example give higher likelihoods to reconciliation scenarios where horizontal gene transfers happen between entities sharing the same [[habitat]]. This has been achieved for the first time with DTL gene/species reconciliations nested with a DTL gene domain and gene reconciliation.<ref name=stolzer_event_2015>{{Cite journal|pmid = 26451642| year=2015 | last1=Stolzer | first1=M. | last2=Siewert | first2=K. | last3=Lai | first3=H. | last4=Xu | first4=M. | last5=Durand | first5=D. | title=Event inference in multidomain families with phylogenetic reconciliation | journal=BMC Bioinformatics | volume=16 | issue=Suppl 14 | pages=S8 | doi=10.1186/1471-2105-16-S14-S8 | pmc=4610023 | doi-access=free }}</ref> Different costs for inter and intra transfers depend on whether or not transfers happen between genes of the same genomes.

Note that this model explicitly considers three levels and three trees, but does not yet define a real three-level reconciliation, with a likelihood or score associated.<ref name=stolzer_event_2015/> It relies on a sequential operation, where the second reconciliation is informed by the result of the first one.

====The reconciliation problem in multi-level models====
The next step is to define the score of a reconciliation consisting of three nested trees and to compute, given the three trees, three-level reconciliations according to their score. It has been achieved with a species/gene/domain system, where genes evolve within the species tree with a DL model and domains evolve within the gene/species system with a DTL model, forbidding domain transfers between genes of two different species.<ref name=li_integrated_2019>{{Cite journal|pmid = 29994126| year=2019 | last1=Li | first1=L. | last2=Bansal | first2=M. S. | title=An Integrated Reconciliation Framework for Domain, Gene, and Species Level Evolution | journal=IEEE/ACM Transactions on Computational Biology and Bioinformatics | volume=16 | issue=1 | pages=63–76 | doi=10.1109/TCBB.2018.2846253 | s2cid=51614715 | doi-access=free }}</ref> Inference involves candidate scenarios with joint scores. Computing the minimum score scenario is NP-hard, but dynamic programming or integer linear programming can offer heuristics.<ref name=li_integrated_2019/><ref name=li_integer_2018>{{cite book | doi=10.1145/3233547.3233603 | chapter=An Integer Linear Programming Solution for the Domain-Gene-Species Reconciliation Problem | title=Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics | year=2018 | last1=Li | first1=Lei | last2=Bansal | first2=Mukul S. | pages=386–397 | isbn=9781450357944 | s2cid=49426403 }}</ref> Variations of the problem considering multiple domains<ref name=li_simultaneous_2019>{{cite book | doi=10.1007/978-3-030-20242-2_7 | chapter=Simultaneous Multi-Domain-Multi-Gene Reconciliation Under the Domain-Gene-Species Reconciliation Model | title=Bioinformatics Research and Applications | series=Lecture Notes in Computer Science | year=2019 | last1=Li | first1=Lei | last2=Bansal | first2=Mukul S. | volume=11490 | pages=73–86 | isbn=978-3-030-20241-5 | s2cid=85507475 }}</ref> are available, and so is a simulation framework.<ref name=kundu_sagephy:_2019>{{Cite journal|pmid = 30715213| year=2019 | last1=Kundu | first1=S. | last2=Bansal | first2=M. S. | title=SaGePhy: An improved phylogenetic simulation framework for gene and subgene evolution | journal=Bioinformatics | volume=35 | issue=18 | pages=3496–3498 | doi=10.1093/bioinformatics/btz081 }}</ref>

====Inferring the intermediate tree using models of 3-level lower/intermediate/upper reconciliation====
Just like two-level reconciliation can be used to improve lower or upper phylogenies, or to help constructing them from aligned sequences, joint reconciliation models can be used in the same manner.

In this vein, a coupled gene/species DL, domain gene DL and gene sequence evolution model in a Bayesian framework improves the reconstruction of gene trees.<ref name=muhammad_species_2018>{{cite journal | url=https://doi.org/10.1101/336453 | doi=10.1101/336453 | title=Species tree-aware simultaneous reconstruction of gene and domain evolution | year=2018 | last1=Muhammad | first1=Sayyed Auwn | last2=Sennblad | first2=Bengt | last3=Lagergren | first3=Jens | s2cid=90627553 }}</ref>

==Software==
Multiple pieces of software have been developed to implement the various models of reconciliation. The following table does not aim for exhaustiveness but presents a number of software tools aimed at reconciling trees to infer reconciliation scenarios or for related usage, such as correcting or inferring trees, or testing coevolution. 
The levels of interest section details the levels for which the software was implemented, even though it is entirely possible, for instance, to use a software made for species and gene reconciliation to reconcile host and symbionts.<ref name=charlat_ale>{{Cite journal|pmid = 28201740| year=2017 | last1=Bailly-Bechet | first1=M. | last2=Martins-Simões | first2=P. | last3=Szöllosi | first3=G. J. | last4=Mialdea | first4=G. | last5=Sagot | first5=M. F. | last6=Charlat | first6=S. | title=How Long Does Wolbachia Remain on Board? | journal=Molecular Biology and Evolution | volume=34 | issue=5 | pages=1183–1193 | doi=10.1093/molbev/msx073 | doi-access=free }}</ref> Parsimony or probability is the underlying model that is used for the reconciliation.

{| class="wikitable sortable"
|-
! Name !! Levels of interest !! Platform !! [[Command line]] or [[Graphical user interface|graphical user interface (GUI)]] !! Usage !! Probability or parsimony !! Software availability and [[software license]]
|-
| Diva<ref>{{cite web |title=Diva |date=26 April 2013 |url=https://sourceforge.net/projects/diva/ |access-date=21 November 2022}}</ref> || Geography and species || [[Unix]], [[macOS|Mac]], [[Microsoft Windows|Win]] || Command line || Reconciliation inference || Parsimony || [[GNU GPLv2]]
|-
| Lagrange<ref>{{cite web |title=Lagrange |url=https://code.google.com/archive/p/lagrange/ |access-date=21 November 2022}}</ref> || Geography and species || [[Linux]], Mac, Win || [[Python (programming language)|Python package]] || Reconciliation inference || Probability || GNU GPLv2
|-
| BioGeoBEARS<ref>{{cite web |title=BioGeoBEARS |url=http://phylo.wikidot.com/biogeobears |access-date=21 November 2022}}</ref> || Geography and species || [[R package]] || R package || Reconciliation inference, statistical model test || Probability ||GNU GPLv2, [[GNU GPLv3]]
|-
| Jane<ref>{{cite web |title=Jane |url=https://www.cs.hmc.edu/~hadas/jane/ |access-date=21 November 2022}}</ref> || Host and symbionts || Unix, Mac, Win || GUI or command line || Reconciliation inference, tree uncertainty || Parsimony || [[Proprietary software|Proprietary]], registration to download
|-
| eMPRess<ref>{{cite web |title=eMPRess |url=https://sites.google.com/g.hmc.edu/empress/home |access-date=21 November 2022}}</ref> || Host and symbionts || Unix, Mac, Win || GUI or command line || Reconciliation inference, cost estimation, solution space study|| Parsimony || GNU GPLv3
|-
| Eucalypt<ref>{{cite web |title=Eucalypt |date=28 July 2014 |url=https://team.inria.fr/erable/en/software/eucalypt/ |access-date=21 November 2022}}</ref> || Host and symbionts || [[Java (programming language)|Java]] || Command line, graphical output with included viewer CophyTrees|| Reconciliation inference, solution space study || Parsimony || [[CeCILL]]
|-
| Capybara<ref>{{cite web |title=Capybara |url=https://capybara-doc.readthedocs.io/ |access-date=21 November 2022}}</ref> || Host and symbionts || Linux, Mac, Win, and Python package|| GUI, Python package || Reconciliation inference, solution space study || Parsimony || code available on [https://github.com/Helio-Wang/capybara github]
|-
| Coala<ref>{{cite web |title=Coala |date=28 July 2014 |url=https://team.inria.fr/erable/en/software/coala/ |access-date=21 November 2022}}</ref> || Host and symbionts || Linux, Mac || Command line|| cost estimation || Parsimony || CeCILL
|-
| RANGER-DTL<ref>{{cite web |title=RANGER-DTL |date=31 May 2018 |url=https://compbio.engr.uconn.edu/software/ranger-dtl/ |access-date=21 November 2022}}</ref> || Species and genes || Linux, Mac, Win || Command line|| Reconciliation inference, tree uncertainty, solution sampling, replacing transfers || Parsimony || GNU GPLv3
|-
| Notung<ref>{{cite web |title=Notung |url=http://www.cs.cmu.edu/~durand/Notung/ |access-date=21 November 2022}}</ref> || Species and genes || Linux, Mac, Win < 7 || GUI || Reconciliation inference, tree uncertainty, gene, gene domain, species model || Parsimony || Proprietary
|-
| Mowgli<ref>{{cite web |title=Mowgli |url=http://www.atgc-montpellier.fr/Mowgli/ |access-date=21 November 2022}}</ref> || Species and genes, Host and symbiont|| Linux, Mac || Command line, graphical output with compatible viewer Sylvx || Reconciliation inference, tree uncertainty, ILS, geographical constraints, dated tree input || Parsimony || Proprietary
|-
| Sylvx<ref>{{cite web |title=Sylvx |url=http://www.sylvx.org/ |access-date=21 November 2022}}</ref> || Species and genes, Host and symbiont|| Linux, Mac, Win || GUI || Viewer, compatible with Mowgli, ecceTERA || - || GNU GPLv2 or later
|-
| AnGST<ref>{{cite web |title=AnGST |url=https://web.mit.edu/almlab/angst.html |access-date=21 November 2022}}</ref> || Species and genes|| Python 2 || Command line || Reconciliation inference, cost estimation, dated tree input, tree uncertainty || Parsimony || [[source-available software]]<ref>Code available on [https://github.com/almlab/angst Github]</ref>
|-
| ecceTERA<ref>{{cite web |title=ecceTERA |website=[[GitHub]] |date=21 September 2021 |url=https://github.com/celinescornavacca/ecceTERA |access-date=21 November 2022}}</ref> || Species and genes|| Linux, Mac, built from code|| Command line, compatible with Sylvx viewer, and recphyloxml output|| Reconciliation inference, cost estimation, dated, partially dated or undated species tree input, tree uncertainty, reconciliation space study, species network || Parsimony || CeCILL
|-
| ALE<ref>{{cite web |title=ALE |website=[[GitHub]] |date=4 October 2022 |url=https://github.com/ssolo/ALE |access-date=21 November 2022}}</ref> || Species and genes|| Linux, Mac || Command line|| Reconciliation inference, cost estimation, dated or undated species tree input, tree uncertainty || Probability || GNU GPLv3
|-
| Treerecs<ref>{{cite web |title=Treerecs – Fast, Versatile and user friendly phylogenetic reconciliation |url=https://project.inria.fr/treerecs/ |access-date=20 December 2022}}</ref> || Species and genes|| Linux, Mac, Win || GUI, integrated to [http://doua.prabi.fr/software/seaview Seaview]|| DL tree correction || Parsimony, Probability || [[GNU Affero General Public License|GNU Affero GPL]] Version 3.0-or-later
|-
| GeneRax<ref>{{cite web |title=GeneRax |website=[[GitHub]] |url=https://github.com/BenoitMorel/GeneRax |access-date=20 December 2022 |date=8 September 2022}}</ref> || Species and genes|| Linux, Mac || Command line, graphical output with recphyloxml and thirdkind || Gene tree inference from reconciliation and aligned sequences, species tree inference|| Probability || GNU Affero GPL v3.0
|-
| Phyldog<ref>{{cite web |title=PHYLDOG: joint reconstruction of species and gene phylogenies |url=https://pbil.univ-lyon1.fr/software/phyldog/ |website=pbil.univ-lyon1.fr |access-date=20 December 2022 |language=fr}}</ref> || Species and genes|| Linux, docker, vm || Command line || Gene and species tree inference from reconciliation and aligned sequences|| Probability || CeCILL
|-
| CoRe-PA<ref>{{cite web |title=Leipzig University - Faculty of Mathematics and Computer Science - Swarm Intelligence and Complex Systems Group |url=http://pacosy.informatik.uni-leipzig.de/49-1-CoRe-PA.html |website=pacosy.informatik.uni-leipzig.de |access-date=20 December 2022}}</ref> || Host and symbiont|| Linux, Mac, Win || GUI, Command line, graphical svg output || Reconciliation inference, cost estimation, dated tree, statistical test|| Parsimony || -
|-
| CoRe-ILP<ref>{{cite web |title=Universität Leipzig - Fakultät für Mathematik und Informatik - Professur für Schwarmintelligenz und Komplexe Systeme |url=http://pacosy.informatik.uni-leipzig.de/217-0-CoRe-ILP.html |website=pacosy.informatik.uni-leipzig.de |access-date=20 December 2022}}</ref> || Host and symbiont|| Linux, Mac, Win || Command line || Reconciliation inference, temporal feasibility, dated tree|| Parsimony || requires [[CPLEX]] (academic license can be obtained for free)
|-
| Rascal<ref name=drinkwater_rascal_2016/> || Host and symbiont|| Java || Command line || Reconciliation inference, dated tree|| Parsimony || -
|-
| MixTreEM<!-- http://prime.scilifelab.se/mixtreem/index.html -->{{Dead link|date=December 2022}} || Species and gene|| Linux, Mac, Win (build from source) || Command line || Gene and species tree inference from reconciliation and aligned sequences|| Probability || <!--(Open source)?-->
|-
| PrIME<!-- http://prime.scilifelab.se/ -->{{Dead link|date=December 2022}} || Species and gene|| Linux, Mac || Command line, graphical output (PrIMETV) || Reconciliation inference, gene and species tree inference from reconciliation and aligned sequences, orthology analysis|| Probability || <!--(Open source)?-->
|-
| Treemap<!-- http://prime.scilifelab.se/mixtreem/index.html -->{{Dead link|date=December 2022}} || Host and symbiont|| Java || Command line || Reconciliation inference, statistical test|| Parsimony || <!--(Open source)?-->
|-
| JPrIME<ref>{{cite web |last1=Arvestad |first1=Lars |title=About JPrIME |website=[[GitHub]] |url=https://github.com/arvestad/jprime |access-date=20 December 2022 |date=6 September 2021}}</ref> || Gene and species|| Java library || Command line || Reconciliation inference, gene and species tree inference from reconciliation and aligned sequences|| Probability || New BSD
|-
| SEADOG<ref>{{cite web |last1=Orlando |first1=Echevarria |title=SEADOG {{!}} Computational Biology Research Laboratory |url=https://compbio.engr.uconn.edu/software/seadog/ |website=compbio.engr.uconn.edu |access-date=20 December 2022 |date=31 May 2018}}</ref> || Species and genes and domains|| Linux, Mac || Command line || 3-level reconciliation inference|| Parsimony || GNU GPLv3
|-
| iGTP<ref>{{cite web |title=iGTP Home |url=https://genome.cs.iastate.edu/igtp/home |website=Computational Biology Laboratory |access-date=20 December 2022 |language=en}}</ref> || Species and genes|| Linux, Mac, Win || GUI || Gene tree correction in DL or deep coalescence|| Parsimony || Source code on request
|-
| TreeSolve<ref>{{cite web |last1=Mukul |first1=Bansal |title=TreeSolve {{!}} Computational Biology Research Laboratory |url=https://compbio.engr.uconn.edu/software/treesolve/ |website=compbio.engr.uconn.edu |date=26 November 2018}}</ref> || Species and genes|| Linux, Win || GUI || Gene tree correction in DTL|| Parsimony || Source code on request
|-
| TreeFix,<ref>{{cite web |title=TreeFix |url=https://www.cs.hmc.edu/~yjw/software/treefix/ |website=www.cs.hmc.edu |access-date=20 December 2022}}</ref> TreeFix-DTL<ref>{{cite web |title=TreeFix-DTL |url=https://www.cs.hmc.edu/~yjw/software/treefix-dtl/ |website=www.cs.hmc.edu |access-date=20 December 2022}}</ref> || Species and genes|| Linux || Command line || Gene tree correction in DL and DTL|| Parsimony || GNU GPLv3
|-
| ARTra<ref>{{cite web |last1=Mukul |first1=Bansal |title=ARTra: Additive and Replacing Transfer Inference {{!}} Computational Biology Research Laboratory |url=https://compbio.engr.uconn.edu/software/ARTra/ |website=compbio.engr.uconn.edu |access-date=20 December 2022 |date=26 November 2018}}</ref>|| Species and genes|| Linux, Mac || Command line || Additive and replacing transfers inference|| Parsimony || GNU GPL
|-
| DLCoal<ref>{{cite web |title=DLCoal: Modeling gene duplications, losses, and coalescence. |url=http://compbio.mit.edu/dlcoal/ |website=compbio.mit.edu |access-date=20 December 2022}}</ref>|| Species and genes|| Linux, Mac, Win || Command line || Reconciliation inference with ILS|| Parsimony || GNU GPL
|-
| Thirdkind<ref>{{cite web |title=Home · simonpenel/thirdkind Wiki |url=https://github.com/simonpenel/thirdkind/wiki |website=GitHub |access-date=20 December 2022 |language=en}}</ref> || Species and genes|| Linux, Mac, Win || Command line || Viewer, compatible with recphyloxml|| - || CeCILL
|}

== References ==
{{Academic peer reviewed|Q115175616|doi-access=free}}
{{reflist|colwidth=30em}}

== External links ==
{{Scholia}}
* {{Commons category-inline}}

{{Phylogenetics}}

[[Category:Phylogenetics]]
[[Category:Evolutionary biology]]
[[Category:NP-complete problems]]