Sammanfattning
A fundamental task in evolutionary biology is the amalgamation of a collection P of leaf-labelled trees into a single parent tree. A desirable feature of any such amalgamation is that the resulting tree preserves all of the relationships described by the trees in P. For unrooted trees, deciding if there is such a tree is NP-complete. However, two polynomial-time approaches that sometimes provide a solution to this problem involve the computation of the semi-dyadic and the split closure of a set of quartets that underlies P. In this paper, we show that if a leaf-labelled tree T can be recovered from the semi-dyadic closure of some set Q of quartet subtrees of T, then T can also be recovered from the split-closure of Q. Furthermore, we show that the converse of this result does not hold, and resolve a closely related question posed in [S. Bocker, D. Bryant, A. Dress, M. Steel, Algorithmic aspects of tree amalgamation, Journal of Algorithms 37 (2000) 522-537]. (c) 2004 Elsevier Ltd. All rights reserved.
Nyckelord
supertree; quartets; splits; semi-dyadic closure; split-closure
Publicerad i
Applied Mathematics Letters
2005, volym: 18, nummer: 3, sidor: 361-366
Utgivare: PERGAMON-ELSEVIER SCIENCE LTD
UKÄ forskningsämne
Datavetenskap (datalogi)
Publikationens identifierare
- DOI: https://doi.org/10.1016/j.aml.2004.01.007
Permanent länk till denna sida (URI)
https://res.slu.se/id/publ/138