Minimal Phylogenetic Supertrees and Local Consensus Trees

AIMS Medical Science

article

Jesper Jansson¹  Ramesh Rajaby²  Wing-Kin Sung¹ 

[1] Department of Computing, The Hong Kong Polytechnic University;NUS Graduate School for Integrative Sciences and Engineering, National University of Singapore;School of Computing, National University of Singapore;Genome Institute of Singapore

关键词: Phylogenetic tree;    rooted triplet;    local consensus;    minimal supertree;    algorithms;    computational complexity;    ;   

DOI  :  10.3934/medsci.2018.2.181

来源: American Institute of Mathematical Sciences

【 摘 要 】

The problem of constructing a minimally resolved phylogenetic supertree (i.e., a rooted tree 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 article, 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 et al. in 1998.) We also measure the running times and memory usage in practice of the new algorithms for various inputs. Finally, we use our implementations to experimentally investigate the non-optimality of Aho et al.’s well-known BUILD algorithm from 1981 when applied to the local consensus tree problems considered here.

【 授权许可】

CC BY