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 [J].

DAY, WHE .

JOURNAL OF CLASSIFICATION, 1985, 2 (01) :7-28

[2] COMPARISON OF UNDIRECTED PHYLOGENETIC TREES BASED ON SUBTREES OF 4 EVOLUTIONARY UNITS [J].

ESTABROOK, GF ;

MCMORRIS, FR ;

MEACHAM, CA .

SYSTEMATIC ZOOLOGY, 1985, 34 (02) :193-200

[3] OBTAINING COMMON PRUNED TREES [J].

FINDEN, CR ;

GORDON, AD .

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 [J].

PENNY, D ;

HENDY, MD .

SYSTEMATIC ZOOLOGY, 1985, 34 (01) :75-82

[8] VICARIANT PATTERNS AND HISTORICAL EXPLANATION IN BIOGEOGRAPHY [J].

ROSEN, DE .

SYSTEMATIC ZOOLOGY, 1978, 27 (02) :159-188

[9] KAIKOURA TREE THEOREMS - COMPUTING THE MAXIMUM AGREEMENT SUBTREE [J].

STEEL, M ;

WARNOW, T .

INFORMATION PROCESSING LETTERS, 1993, 48 (02) :77-82

[10] DISTRIBUTIONS OF TREE COMPARISON METRICS - SOME NEW RESULTS [J].

STEEL, MA ;

PENNY, D .

SYSTEMATIC BIOLOGY, 1993, 42 (02) :126-141

← 1 2 →