Paper Info
Title
Tree Reconstruction from Multi-State Characters
Abstract
In evolutionary biology, a character is a function @g from a set X of present-day species into a finite set of states. Suppose the species in X have evolved according to a bifurcating tree T. Biologists would like to use characters to infer this tree. Assume that @g is the result of an evolutionary process on T that has not involved reverse or parallel transitions; such characters are called homoplasy-free. In this case, @g provides direct combinatorial information about the underlying evolutionary tree T for X. We consider the question of how many homoplasy-free characters are required so that T can be correctly reconstructed. We first establish lower bounds showing that, when the number of states is bounded, the number of homoplasy-free characters required to reconstruct T grows (at least) linearly with the size of X. In contrast, our main result shows that, when the state space is sufficiently large, every bifurcating tree can be uniquely determined by just five homoplasy-free characters. We briefly describe the relevance of this result for some new types of genomic data, and for the amalgamation of evolutionary trees.
Year
DOI
Venue
2002
10.1006/aama.2001.0772
Advances in Applied Mathematics
Keywords
Field
DocType
tree reconstruction,set x,phylogeny,chordal graph.,homoplasy-free character,evolutionary tree,finite set,character compatibility,present-day species,evolutionary biology,main result,evolutionary process,multi-state characters,. tree,bifurcating tree,underlying evolutionary tree,state space,evolutionary trees,lower bound,tree,chordal graph
Graph theory,Discrete mathematics,Combinatorics,Finite set,Phylogenetic tree,Chordal graph,K-ary tree,Tree structure,State space,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
28
2
0196-8858
Citations 
PageRank 
References 
8
1.16
7
Authors
2
Name
Order
Citations
PageRank
Charles Semple143247.99
Mike Steel227041.87