Four characters suffice to convexly define a phylogenetic tree

被引：11

作者：

Huber, KT ^{[1
]}

Moulton, V

Steel, M

机构：

[1] Univ E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England

[2] Uppsala Univ, Linnaeus Ctr Bioinformat, Uppsala, Sweden

[3] Univ Canterbury, Biomath Res Ctr, Christchurch 1, New Zealand

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2005年 / 18卷 / 04期

关键词：

phylogenetic tree; X-tree; convexly define; display; semidyadic closure; character compatibility;

D O I：

10.1137/S0895480102416696

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It was recently shown that just five characters ( functions on a. finite set X) suffice to convexly define a trivalent tree with leaf set X. Here we show that four characters suffice which, since three characters are not enough in general, is the best possible.

引用

页码：835 / 843

页数：9

共 12 条

[1] A POLYNOMIAL-TIME ALGORITHM FOR THE PERFECT PHYLOGENY PROBLEM WHEN THE NUMBER OF CHARACTER STATES IS FIXED [J].

AGARWALA, R ;

FERNANDEZBACA, D .

SIAM JOURNAL ON COMPUTING, 1994, 23 (06) :1216-1224

[2] RECONSTRUCTING THE SHAPE OF A TREE FROM OBSERVED DISSIMILARITY DATA [J].

BANDELT, HJ ;

DRESS, A .

ADVANCES IN APPLIED MATHEMATICS, 1986, 7 (03) :309-343

[3] Algorithmic aspects of tree amalgamation [J].

Böcker, S ;

Bryant, D ;

Dress, AWM ;

Steel, MA .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (02) :522-537

[4]

Buneman P., 1971, Mathematics in the Archaeological and Historical Sciences, P387

[5] TREE-STRUCTURES FOR PROXIMITY DATA [J].

COLONIUS, H ;

SCHULZE, HH .

BRITISH JOURNAL OF MATHEMATICAL & STATISTICAL PSYCHOLOGY, 1981, 34 (NOV) :167-180

[6]

Dekker M.C., 1986, THESIS VRIJE U AMSTE

[7] A fast algorithm for the computation and enumeration of perfect phylogenies [J].

Kannan, S ;

Warnow, T .

SIAM JOURNAL ON COMPUTING, 1997, 26 (06) :1749-1763

[8] TRIANGULATING VERTEX-COLORED GRAPHS [J].

MCMORRIS, FR ;

WARNOW, TJ ;

WIMER, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) :296-306

[9] Tree reconstruction from multi-state characters [J].

Semple, C ;

Steel, M .

ADVANCES IN APPLIED MATHEMATICS, 2002, 28 (02) :169-184

[10]

SEMPLE C, 2001, LNCS, V2066, P126

← 1 2 →