TY - GEN
T1 - The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
AU - Jansson, Jesper Andreas
AU - Lingas, Andrzej
AU - Lundell, Eva Marta
PY - 2015/1/1
Y1 - 2015/1/1
N2 - The maximum rooted resolved triplets consistency problem takes as input a set R of resolved triplets and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This paper studies the polynomial-time approximability of a generalization of the problem where in addition to resolved triplets, the input may contain fan triplets and forbidden triplets. To begin with, we observe that the generalized problem admits a 1/4-approximation in polynomial time. Next, we present a polynomial-time approximation scheme (PTAS) for dense instances based on smooth polynomial integer programming. Finally, we generalize Wu’s exact exponential-time algorithm in [19] for the original problem to also allow fan triplets, forbidden resolved triplets, and forbidden fan triplets. Forcing the algorithm to always output a k-ary phylogenetic tree for any specified k ≥ 2 then leads to an exponential-time approximation scheme (ETAS) for the generalized, unrestricted problem.
AB - The maximum rooted resolved triplets consistency problem takes as input a set R of resolved triplets and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in R. This paper studies the polynomial-time approximability of a generalization of the problem where in addition to resolved triplets, the input may contain fan triplets and forbidden triplets. To begin with, we observe that the generalized problem admits a 1/4-approximation in polynomial time. Next, we present a polynomial-time approximation scheme (PTAS) for dense instances based on smooth polynomial integer programming. Finally, we generalize Wu’s exact exponential-time algorithm in [19] for the original problem to also allow fan triplets, forbidden resolved triplets, and forbidden fan triplets. Forcing the algorithm to always output a k-ary phylogenetic tree for any specified k ≥ 2 then leads to an exponential-time approximation scheme (ETAS) for the generalized, unrestricted problem.
KW - Approximation algorithms
KW - Bioinformatics
KW - Phylogenetic tree
KW - Rooted triplet
KW - Smooth integer program
UR - http://www.scopus.com/inward/record.url?scp=84948951201&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-19929-0_23
DO - 10.1007/978-3-319-19929-0_23
M3 - Conference article published in proceeding or book
SN - 9783319199283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 272
EP - 283
BT - Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
PB - Springer Verlag
T2 - 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
Y2 - 29 June 2015 through 1 July 2015
ER -