TY - GEN
T1 - Algorithms for the majority rule (+) consensus tree and the frequency difference consensus tree
AU - Jansson, Jesper Andreas
AU - Shen, Chuanqi
AU - Sung, Wing Kin
PY - 2013/9/25
Y1 - 2013/9/25
N2 - This paper presents two new deterministic algorithms for constructing consensus trees. Given an input of k phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(k n) time, which is optimal since the input size is Ω(k n), and the second one constructs the frequency difference consensus tree in min {O(kn2), O(k n (k + log2n))} time.
AB - This paper presents two new deterministic algorithms for constructing consensus trees. Given an input of k phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(k n) time, which is optimal since the input size is Ω(k n), and the second one constructs the frequency difference consensus tree in min {O(kn2), O(k n (k + log2n))} time.
UR - http://www.scopus.com/inward/record.url?scp=84884359529&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40453-5_12
DO - 10.1007/978-3-642-40453-5_12
M3 - Conference article published in proceeding or book
SN - 9783642404528
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 141
EP - 155
BT - Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
T2 - 13th Workshop on Algorithms in Bioinformatics, WABI 2013
Y2 - 2 September 2013 through 4 September 2013
ER -