Thumbnail
Access Restriction
Subscribed

Author Jansson, Jesper ♦ Shen, Chuanqi ♦ Sung, Wing-Kin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Phylogenetic tree ♦ Cluster ♦ Greedy consensus tree ♦ Implementation ♦ Loose consensus tree ♦ Majority rule consensus tree ♦ Pairwise compatibility
Abstract A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and widely used ones are the majority rule consensus tree, the loose consensus tree, and the greedy consensus tree. This article presents new deterministic algorithms for constructing them that are faster than all the previously known ones. Given $\textit{k}$ phylogenetic trees with $\textit{n}$ leaves each and with identical leaf label sets, our algorithms run in $\textit{O}(\textit{nk})$ time (majority rule consensus tree), $\textit{O}(\textit{nk})$ time (loose consensus tree), and $O(n^{2}k)$ time (greedy consensus tree). Our algorithms for the majority rule consensus and the loose consensus trees are optimal since the input size is $Ω(\textit{nk}).$ Experimental results show that the algorithms are fast in practice.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 3
Page Count 24
Starting Page 1
Ending Page 24


Open content in new tab

   Open content in new tab
Source: ACM Digital Library