A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set

Algorithms for Molecular Biology

David Schaller¹  Peter F. Stadler²  Marc Hellmuth³ 

[1] Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16–18, 04107, Leipzig, Germany;Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16–18, 04107, Leipzig, Germany;Competence Center for Scalable Data Services and Solutions Dresden/Leipzig, Interdisciplinary Center for Bioinformatics, German Centre for Integrative Biodiversity Research (iDiv), and Leipzig Research Center for Civilization Diseases, Universität Leipzig, Augustusplatz 12, 04107, Leipzig, Germany;Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, 04109, Leipzig, Germany;Department of Theoretical Chemistry, University of Vienna, Währinger Straße 17, 1090, Vienna, Austria;Facultad de Ciencias, Universidad National de Colombia, Sede Bogotá, Ciudad Universitaria, 111321, Bogotá, D.C, Colombia;Santa Fe Institute, 1399 Hyde Park Rd., 87501, Santa Fe, NM, USA;Department of Mathematics, Faculty of Science, Stockholm University, SE-10691, Stockholm, Sweden;

关键词: Mathematical phylogenetics;    Rooted trees;    Compatibility of rooted trees;   

DOI  :  10.1186/s13015-021-00202-8

来源: Springer

【 摘 要 】

BackgroundThe supertree problem, i.e., the task of finding a common refinement of a set of rooted trees is an important topic in mathematical phylogenetics. The special case of a common leaf set L is known to be solvable in linear time. Existing approaches refine one input tree using information of the others and then test whether the results are isomorphic.ResultsAn O(k|L|) algorithm, LinCR, for constructing the common refinement T of k input trees with a common leaf set L is proposed that explicitly computes the parent function of T in a bottom-up approach.ConclusionLinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons.AvailabilityAn implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda.

【 授权许可】

CC BY