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.
|Keywords:||Phylogenetic tree, r-State character, Chordal graph.|
|Full text:||(VoR) Version of Record|
Download PDF (354Kb)
|Publisher Web site:||http://dx.doi.org/10.1137/130924469|
|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|