Abstract
This article presents two new deterministic algorithms for constructing consensus trees. Given an input of κ phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(kn) time, which is optimal since the input size is ω (kn) , and the second one constructs the frequency difference consensus tree in μ\lbrace O(kn2), O(kn (k+log2n)) time.
Original language | English |
---|---|
Pages (from-to) | 15-26 |
Number of pages | 12 |
Journal | IEEE/ACM Transactions on Computational Biology and Bioinformatics |
Volume | 15 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Externally published | Yes |
Keywords
- cluster
- consensus tree
- pairwise compatibility
- Phylogenetic tree
- tree algorithm
ASJC Scopus subject areas
- Biotechnology
- Genetics
- Applied Mathematics