Skip to main content

Research Repository

Advanced Search

Defining a Phylogenetic Tree with the Minimum Number of r-State Characters

Bordewich, M.; Semple, C.

Defining a Phylogenetic Tree with the Minimum Number of r-State Characters Thumbnail


Authors

C. Semple



Abstract

Semple and Steel (2002) showed that if T is a phylogenetic X-tree and C is a collection of r-state characters that defines T , then |C| ≥ (n − 3)/(r − 1), where n = |X|. In this paper, we show that, provided n is sufficiently large, this lower bound is sharp. Furthermore, we show that, for all n ≥ 13, there exists a collection of 4-state characters of size (n − 3)/3 that defines T , but there is a phylogenetic X-tree with n = 12 which is not defined by any set of 3 characters.

Citation

Bordewich, M., & Semple, C. (2015). Defining a Phylogenetic Tree with the Minimum Number of r-State Characters. SIAM Journal on Discrete Mathematics, 29(2), 835-853. https://doi.org/10.1137/130924469

Journal Article Type Article
Acceptance Date Jan 28, 2015
Publication Date Apr 21, 2015
Deposit Date Apr 28, 2015
Publicly Available Date Mar 28, 2024
Journal SIAM Journal on Discrete Mathematics
Print ISSN 0895-4801
Electronic ISSN 1095-7146
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 29
Issue 2
Pages 835-853
DOI https://doi.org/10.1137/130924469
Keywords Phylogenetic tree, r-State character, Chordal graph.

Files

Published Journal Article (362 Kb)
PDF

Copyright Statement
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.





You might also like



Downloadable Citations