TY - GEN

T1 - New results on optimizing rooted triplets consistency

AU - Byrka, Jaroslaw

AU - Guillemot, Sylvain

AU - Jansson, Jesper Andreas

PY - 2008/12/1

Y1 - 2008/12/1

N2 - A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem ( ) and the minimum rooted triplets inconsistency problem ( ) in which the input is a set of rooted triplets, and where the objectives are to find a largest cardinality subset of which is consistent and a smallest cardinality subset of whose removal from results in a consistent set, respectively. We first show that a simple modification to Wu's Best-Pair-Merge-First heuristic [25] results in a bottom-up-based 3-approximation for . We then demonstrate how any approximation algorithm for could be used to approximate , and thus obtain the first polynomial-time approximation algorithm for with approximation ratio smaller than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any tree is approximately one third, and then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both and are NP-hard even if restricted to minimally dense instances. Finally, we prove that cannot be approximated within a ratio of Ω(logn) in polynomial time, unless P∈=∈NP.

AB - A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem ( ) and the minimum rooted triplets inconsistency problem ( ) in which the input is a set of rooted triplets, and where the objectives are to find a largest cardinality subset of which is consistent and a smallest cardinality subset of whose removal from results in a consistent set, respectively. We first show that a simple modification to Wu's Best-Pair-Merge-First heuristic [25] results in a bottom-up-based 3-approximation for . We then demonstrate how any approximation algorithm for could be used to approximate , and thus obtain the first polynomial-time approximation algorithm for with approximation ratio smaller than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any tree is approximately one third, and then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both and are NP-hard even if restricted to minimally dense instances. Finally, we prove that cannot be approximated within a ratio of Ω(logn) in polynomial time, unless P∈=∈NP.

UR - http://www.scopus.com/inward/record.url?scp=58549097720&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-92182-0_44

DO - 10.1007/978-3-540-92182-0_44

M3 - Conference article published in proceeding or book

SN - 3540921818

SN - 9783540921813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 484

EP - 495

BT - Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings

T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008

Y2 - 15 December 2008 through 17 December 2008

ER -