Home
People
Papers
Software

For students (in Slovak):
Študijný program
Uplatnenie
Predmety
Seminár
Témy prác

Members of:
Bratislava Biocenter

Funding

Broňa Brejová, Rastislav Královič. A Linear-Time Algorithm for the Isometric Reconciliation of Unrooted Trees. Algorithms, 13(9):225. 2020.

Download preprint: not available

Download from publisher: https://doi.org/10.3390/a13090225

Related web page: not available

Bibliography entry: BibTeX

Abstract: 

In the reconciliation problem, we are given two phylogenetic trees. A 
species tree represents the evolutionary history of a group of species, and 
a gene tree represents the history of a family of related genes within these 
species. A reconciliation maps nodes of the gene tree to the corresponding 
points of the species tree, and thus helps to interpret the gene family 
history. In this paper, we study the case when both trees are unrooted and 
their edge lengths are known exactly. The goal is to root them and to find a 
reconciliation that agrees with the edge lengths. We show a linear-time 
algorithm for finding the set of all possible root locations, which is a 
significant improvement compared to the previous \$O(N^3log N)\$ algorithm.