BACKGROUND: The 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. RESULTS: An 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. CONCLUSION: LinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons. AVAILABILITY: An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda .
%0 Journal Article
%1 Schaller2021-vf
%A Schaller, David
%A Hellmuth, Marc
%A Stadler, Peter F
%D 2021
%I Springer Science and Business Media LLC
%J Algorithms Mol. Biol.
%K Compatibility Mathematical Rooted of phylogenetics; rooted trees trees;
%N 1
%P 23
%R 10.1186/s13015-021-00202-8
%T A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set
%V 16
%X BACKGROUND: The 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. RESULTS: An 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. CONCLUSION: LinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons. AVAILABILITY: An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda .
@article{Schaller2021-vf,
abstract = {BACKGROUND: The 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. RESULTS: An 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. CONCLUSION: LinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons. AVAILABILITY: An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda .},
added-at = {2024-09-10T11:54:51.000+0200},
author = {Schaller, David and Hellmuth, Marc and Stadler, Peter F},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/207b4b50af12d7929722e02a7fab89220/scadsfct},
copyright = {https://creativecommons.org/licenses/by/4.0},
doi = {10.1186/s13015-021-00202-8},
interhash = {8a3d83100e66e4e828b59a2e03bac9c0},
intrahash = {07b4b50af12d7929722e02a7fab89220},
journal = {Algorithms Mol. Biol.},
keywords = {Compatibility Mathematical Rooted of phylogenetics; rooted trees trees;},
language = {en},
month = dec,
number = 1,
pages = 23,
publisher = {Springer Science and Business Media LLC},
timestamp = {2024-09-10T11:54:51.000+0200},
title = {A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set},
volume = 16,
year = 2021
}
