Computer Science ›› 2015, Vol. 42 ›› Issue (12): 283-287.

Previous Articles     Next Articles

Accurately and Efficiently Comparing Rooted Phylogenetic Trees

LI Shu-guang, CHEN Shu-ying and ZHU Li-bo   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Phylogenetic trees represent the historical evolutionary relationships among different species.Comparing phylogenetic trees is a fundamental task in bioinformatics.One way for tree comparison is to define a pairwise measure of similarity or dissimilarity in the tree space to determine how different two trees are.Robinson-Foulds distance is by far the most widely used dissimilarity measure.A new pairwise dissimilarity measure for comparing rooted phylogenetic trees was defined which takes into account not only the identity of clusters in the case of Robinson-Foulds distance,but also more subtle similarities between clusters,and thus may provide more accurate and cleaner measurement than Robin-Foulds distance.Two algorithms to compute this measure efficiently were presented.With slight modifications of these results,they can be applied to five other related comparison indices.

Key words: Phylogenetic trees,Tree comparison,Dissimilarity measure,Robinson-Foulds distance,Cluster

[1] Salemi M,Vandamme A-M,Lemey P.The phylogenetic hand-book:a practical approach to phylogenetic analysis and hypothesis testing [M].Cambridge University Press,2009
[2] 黄原.分子系统发生学[M].北京:科学出版社,2012 Huang Yuan.Molecular Phylogenetics[M].Beijing:Science Press,2012
[3] Semple C,Steel M A.Phylogenetics [M].Oxford UniversityPress,2003
[4] Bodlaender H L,Fellows M R,Warnow T J.Two strikes against perfect phylogeny [M].Springer,1992
[5] Sokal R R,Michener C D.A statistical method for evaluating systematic relationships[J].University of Kansas Scientific Bulletin,1958,38:1409-1438
[6] Saitou N,Nei M.The neighbor-joining method:a new method for reconstructing phylogenetic trees [J].Molecular biology and evolution,1987,4(4):406-425
[7] Fitch W M,Margoliash E.Construction of phylogenetic trees[J].Science,1967,155(760):279-284
[8] Day W H,Johnson D S,Sankoff D.The computational complexity of inferring rooted phylogenies by parsimony [J].Mathematical Biosciences,1986,81(1):33-42
[9] Guindon S,Gascuel O.A simple,fast,and accurate algorithm to estimate large phylogenies by maximum likelihood [J].Systema-tic Biology,2003,52(5):696-704
[10] Roch S.A short proof that phylogenetic tree reconstruction by maximum likelihood is hard [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2006,3(1):92
[11] Huelsenbeck J P,Ronquist F.MRBAYES:Bayesian inference of phylogenetic trees [J].Bioinformatics,2001,17(8):754-755
[12] Drummond A J,Rambaut A.BEAST:Bayesian evolutionary analysis by sampling trees [J].BMC Evolutionary Biology,2007,7(1):214
[13] 李军令,赵宏伟,马志强,等.基于遗传算法的最大似然法构建系统发生树[J].东北师大学报(自然科学版),2008,40(1):36-39 Li Jun-ling,Zhao Hong-wei,Ma Zhi-qiang,et al.A maximum likehoood method based on genetic algorithms for constructing phylogenetic trees[J].Journal of Northeast Normal University(Natural Science Edition),2008,40(1):36-39
[14] 赵建邦,高琳,宋佳.一种基于代谢路径构建系统发生树的有效方法[J].电子学报,2009,37(8):1633-1638 Zhao Jian-bang,Gao Lin,Song Jia.An efficient method for constructing phylogenetic trees based on metabolic pathway[J].Acta Electronica Sinica,2009,37(8):1633-1638
[15] 刘红梅,刘国庆.基于k-mer组分信息的系统发生树构建方法[J].生物信息学,2013,11(2):100-104 Liu Hong-mei,Liu Guo-qing.A method for constructing phylogenetic trees based on k-mer component information[J].China Journal of Bioinformatics,2013,11(2):100-104
[16] 张树波,赖剑煌.分子系统发育分析的生物信息学方法[J].计算机科学,2010,37(8):47-51 Zhang Shu-bo,Lai Jian-huang.Bioinformatics approach for molecular evolution research[J].Computer Science,2010,37(8):47-51
[17] 张丽娜,荣昌鹤,何远,等.常用系统发育树构建算法和软件鸟瞰[J].动物学研究,2013,34(6):640-650 Zhang Li-na,Rong Chang-he,He Yuan,et al.A bird’s eye view of the algorithms and software packages for reconstructing phylogenetic trees[J].Zoological Research,2013,34(6):640-650
[18] Stockham C,Wang L-S,Warnow T.Statistically based postprocessing of phylogenetic analysis by clustering [J].Bioinforma-tics,2002,18(Suppl 1):285-293
[19] Wang J T,Shan H,Shasha D,et al.Fast structural search in phylogenetic databases [J].Evolutionary Bioinformatics,2005,21(1):37-46
[20] de Vienne D M,Giraud T,Martin O C.A congruence index for testing topological similarity between trees [J].Bioinformatics,2007,23(23):3119-3124
[21] Pompei S,Loreto V,Tria F.On the accuracy of language trees [J].PloS one,2011,6(6):e20109
[22] Hayes M,Walenstein A,Lakhotia A.Evaluation of malwarephylogeny modelling systems using automated variant generation [J].Journal in Computer Virology,2009,5(4):335-343
[23] Swofford D L.When are phylogeny estimates from molecular and morphological data incongruent [M]∥Phylogenetic Analysis of DNA Sequences.1991:295-333
[24] Bryant D.Building trees,hunting for trees,and comparing trees:theory and methods in phylogenetic analysis[D].Dept.of Math.,Univ.of Canterbury,1997
[25] Day W H.Optimal algorithms for comparing trees with labeled leaves [J].Journal of Classification,1985,2(1):7-28
[26] Robinson D,Foulds L R.Comparison of phylogenetic trees [J].Mathematical Biosciences,1981,53(1):131-147
[27] Steel M A,Penny D.Distributions of tree comparison metrics—some new results [J].Systematic Biology,1993,42(2):126-141
[28] Bogdanowicz D,Giaro K.On a Matching Distance BetweenRooted Phylogenetic Trees [J].International Journal of Applied Mathematics and Computer Science,2013,23(3):669-684
[29] Gabow H N,Tarjan R E.Faster scaling algorithms for network problems [J].SIAM Journal on Computing,1989,18(5):1013-1036
[30] Bogdanowicz D,Giaro K.Matching split distance for unrooted binary phylogenetic trees [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2012,9(1):150-160
[31] Lin Y,Rajan V,Moret B M.A metric for phylogenetic trees based on matching [J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2012,9(4):1014-1022

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!