A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set.
Algorithms Mol Biol
; 16(1): 23, 2021 Dec 06.
Article
en En
| MEDLINE
| ID: mdl-34872590
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 .
Texto completo:
1
Colección:
01-internacional
Banco de datos:
MEDLINE
Tipo de estudio:
Prognostic_studies
Idioma:
En
Revista:
Algorithms Mol Biol
Año:
2021
Tipo del documento:
Article
País de afiliación:
Alemania