Capturing a phylogenetic tree when the number of character states varies with the number of leaves

2015/03/03 by Mike Steel, Steel, Mike
Biochemistry, Genetics and Molecular Biology · #FOS: Biological sciences #Populations and Evolution (q-bio.PE) #q-bio.PE

paper · pdf · doi:10.48550/arxiv.1503.00831

3 pages, 0 figures

arxiv created 2015/08/26 · arxiv updated 2015/08/27

Abstract

We show that for any two values α, β>0 for which α+β>1 then there is a value N so that for all n ≥ N the following holds. For any binary phylogenetic tree T on n leaves there is a set of \lfloor n^α\rfloor characters that capture T, and for which each character takes at most \lfloor n^β\rfloor distinct states. Here `capture' means that T is the unique perfect phylogeny for these characters. Our short proof of this combinatorial result is based on the probabilistic method.

Related

• Combinatorial views on persistent characters in phylogenetics
• Defining binary phylogenetic trees using parsimony
• Defining a phylogenetic tree with the minimum number of small-state characters
• Defining binary phylogenetic trees using parsimony: new bounds
• Phylogenetic trees defined by at most three characters