In phylogenetics, reconciliation is an approach to connect the history of two or more coevolving biological entities. The general idea of reconciliation is that a phylogenetic tree representing the evolution of an entity (e.g. homologous genes or 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 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
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 symbionts 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, the interacting history of transposable elements and species, the evolution of a protein complex across species. The scale of evolutionary events considered can go from population events such as geographical diversification to nucleotids levels one inside genes, including for instance chromosome levels events inside genomes such as whole genome duplication. Phylogenies have been used for representing the diversification of life at many levels of organization: macro-organisms, their cells throughout development, micro-organisms through marker genes, chromosomes, proteins, protein domains, and can also be helpful to understand the evolution of human culture elements such as languages or fairy tales. 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 dolls) 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). 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—in particular those based on duplication-transfer-loss events, which are central to this article—can be transposed, with slight modifications, to any pair of connected levels: 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 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. The term reconciliation has been used by Wayne Maddison in 1997, 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 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. Character methods, such as Brooks Parsimony Analysis, 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. Debates followed, as the methods were not yet completely sound but integrated useful information in a new framework. 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. Reconciliation returned to the framework it was introduced in, gene and species. After character models were considered for horizontal gene transfer, 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. 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. New developments start to bring the different frameworks together with new integrative models.
Pocket Gophers and their chewing lices: a classical example
Pocket gophers (Geomyidae) and their chewing lice (Trichodectidae) form a well studied system of host and symbiont coevolution. 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, using two different frameworks which could be deemed as pre-dynamic programming DTL reconciliation. In modern DTL reconciliation frameworks, costs are assigned to events. The two scenarios were then shown to correspond to maximum parsimonious reconciliation with different cost assignments. 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 6 × 0 + 1 × 2 + 3 × 1 + 1 × 3 = 8 {\displaystyle 6\times 0+1\times 2+3\times 1+1\times 3=8} and scenario B of 5 × 0 + 1 × 2 + 3 × 1 + 2 × 3 = 11 {\displaystyle 5\times 0+1\times 2+3\times 1+2\times 3=11} , 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
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, the geographical region on a species tree, the number of genes on a genome tree, or nucleotides in a sequence. Such methods thus aim at reconstructing ancestral characters at internal nodes of the tree. 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 Duplication and loss were invoked first to explain the presence of multiple copies of a gene in a genome or its absence in certain species. It is possible with those two events to reconcile any two trees, 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 (LCA) mapping: proceeding from the leaves to the root, each 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 parsimony principle: no event should be invoked if it is not necessary. However the use of this principle is debated, 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 and death Markovian model is such a model that can generate a lower tree "inside" a fixed upper one from root to leaves. Statistical inference provides a framework to find most likely scenarios, and in that case, a 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.
Introducing horizontal transfer
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 admixture or introgression. It is considered in character methods, without information from the symbiont phylogeny. 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. 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 co-speciations with a heuristic algorithm. Another solution is to give relative costs to the events and find a scenario that minimizes the sum of the costs of its events. 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 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. In a parsimony framework, costs of reconciling a lower subtree rooted at l {\displaystyle l} with an upper subtree rooted at U {\displaystyle U} is initialized for the leaves with their matching:
And then inductively, denoting l ′ , l ′ ′ {\displaystyle l^{\prime },l^{\prime \prime }} the children of l , U ′ , U ′ ′ {\displaystyle l,U^{\prime },U^{\prime \prime }} the children of U , c S , c D , c T , c L {\displaystyle U,c^{S},c^{D},c^{T},c^{L}} the costs associated with speciation, duplication, horizontal transfer and loss, respectively (with c S {\displaystyle c^{S}} often fixed to 0),
The costs min V ( c ( V , l ′ ) ) {\displaystyle \min _{V}(c(V,l^{\prime }))} and min V ( c ( V , l ′ ′ ) ) {\displaystyle \min _{V}(c(V,l^{\prime \prime }))} , because they do not depend on U {\displaystyle U} , can be computed once for all U {\displaystyle U} , hence achieving quadratic complexity to compute c {\displaystyle c} for all couples of U {\displaystyle U} and l {\displaystyle l} . 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. With an unlimited use, it is necessary to use or add other known methods to solve systems of equations like fixed point methods, or numerical solving of differential equations. In 2016, only two out of seven of the most commonly used parsimony reconciliation programs did handle TL events, although their consideration can drastically change the result of a reconciliation. 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 quadratic time, 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. 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
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 explores in a recursive manner the space of cost vectors, searching for a good matching with the event frequencies in reconciliations. ALE uses the same idea in a probabilistic framework to estimate the event rates by maximum likelihood. Alternatively, COALA is a preprocess using approximate Bayesian computation with sequential 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 optimal solution. 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 chooses the costs that minimize the variation of genome size, in number of genes, between parent and children species.
The problem of temporal feasibility
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-hard. It is 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. Some solutions imply integer linear programming or branch and bound exploration. 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 polynomial time or with a speed-up in RASCAL, by testing only a fraction of node mappings. Most of the software taking undated trees does not look for temporal feasibility, except Jane, which explores the space of total orders via a genetic algorithm, or, in a post process, Notung, and Eucalypt, which searches inside the set of optimal solutions for time consistent ones. Other methods work as supplementary layers to reconciliations, correcting reconciliations or returning a subset of feasible transfers, which can be used to date a species tree.
Expanding phylogenies: Transfers from the dead
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. Accounting for extinct or unsampled biodiversity in phylogenetic studies can give a better understanding of these processes. 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 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, showing that considering these transfers improves the capacity to reconstruct gene trees using reconciliation, and with a more explicit model and in a probabilistic setting, in ALE undated.
The specificity of biogeography: a tree like structure for the "evolution" of 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—with events and dynamic programming—can infer evolutionary scenarios between the upper geographical structure and the lower species tree. Diva and Lagrange 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 is a biogeography inference package that reimplemented DIVA and Lagrange models and allows for new options, like distant dependent transfers and discussion on statistical model selection.
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, while others, and specific packages, in DL or DTL, 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, has been established and endorsed by part of the community, and a viewer is available, able to display reconciliation in multi level systems.
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
Dynamic programming makes it possible to sample reconciliations, uniformly among optimal ones or according to their likelihood. It is also possible to enumerate them in time proportional to the number of solutions, 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 or by constructing a graph summarizing the optimal solutions. This can be achieved by giving support values to specific events based on all optimal (or suboptimal) reconciliations, or with the use of a consensus reconciled tree. In a DL model, it is possible to define a median reconciliation, based on shared events and to compute it in polynomial time. EMPRess can group similar reconciliations through clustering, with all pairwise distance between reconciliations computable in polynomial time (independently of the number of most parsimonious reconciliations). With the same aim, Capybara 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, 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. 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. 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 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 unrooted symbiont trees or dealing with polytomies in Jane.
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. In a duplication-loss model, the set of roots minimizing the costs are found close to one another, forming a "plateau", a property which does not generalize to DTL.
Reconciliation can also take as input 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. In DTL, the problem is NP hard. Heuristics and exact fixed parameter tractable algorithms 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, 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. 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. AngST, ALE and ecceTERA 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 and in GeneRax with DTL. In a DL model with sequence evolution and relaxed molecular clock, the lower tree space can be explored with an MCMC. MowgliNNI 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. Finally, integrative models—mixing sequence evolution and reconciliation—can compute a joint likelihood via dynamic programming (for both reconciliation and gene sequences evolution), use Markov chain Monte Carlo to include molecular clock to estimate branch lengths, in a DL model or with a relaxed molecular clock, and in a DTL model. 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. It is particularly interesting in the case of gene/species reconciliation where many (typically thousands of) gene trees are available from 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, and with a generalised Robinson Foulds multicopy distance, with better running time but assuming gene trees do not contain bipartitions contradicting the species tree, which seems rare under a DL model.
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—minimizing a DL reconciliation score—is NP-hard. In particular, reconstructing the species tree giving the best DL cost for several gene trees is NP-hard and 2-approximable. 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. It is NP-hard, with interesting results on the problem complexity and the behaviour of the model with different input size, structure and ILS presence. Multiple solutions exists, with ILP or heuristics, and with the possibility of a deep coalescence score. ODTL 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 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 presents a faster solution.
Limits of the two-level DTL model
A limit to dynamic programming: non independent evolution of 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. 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) upper and lower forests. The problem is NP-hard, but several approximations have been proposed. Replacing transfers can be considered on top of the DL model. 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.
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 intractable inference problems, because polytomies need to be resolved. It is also modeled by an additional evolutionary event "failure to diverge" (Jane, Amocoala). 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. 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.
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 deep coalescence of lineages, leading to Incomplete Lineage Sorting (ILS), which is not handled by the DTL model. 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. 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. Notung 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 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 network instead of a tree. This models in particular introgression, with the possibility to estimate model parameters. More integrative reconciliation models accounting for ILS have been proposed, including both DL and multispecies coalescent, with DLCoal. It is a probabilistic model with a parsimony translation, 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
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 geographi