Computing the quartet distance between evolutionary trees in time O(n log n)

被引:29
作者
Brodal, GS [1 ]
Fagerberg, R [1 ]
Pedersen, CNS [1 ]
机构
[1] Aarhus Univ, Dept Comp Sci, BRICS, DK-8000 Aarhus C, Denmark
关键词
evolutionary trees; distance measures; quartet distance; hierarchical decompositions;
D O I
10.1007/s00453-003-1065-y
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time 0 (it log n). The previous best algorithm for the problem uses time 0(n(2)).
引用
收藏
页码:377 / 395
页数:19
相关论文
共 19 条
[1]  
Allen B. L., 2001, ANN COMB, V5, P1
[2]  
[Anonymous], COMBINATORIAL MATH
[3]  
[Anonymous], 1997, ALGORITHMS STRINGS T, DOI DOI 10.1017/CBO9780511574931
[4]   PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].
BRENT, RP .
JOURNAL OF THE ACM, 1974, 21 (02) :201-206
[5]  
Brodal GS, 2001, LECT NOTES COMPUT SC, V2223, P731
[6]  
Brodal GS, 2001, LECT NOTES COMPUT SC, V2076, P140
[7]  
Brodal GS, 2000, LECT NOTES COMPUT SC, V1848, P397
[8]  
Bryant D, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P285
[9]  
Buneman P., 1971, Mathematics in the Archaeological and Historical Sciences, P387
[10]   DYNAMIC EXPRESSION-TREES [J].
COHEN, RF ;
TAMASSIA, R .
ALGORITHMICA, 1995, 13 (03) :245-265