| Autor: |
David Schaller, Marc Hellmuth, Peter F. Stadler |
| Jazyk: |
angličtina |
| Rok vydání: |
2021 |
| Předmět: |
|
| Zdroj: |
Algorithms for Molecular Biology, Vol 16, Iss 1, Pp 1-11 (2021) |
| Druh dokumentu: |
article |
| ISSN: |
1748-7188 |
| DOI: |
10.1186/s13015-021-00202-8 |
| Popis: |
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 . |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
