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

Bordewich, M.; Semple, C.

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: May 6, 2015
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1430472