Constructing the Simplest Possible Phylogenetic Network from Triplets

详细信息    查看全文

• 作者：Leo van Iersel ; Steven Kelk
• 刊名：Lecture Notes in Computer Science
• 出版年：2008
• 出版时间：2008
• 年：2008
• 卷：5369
• 期：1
• 页码：472-483
• 全文大小：510.0 KB

文摘

A phylogenetic network is a directed acyclic graph that visualises an evolutionary history containing so-called reticulations such as recombinations, hybridisations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network, which minimises both the level and the total number of reticulations, in time O(|T| k + 1), if k is a fixed upper bound on the level.