{'fraction_non_alphanumeric': 0.042512555704887885, 'fraction_numerical': 0.007250477470467568, 'mean_word_length': 4.376497432972048, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Unifying Parsimonious Tree Reconciliation

Evolution is a process that is influenced by various environmental factors, e.g. the interactions between different species, genes, and biogeographical properties. Hence, it is interesting to study the combined evolutionary history of multiple species, their genes, and the environment they live in. A common approach to address this research problem is to describe each individual evolution as a phylogenetic tree and construct a tree reconciliation which is parsimonious with respect to a given event model. Unfortunately, most of the previous approaches are designed only either for host-parasite systems, for gene tree/species tree reconciliation, or biogeography. Hence, a method is desirable, which addresses the general problem of mapping phylogenetic trees and covering all varieties of coevolving systems, including e.g., predator-prey and symbiotic relationships. To overcome this gap, we introduce a generalized cophylogenetic event model considering the combinatorial complete set of local coevolutionary events. We give a dynamic programming based heuristic for solving the maximum parsimony reconciliation problem in time O(n^2), for two phylogenies each with at most n leaves. Furthermore, we present an exact branch-and-bound algorithm which uses the results from the dynamic programming heuristic for discarding partial reconciliations. The approach has been implemented as a Java application which is freely available from http://pacosy.informatik.uni-leipzig.de/coresym.


Introduction
Tree reconciliation analysis is a powerful tool in phylogenetics and has a wide variety of applications. It is used in cladistic biogeography as well as for studying host-parasite coevolution and gene/species tree inference [21]. A common principle for creating tree reconciliations is to use event-based maximum parsimony [24]. Therefore, coevolutionary events are defined together with a cost model for the events and a reconciliation of the trees is sought that minimizes the overall costs. Table 1 shows the common events used within the different types of applications. Two closely related types of this problem can be distinguished: tree inference and tree embedding/tree mapping. In the first case an overarching tree is sought that embeds a given set of, possibly incongruent, trees. In the second case two (or more) trees are given and a mapping of those trees onto each other is sought. Although tree reconciliation refers to both types of problems, the scope of this paper lies on the latter case.
Starting in 1979 Goodman et al. [8] introduced the problem of embedding gene trees into species trees. They presented a method to construct most parsimonious reconciliations, based on the evolutionary events gene duplication and gene loss. Since then, several algorithms for gene tree/species tree reconciliation have been developed, e.g., GeneTree [20], SDI [29], Softparsmap [1], Notung [5,27], and Mowgli [7]. These tools either consider additional events like lateral gene transfer or incomplete lineage sorting, or they are extended to suit unresolved phylogenetic trees. Recently, [26] examines lateral gene transfer to and from species that are not represented in the phylogenetic tree, i.e. extincted or unsampled species. The respective event was called lateral transfer from the dead.
A similar problem arose in the field of biogeography, where species trees and area cladograms have to be reconciled. Nelson and Platnick [15] were the first who proposed general assumptions for inferring area cladograms from species trees that have been implemented in the software COMPONENT 1.5 [18]. There are several other approaches for inferring area cladograms from species trees, based on association matrices, e.g., component compatibility analysis [28], Brooks parsimony analysis [2], and three area statement analysis [14]. But all of them are pattern-based approaches and do not produce reconciled trees. The dispersalvicariance analysis [23] implemented in the software DIVA is an event-based method considering vicariance, duplication, dispersal, and extinction events. It supports tree inference as well as tree embedding.
In 1988 Hafner and Nadler published a cophylogenetic analysis on pocket gophers and their chewing lice parasites [9]. Methods designed for biogeographical [15] as well as gene tree/species tree problems [11] to examine cospeciation events in host-parasite systems have been proposed in [10]. In the same year Ronquist and Nylin [24] suggested the usage of colonisation, exclusion, and successive specialization events with given weights relative to the probability of each event. Based on these events they developed a method for reconstructing the evolutionary history for two given phylogenetic trees and an association matrix describing the associations between extant species. This type of data set can be represented graphically by a so called tanglegram [3]. In the same paper Charleston developed a data structure, called jungles, and a method to construct all optimal solutions for the reconciliation problem with events cospeciation, duplication, lineage sorting, and host switch under a general weighting scheme. The approach was implemented in the software TreeMap 2.0 and extended in Tarzan [12] by the use of additional timing information. Jane [6] and CoRe-PA [13] use dynamic programming to efficiently compute reconciliations based on the same event model. The latter tool also considered unresolved phylogenies and presented a method for approximating event costs automatically. Additionally a first attempt was given to handle parasites infesting multiple hosts. The current version 4 of Jane supports multi-host parasites and failure to diverge events as well. Furthermore, it is able to automatically resolve polytomies.
In [19] Page already pointed out the similarity between the three different types of reconciliation problems and gave a unified definition of reconciled trees. He presented the software COMPONENT 2.0, which he applied to data sets from all three types of problems.
Gene tree/species tree, biogeography, and host-parasite reconciliation problems have in common, that there exists an overarching tree into which the other trees have to be embedded, i.e., the gene trees have to be embedded into a species tree, the species tree into an area cladogram, and the parasite tree into a host tree. Until now there is no event model and respective algorithms which considers the general problem of two trees which also can be equitable mapped onto each other, as it is the case for, e.g., symbiotic systems or gene-gene interactions. To fill this gap and to straighten up the event proliferation we introduce a combinatorial complete event model of local association patterns. However, a certain type of application may consider a subset of all possible event types only. Therefore, the event model can be utilized by defining a cost model with infinity costs for neglected events. Furthermore, we present a dynamic programming heuristic as well as an exact branch-and-bound algorithm to construct tree reconciliations under the new event model. In [16] it was shown that even the special case of host-parasite tree reconciliation considering the events cospeciation, sorting, duplication, and host switching is NP-complete. Therefore, heuristic or approximation algorithms might be the only chance to obtain solutions in reasonable time for large data sets. However, for smaller data sets an computing an optimal solution might be feasible.

Basic Notations and Preliminaries
For the following formal description we select the cophylogenetic reconciliation of two dependent sets of species as reference problem. Other kinds of tree reconciliation problems, e.g., of species, areas, or genes, are covered analogously.
The evolution of a set of species is usually depicted as a phylogenetic tree, which is a tree T = (V T , E T ) with node set V T , edge set E T , and leaf set L T ⊂ V T . In the context of phylogenetic trees an internal node u ∈ V T \ L T refers to a speciation of an ancestral species u into subspecies. An edge (u ′ , u) ∈ E T represents the time span of the existence of a species u from its emergence after the speciation of u ′ until its own speciation or the present day. We refer to an edge (u ′ , u) as e u or simply u if it is clear from the context. If not stated otherwise we assume a phylogenetic tree being binary and rooted, i.e., each node has an outdegree of either two (internal node) or zero (leaf node) and there is exactly one node, the root ρ T , with indegree zero whereas all other nodes u ∈ V T \ ρ T have indegree one. For each internal node u ∈ V T \L T we denote the children of u as u i with i ∈ {1, 2}. For technical reasons we introduce an artificial root ρ ′ and an edge (ρ ′ , ρ). In that way it is possible to refer to the time span of the existence of root species ρ by e ρ , or simply edge ρ. We define a partial order T on V T biogeography gene tree/species tree host-parasite vicariance [25], allopatric speciation [23] speciation (null event) cospeciation [17], codivergence [4], successive specialisation [24] duplication [25], sympatric speciation [23] gene duplication [8] duplication [17], independent speciation [17] partial extinction [25] sorting [17], partial extinction [17], missing the boat [17] × -speciation and loss [7] -× complete extinction [25] gene loss [8] extinction [17] (partial) dispersal [25] horizontal/lateral gene transfer [5,26], direct transfer [26] host switch [17], partial switch [17] complete dispersal [25] complete switch [ Table 1. Coevolutionary events with the various names used within the different types of applications -biogeography (BG), gene/species tree (GST) and host-parasite coevolution (HPC). Solid lines represent the overarching tree (i.e., the area cladogram, species tree, and host tree, respectively), dotted lines represent the embedded tree (i.e., species tree, parasite tree, and gene tree, respectively).
such that u ′ T u, if and only if u ′ lies on the path from ρ to u. In addition, u ′ ≺ T u if and only if u ′ T u and u ′ = u. Node u ′ is called an ancestor of u and u a descendant of u ′ , respectively. Furthermore, we define the timing τ of a tree as τ : , respectively. In the evolutionary context τ (u) represents the point in time at which the speciation of u took place.
Let (S, T, φ) be a pair of rooted binary trees S = (V S , E S ) and representing inter-species association strengths measured by a value between zero and one. The strength φ(s, t) can be interpreted as an a priori probability of two species s and t being associated. The given definition of φ is a generalization of the leaf-to-leaf associations ϕ defined in [3], extended by association strengths for extant and ancestral species. According to the notion of tanglegrams we refer to such a tuple (S, T, φ) as an X-tanglegram.
A cophylogenetic reconciliation for a given X-tanglegram (S, T, φ) can be described as a set of associations R ⊆ E S × E T between edges, with R being the reconciled interactions between extant as well as ancestral species. Depending on the type of application additional constrains on the set R are required for a reconciliation to be phylogenetically meaningful, e.g., timing constraints. These will be discussed later on. A sub-reconciliation R |s,t is a subset of R such that (e u , e v ) ∈ R |s,t ⇔ (e u , e v ) ∈ R and s S u and t T v, i.e., R |s,t is a reconciliation of the subtrees of S and T rooted at nodes s and t, respectively.
Note that in contrast to previous approaches we describe a reconciliation as a mapping between edges. In [12] a reconciliation was assumed to be a bijective mapping m : {V T } → {V S ∪ E S } from the nodes of the parasite tree to the nodes and edges of the host tree. However, from a given mapping m the respective edge-to-edge mapping R can be derived as follows. Let (t, t i ) ∈ E T be an edge from T and s ∈ V S be the node for which m(t) = s or m(t) = e s . Furthermore, let s ′′ ∈ V S be a node for which m(t i ) = s ′′ or m(t i ) = e s ′′ . Then it holds that (e s , e t ), (e s ′′ , e ti ) ∈ R. If s is an ancestor of s ′′ then for all nodes s ′ , s ≺ S s ′ ≺ S s ′′ it holds that {(e s ′ , e ti )} ∈ R. Additionally, if m(t) = e s is an edge mapping then also (e s , e ti ) ∈ R.

Generalized Coevolutionary Event Model
Previous reconciliation approaches always consider a certain set of cophylogenetic events. These events are designed to suit to a certain type of application and some of them are combinations of other events, e.g., speciation and loss or transfer and loss. In this section a generalized event model is presented that covers all possible local association patterns, i.e., all possible associations between coincident edges of two nodes. Hence, this event model can be applied to most of the applications. In the following the term species will be interchangeably used for edge. This is because associations between species have a one-to-one correspondence to pairs of associated edges in the reconciliation R.
In this approach a cophylogenetic event is defined as a relation between the sets of coincident edges of two nodes s ∈ V S and t ∈ V T . Formally, an event is described as a subset of {e s , e s1 , e s2 } × {e t , e t1 , e t2 }. For a pair of species (s, t) we define a binary variable b (s,t) ∈ {0, 1}, such that b (s,t) = 1 if species s and t are assumed to be associated, i.e., (e s , e t ) ∈ R, otherwise b (s,t) = 0. Hence, an event can be described as an association tuple b A cost model γ : {0, 1} 9 → R is defined specifying a cost value for each of the 2 9 cophylogenetic events. Among the events there are some events which are isomorphic, i.e., they are identical when changing the child order of s 1 and s 2 , respectively t 1 and t 2 . For instance, the event {(e s , e t ), (e s1 , e t )} is isomorphic to the event {(e s , e t ), (e s2 , e t )}. Although it is not required, these isomorphic events should have the same cost value and events with no associations at all should be regarded as null event and therefore get a value of zero.
Not all events which can be modeled this way are phylogenetically meaningful. If, for example, species s is associated with a child t j of species t and t with a child species s i of s, this would immediately result in an inconsistency as the speciation of s had to occur before the speciation of t and vice versa. Therefore, we distinguish between three types of events: i) events with τ (s) < τ (t) (denoted as "<" events), ii) events with τ (s) > τ (t) (">" events) and iii) events with τ (s) = τ (t) ("=" events). In the first case there must not be an association between s and the descendant species t i . The second case is equivalently but with no associations between t and s j . In the last case none of the species s, respectively t, is associated with the descendant species t j , respectively s i . The events for case i) and case ii) are depicted in Figure 1. Case ii) is symmetric to the first case with exchanged roles of s and t. Case iii) is shown in Figure 2.
In the algorithmic sections the restricted set of phylogenetically meaningful events is considered only.

Dynamic Programming
For a given X-tanglegram (S, T, φ) and cost model γ a reconciliation R is sought, such that the sum of all event and leaf-to-leaf association costs is minimal.
In the first step dynamic programming is used to determine all optimal subreconciliations with respect to a given cost model. Therefore, two dynamic programming matrices C 0 and C 1 are computed. C 0 (s, t) gives the costs for the optimal sub-reconciliation R |s,t of the two subtrees rooted at s and t with s and t being not associated. Accordingly, C 1 (s, t) computes the optimal subreconciliation costs with s and t being associated. Starting from a pair of extant species (s, t) the cost of a (non-)association C b (s, t) is evaluated based on the a priori association strength φ(s, t). For pairs of ancestral species (s, t) the cost of each possible cophylogenetic event is evaluated, weighted, and accumulated with the costs of the respective sub-reconciliations. From all those costs the minimum is chosen for C b (s, t). With b = b s,t ∈ {0, 1} the dynamic programming    formulation is as follows.
with the user defined parameter α ≥ 1 resulting in a cost value between 0 and ∞ for the leaf-to-leaf associations (division by 0 is evaluated as ∞). C b ⊙ (s, t), ⊙ ∈ {<, >, =} is the cost of the minimal sub-reconciliation with an event of type ⊙ occurring during the speciation of s and/or t. Precisely: give the weighting factors for the event costs γ( b s,t ). The user defined parameter β ≥ 1 results in factors ranging from 1/β to β. Associations with a strength of x = 0, respectively non-associations with a strength of x = 1, result in infinite costs. The term (2x − 1) is used to normalize g b (x) to result in a factor of 1 if the association strength is 0.5.
After computing the dynamic programming matrices the cost for an optimal reconciliation is given by min(C 0 ρS ,ρT , C 1 ρS ,ρT ) with ρ S and ρ T being the roots of trees S and T . The reconciliation can be retrieved by backtracking.

Time Consistency
Although the dynamic programming solutions are optimal with respect to the given cost model γ, the reconciliations might be phylogenetically invalid due to chronological inconsistencies [12]. With the dynamic programming formulation it is assured that for an association of species s and t no descendant of s is associated with an ancestor of t, and vice versa. However, additional timing constraints are introduced by each pairwise association in R. Assume two species s and t being associated and therefore (e s , e t ) ∈ R. As species s and t interacted, both existed at the same time. Hence, species s has to be emerged before the speciation of t and vice versa and it follows that ∀s ′ < T s : τ (s ′ ) < τ (t), respectively ∀t ′ < T t : τ (t ′ ) < τ (s), see Figure 3 (a). This is not assured by the dynamic programming formulation. Contradicting associations of species from disjoint subtrees of both phylogenies can occur. For an example consider the species s1, s2, t1, and t2 from disjoint subtrees of S, respectively T , with {(e s1 , e t1 ), (e s2 , e t2 )} ⊆ R. Furthermore, let the species s1 ′ and s2 ′ be the parent species of s1, respectively s2. Now assume that s1 ′ is associated with the child species t2 j of t2 and s2 ′ is associated with the child species t1 i of t1, i.e., {(e s1 ′ , e t2j ), (e s2 ′ , e t1i )} ⊆ R. This scenario creates (among others) the timing constraints τ (s1 ′ ) < τ (t1) < τ (s2 ′ ) < τ (t2) < τ (s1 ′ ) which gives a timing inconsistency. Figure 3 (b) shows this example. For a reconciliation to be phylogenetically meaningful such cases must not occur. To determine phylogenetically valid reconciliations the following two definitions are needed. Definition 1 (Timing Graph). For a given X-tanglegram (S, T, φ) and a reconciliation R the timing graph TG is a directed graph (V T G , E T G ) with node set V T G = V S ∪ V T and edge set E T G = E S ∪ E T ∪ {(s ′ , t), (t ′ , s) : (e s , e t ) ∈ R and (s ′ , s) ∈ E S and (t ′ , t) ∈ E T }.
Definition 2 (Time Consistency). A reconciliation R for an X-tanglegram (S, T, φ) is said to be time consistent if its timing graph is acyclic.
Observe that there are event models where the dynamic programming will always create time consistent reconciliations which are parsimonious with respect to the total event costs. Chronological inconsistencies are created by contradicting timing constraints. But the set of timing constraints coming from the tree topologies of both trees without any associations are always compatible. Therefore, for an inconsistency to occur there must be paths in the timing graph connecting nodes of S, respectively T , which have no ancestor/descendant relation, i.e., nodes from distinct subtrees of the same phylogenetic tree. Such constraints are created by either S-duplications (only between nodes from S) and T-duplications (only between nodes from T ) or by any of the landing events (constraints between nodes from both trees). A chronological inconsistency can be created only if combinations of such constrains between both types of trees exist. Therefore, any event model which forbids landing events and allows only one type of duplication (S or T) will lead to time consistent reconciliations. For instance the gene duplication/gene loss event model commonly used for gene tree/species tree reconciliation can be solved without chronological inconsistencies using dynamic programming.
But even if events are considered which possibly lead to chronological inconsistencies, dynamic programming can be used to construct valid solutions as well. This is done by running dynamic programming and checking the timing graph for cycles. In each cycle there exist edges which were introduced due to associations between species. In an iterative way one can restrict the input data by forbidding some of the associations and redo the dynamic programming until the timing graph is acyclic. However, the produced reconciliation may not be parsimonious anymore, see also [22].

Branch-and-Bound Algorithm
Although the (unrestricted) dynamic programming does not necessarily result in a time consistent reconciliation, it can be used to determine a lower bound for the costs of a partially computed reconciliation. This lower bound is used by a branch-and-bound algorithm to cut the computation whenever a partial solution indicates that the cost will be higher than a certain value, e.g., the cost of a previously found reconciliation or a maximum threshold.
The algorithm starts with an empty set of associations and a lower bound of min(C 0 ρS ,ρT , C 1 ρS ,ρT ) for the reconciliation costs. In the branching procedure of the algorithm a decision tree is traversed by considering in each step a pair of species, i.e., edges, as either associated or not associated. In this way a partial reconciliation is constructed adding at most one association per branching step. The pairs are selected in a top-down manner, starting from (ρ S , ρ T ), such that it is assured that when selecting a pair (s, t) all pairs of ancestral species (s ′ , t ′ ), with s ′ ≺ S s and t ′ ≺ T t, were already processed beforehand. For each selection the timing graph is updated and checked for cycles. If the graph contains any cycles the computation is cut at this point and the next pair of species is selected.
As a cophylogenetic event consists of multiple associations, all the respective pairs have to be processed before an event, and therefore its cost, can be determined. If this is the case then the cost of the respective event is added to the cost of the already computed partial reconciliation. The lower bound for the total costs is then given by the costs of the partial reconciliation plus the minimum costs needed for the sub-reconciliations of the unprocessed pairs of subtrees. These minimum costs are taken from the two dynamic programming matrices C 0 and C 1 .
To avoid unnecessary branching after choosing two species s and t as being associated, all pairs (s ′ , t ′′ ) and (s ′′ , t ′ ) with s ′ ≺ S s ≺ S s ′′ and t ′ ≺ T t ≺ T t ′′ are assumed to be not associated, as this would result in timing inconsistencies. The pseudocode is given in Algorithm 1.
Beside timing constraints, some coevolutionary systems require that additional properties have to be satisfied for a reconciliation to be valid. There may be systems which require, e.g., that each species of one type is associated with at least, respectively at most, one species of the other type at a time. For instance in gene tree/species tree reconciliations each (ancestral) gene is associated with exactly one species. As these constraints restrict the set of valid solutions they can be easily integrated into the branch-and-bound algorithm. In each branching step it is checked if the current association will lead to a violation and, if applicable, the computation can be cut.

Discussion
A certain type of application usually requires only a subset of the events modeled by this approach. For each event from this subset a cost value has to be specified. All neglected events get infinite costs and will therefore not occur in reconciliations with finite overall costs. Obviously there is a 1-to-1 correspondence between most of the cophylogenetic events depicted in Table 1 and the events defined by local association patterns shown in Figures 1 and 2. Only the two types of switches (partial and complete) and the lateral transfer from the dead can not be modeled directly by this approach. Instead, a partial switch is seen as a combination of the events takeoff and landing, while a complete switch and a lateral transfer from the dead are modeled by an extinction and a landing. When giving the takeoff and landing events, respectively extinction and landing events, the same accumulated costs, then a certain reconciliation results in the same overall costs in both event models. This opens up new possibilities for solving reconciliation problems for a variety of applications. Biogeography, gene tree/species tree, and host-parasite systems can be reconciled with the same algorithms while only the cost model γ differs. Beside that, further cases of application exists, e.g., general symbiotic systems or interactions of genes or gene products, where both association partners are equitable and a reconciliation can not be produced by simply embedding one tree into the other. In this approach we decided a reconciliation to be a set of associations between edges. This has been done to retain a similar graphical representation for the cophylogenetic events as it has been used in previous publications. However, as more complex events can be modeled by this approach, e.g., the partial cospeciation, visualizing a reconciliation is a complex task and the interpretation of the results might be hard. An alternative is to redefine a reconciliation to be a set of associations between nodes on the directed line graphs (line digraphs) of the phylogenetic trees with artificial root ρ ′ . Both definitions are interchangeable as in the line graph only the roles of nodes and edges are changed but the tree structure is retained. Then a reconciliation can be depicted as a graph with directed tree edges representing the tree topology of both trees and undirected association edges.
The dynamic programming algorithm has a time complexity of O(n 2 ), where n is the number of leaves in the larger phylogenetic tree. For each of the O(n 2 ) many values from the two matrices C b < (s, t), b ∈ {0, 1}, the cost of a constant number of possible association patterns is determined. For each pattern this can be done in constant time.

Conclusion
In this paper we introduced a cophylogenetic event model based on local association patterns between coincident edges. Due to the large variety of possible events and the possibility to neglect events via a corresponding cost model the approach suits to various reconciliation problems. In addition we provided the possibility to use a priori knowledge about association strengths to improve the reconciliations. We presented a O(n 2 ) time heuristic based on dynamic programming as well as an exact branch-and-bound algorithm to solve the reconciliation problem for a given X-tanglegram (S, T, φ) and cost model γ.
Until now, only binary phylogenetic trees are considered. But extending the approach to support polytomies can be done by extending the event model to non-binary events. However, this requires a fixed maximal outdegree for the internal nodes and therefore can not be used for multifurcations of arbitrary size. Alternatively, the polytomies can be resolved within the reconciliation process using heuristic approaches.
In recent years there is a trend towards using also phylogenetic networks. These networks can display hybridization events, as nodes with indegree greater than one. While extending our event model to consider cophylogenetic hybridization is straightforward, further research is needed to adopt the reconciliation algorithms.