THE AGREEMENT METRIC FOR LABELED BINARY-TREES

被引：40

作者：

GODDARD, W ^{[1
]}

KUBICKA, E ^{[1
]}

KUBICKI, G ^{[1
]}

MCMORRIS, FR ^{[1
]}

机构：

[1] UNIV LOUISVILLE,DEPT MATH,LOUISVILLE,KY 40292

来源：

MATHEMATICAL BIOSCIENCES | 1994年 / 123卷 / 02期

关键词：

D O I：

10.1016/0025-5564(94)90012-4

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

Let S be a set of n objects. A binary tree of S is a binary tree whose leaves are labeled without repetition from S. The operation of pruning a tree T is that of removing some leaves from T and suppressing all inner vertices of degree 2 which are formed by this deletion. Given two trees T and U, an agreement tree is a tree that can be obtained from T as well as from U by pruning the fewest number of leaves from the two trees. A quadratic algorithm is presented for doing this and two metrics are defined based on agreement trees.

引用

页码：215 / 226

页数：12

共 12 条

[1] OPTIMAL-ALGORITHMS FOR COMPARING TREES WITH LABELED LEAVES
DAY, WHE
[J]. JOURNAL OF CLASSIFICATION, 1985, 2 (01) : 7 - 28
[2] COMPARISON OF UNDIRECTED PHYLOGENETIC TREES BASED ON SUBTREES OF 4 EVOLUTIONARY UNITS
ESTABROOK, GF
MCMORRIS, FR
MEACHAM, CA
[J]. SYSTEMATIC ZOOLOGY, 1985, 34 (02): : 193 - 200
[3] OBTAINING COMMON PRUNED TREES
FINDEN, CR
GORDON, AD
[J]. JOURNAL OF CLASSIFICATION, 1985, 2 (2-3) : 255 - 276
[4] Gordon A. D., 1980, ANAL DONNEES INFORMA, P149
[5] KUBICKA E, IN PRESS J CLASSIF
[6] KUBICKA G, 1992, C NUMER, V88, P217
[7] THE USE OF TREE COMPARISON METRICS
PENNY, D
HENDY, MD
[J]. SYSTEMATIC ZOOLOGY, 1985, 34 (01): : 75 - 82
[8] VICARIANT PATTERNS AND HISTORICAL EXPLANATION IN BIOGEOGRAPHY
ROSEN, DE
[J]. SYSTEMATIC ZOOLOGY, 1978, 27 (02): : 159 - 188
[9] KAIKOURA TREE THEOREMS - COMPUTING THE MAXIMUM AGREEMENT SUBTREE
STEEL, M
WARNOW, T
[J]. INFORMATION PROCESSING LETTERS, 1993, 48 (02) : 77 - 82
[10] DISTRIBUTIONS OF TREE COMPARISON METRICS - SOME NEW RESULTS
STEEL, MA
PENNY, D
[J]. SYSTEMATIC BIOLOGY, 1993, 42 (02) : 126 - 141

← 1 2 →