AN EFFICIENT ALGORITHM FOR SUPERTREES

被引：33

作者：

CONSTANTINESCU, M ^{[1
]}

SANKOFF, D ^{[1
]}

机构：

[1] UNIV MONTREAL,CTR RECH MATH,MONTREAL,PQ H3C 3J7,CANADA

来源：

JOURNAL OF CLASSIFICATION | 1995年 / 12卷 / 01期

关键词：

TREE COMPATIBILITY; CONSTRAINTS ON TREES; SUPERTREES; CONSENSUS TREES;

D O I：

10.1007/BF01202270

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given k rooted binary trees A1,A2,..,A(k), with labeled leaves, we generate C, a unique system of lineage constraints on common ancestors. We then present an algorithm for constructing the set of rooted binary trees B, compatible with all of A1,A2,..,A(k). The running time to obtain one such supertree is O(k2n2), where n is the number of distinct leaves in all of the trees A1,A2,...,A(k).

引用

页码：101 / 112

页数：12

共 7 条

[1]

AHO A, 1981, J COMPUTING, V3, P405

[2]

Cayley A., 1881, AM J MATH, V4, P266, DOI [10.2307/2369158, DOI 10.2307/2369158]

[3] TREE ENUMERATION MODULO A CONSENSUS [J].

CONSTANTINESCU, M ;

SANKOFF, D .

JOURNAL OF CLASSIFICATION, 1986, 3 (02) :349-356

[4] LEAST-SQUARES ALGORITHMS FOR CONSTRUCTING CONSTRAINED ULTRAMETRIC AND ADDITIVE TREE REPRESENTATIONS OF SYMMETRIC PROXIMITY DATA [J].

DESOETE, G ;

CARROLL, JD ;

DESARBO, WS .

JOURNAL OF CLASSIFICATION, 1987, 4 (02) :155-173

[5] CONSENSUS SUPERTREES - THE SYNTHESIS OF ROOTED TREES CONTAINING OVERLAPPING SETS OF LABELED LEAVES [J].

GORDON, AD .

JOURNAL OF CLASSIFICATION, 1986, 3 (02) :335-348

[6] ON THE EVOLUTIONARY DESCENT OF ORGANISMS AND ORGANELLES - A GLOBAL PHYLOGENY BASED ON A HIGHLY CONSERVED STRUCTURAL CORE IN SMALL SUBUNIT RIBOSOMAL-RNA [J].

GRAY, MW ;

SANKOFF, D ;

CEDERGREN, RJ .

NUCLEIC ACIDS RESEARCH, 1984, 12 (14) :5837-5852

[7] A STRATEGY FOR SEQUENCE PHYLOGENY RESEARCH [J].

SANKOFF, D ;

CEDERGREN, RJ ;

MCKAY, W .

NUCLEIC ACIDS RESEARCH, 1982, 10 (01) :421-431

← 1 →