# A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees
## 1 Introduction  
Reconciliation of gene trees and species trees is a computational problem arising in evolutionary biology that has been studied since 1979 [1]. Here, we concentrate on a variant proposed by [PERSON] et al. [2, 3], called isometric reconciliation. We provide a linear-time algorithm for reconciling two unrooted trees, which is a significant improvement over the previous \(O(N^{3}\log N)\) algorithm [4]. A species tree represents an evolutionary history of a group of species. Present-day species are typically placed in the leaves, and internal nodes correspond to speciation events. Speciation is a process in which individuals of a single species separate into two groups that further evolve independently. A gene tree represents an evolutionary history of a group of related genes from several species. In the simplest scenario, each individual has a single copy of a particular gene, and these genes are propagated along the species tree, yielding the gene tree identical to the species tree. However, during evolution, a gene can be lost (deleted), and it can also become duplicated, whereupon a particular species and its descendants have multiple copies of the gene. After a series of such duplication and deletion events, the gene tree and the species tree will differ. In a gene tree, the leaves represent copies of the gene in the present-day species and the internal nodes represent speciations and duplications. Lost gene copies are not represented in gene trees. The goal of reconciliation is to map nodes of a gene tree to the corresponding points in a species tree that represent the same points in the evolutionary history. This mapping helps to distinguish whether a node of a gene tree corresponds to a speciation or a duplication and to estimate the number of deletions (see an example in Figure 1). Note that gene trees and species trees representing evolutionary histories are rooted, with the root representing the last common ancestor of all the leaves. However, trees are in practice constructed from DNA or protein sequences, and many commonly used methods are unable to determine the root location, so instead provide only an unrooted version of the tree [5]. In the isometric reconciliation, both trees have known edge lengths and the reconciliation has to obey these lengths (see an example in Figure 2). The problem was introduced by [PERSON] et al. [2; 3], who provided a polynomial-time algorithm for reconciling an unrooted gene tree with a rooted species tree. [PERSON] et al. [4] have provided a corrected and improved version of this algorithm, which runs in \(O(N\log N)\) time, where \(N\) is the total number of nodes in the two trees combined. The authors also provided algorithms for several variants of the problem, including an \(O(N^{5}\log N)\)-time algorithm to compute all reconciliations of two unrooted trees. In this paper, we improve this running time to \(O(N)\) for gene trees with node degrees bounded by \(O(1)\) (typically, unrooted phylogenetic trees have internal nodes of degree three). To achieve this time, we only output pairs of valid root locations in the two trees instead of full reconciliations. Given any pair of such root locations, the full reconciliation can be computed in \(O(N\log N)\) time by a simple algorithm given by [PERSON] et al. [4]. If the earlier algorithm [4] is modified to output only root locations, it still runs in \(O(N^{3}\log N)\) time; thus the algorithm presented here is a significant improvement. We also characterize the set of possible root locations, proving that it always forms a connected subgraph of the species tree and that the distances between different root locations in the species tree and their counterparts in the gene tree are preserved. Finally, note that the problem of gene tree and species tree reconciliation was also studied in other settings [6]. The most traditional is the parsimony setting that uses unweighted trees and seeks a reconciliation minimizing the number of inferred duplications and deletions.