We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Defining a phylogenetic tree with the minimum number of r-state characters.

Bordewich, M. and Semple, C. (2015) 'Defining a phylogenetic tree with the minimum number of r-state characters.', SIAM journal on discrete mathematics., 29 (2). pp. 835-853.


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.

Item Type:Article
Keywords:Phylogenetic tree, r-State character, Chordal graph.
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
Date accepted:28 January 2015
Date deposited:06 May 2015
Date of first online publication:April 2015
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar