ON A MATCHING DISTANCE BETWEEN ROOTED PHYLOGENETIC TREES

被引：43

作者：

Bogdanowicz, Damian ^{[1
]}

Giaro, Krzysztof ^{[1
]}

机构：

[1] Gdansk Univ Technol, Fac Elect Telecommun & Informat, Dept Algorithms & Syst Modeling, PL-80233 Gdansk, Poland

来源：

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE | 2013年 / 23卷 / 03期

关键词：

phylogenetic tree; phylogenetic tree metric; phylogenetic tree comparison; matching cluster distance; matching split distance; SCALING ALGORITHMS; METRICS; SUPERTREE; DISTRIBUTIONS;

D O I：

10.2478/amcs-2013-0050

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Robinson-Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach based on a minimum-weight perfect matching in bipartite graphs, the values of similarity between clusters are transformed to the final MC-score of the dissimilarity of trees. The analyzed properties give insight into the structure of the metric space generated by MC, its relations with the Matching Split (MS) distance of unrooted trees and asymptotic behavior of the expected distance between binary n-leaf trees selected uniformly in both MC and MS (Theta(n(3/2))).

引用

页码：669 / 684

页数：16

共 52 条

[1] An algebraic metric for phylogenetic trees [J].

Alberich, Ricardo ;

Cardona, Gabriel ;

Rossello, Francesc ;

Valiente, Gabriel .

APPLIED MATHEMATICS LETTERS, 2009, 22 (09) :1320-1324

[2]

Aldous D., 1991, London Math. Soc. Lecture Note Ser., V167, P23, DOI [10.1017/CBO9780511662980.003, DOI 10.1017/CBO9780511662980.003]

[3]

[Anonymous], 2002, PAUP*. Phylogenetic Analysis Using Parsimony (*and other methods). Version 4

[4] Comparing and aggregating partially resolved trees [J].

Bansal, Mukul S. ;

Dong, Jianrong ;

Fernandez-Baca, David .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (48) :6634-6652

[5] Robinson-Foulds Supertrees [J].

Bansal, Mukul S. ;

Burleigh, J. Gordon ;

Eulenstein, Oliver ;

Fernandez-Baca, David .

ALGORITHMS FOR MOLECULAR BIOLOGY, 2010, 5

[6] KIS: AN AUTOMATED ATTRIBUTE INDUCTION METHOD FOR CLASSIFICATION OF DNA SEQUENCES [J].

Biedrzycki, Rafal ;

Arabas, Jaroslaw .

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2012, 22 (03) :711-721

[7]

Bin Ma, 1998, RECOMB 98. Proceedings of the Second Annual International Conference on Computational Molecular Biology, P182

[8] The delayed rise of present-day mammals [J].

Bininda-Emonds, Olaf R. P. ;

Cardillo, Marcel ;

Jones, Kate E. ;

MacPhee, Ross D. E. ;

Beck, Robin M. D. ;

Grenyer, Richard ;

Price, Samantha A. ;

Vos, Rutger A. ;

Gittleman, John L. ;

Purvis, Andy .

NATURE, 2007, 446 (7135) :507-512

[9] The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance [J].

Blum, Michael G. B. ;

Francois, Olivier ;

Janson, Svante .

ANNALS OF APPLIED PROBABILITY, 2006, 16 (04) :2195-2214

[10] Inferring and Validating Horizontal Gene Transfer Events Using Bipartition Dissimilarity [J].

Boc, Alix ;

Philippe, Herve ;

Makarenkov, Vladimir .

SYSTEMATIC BIOLOGY, 2010, 59 (02) :195-211

← 1 2 3 4 5 6 →