Abstract
This paper considers the problem of determining whether a given set T of rooted triplets can be merged without conflicts into a galled phylogenetic network, and if so, constructing such a network. When the input T is dense, we solve the problem in O(|T|) time, which is optimal since the size of the input is Θ(|T|). In comparison, the previously fastest algorithm for this problem runs in O(|T|2) time. Next, we prove that the problem becomes NP-hard if extended to non-dense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set T of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883· |T| of the rooted triplets in T. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in T.
Original language | English |
---|---|
Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) |
Pages | 349-358 |
Number of pages | 10 |
Publication status | Published - 1 Jul 2005 |
Externally published | Yes |
Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: 23 Jan 2005 → 25 Jan 2005 |
Conference
Conference | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Vancouver, BC |
Period | 23/01/05 → 25/01/05 |
ASJC Scopus subject areas
- Software
- General Mathematics