期刊
THEORETICAL COMPUTER SCIENCE
卷 363, 期 1, 页码 60-68出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2006.06.022
关键词
phylogenetic network construction; rooted triplet; sorting network; algorithm
We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O(vertical bar T vertical bar(2)) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O(vertical bar T vertical bar(5/3))-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets. (C) 2006 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据