Title: Minimal phylogenetic supertrees and local consensus trees
Abstract: The problem of constructing a minimally resolved phylogenetic supertree (i.e., having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree;
for any set S of phylogenetic trees over some leaf label set L,
this gives a minimal phylogenetic tree over L that contains every
rooted triplet present in all trees in S, where ``minimal'' means either having the smallest possible number of internal nodes or
the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998.
Publication Year: 2016
Publication Date: 2016-08-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot