Determining the Consistency of Resolved Triplets and Fan Triplets

Journal of computational biology: A journal of computational molecular cell biology

AndrzejLingas^2¹  JesperJansson^1²  Wing-KinSung^3,4³  RameshRajaby^3⁴ 

[1] Department of Computer Science, Lund University, Lund, Sweden^2;Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong^1;Genome Institute of Singapore, Genome, Singapore, Singapore^4;School of Computing, NUS Graduate School for Integrative Sciences and Engineering, National University of Singapore, Singapore^3

关键词: computational complexity;    phylogenetic tree;    rooted triplets consistency;    tree algorithm;   

DOI  :  10.1089/cmb.2017.0256

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

TheConsistency problem takes as input two setsandof resolved triplets and two setsandof fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements inand no elements inas embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfyingwhose running time is linear in the size of the input and therefore optimal.

【 授权许可】

Unknown