title: Phylogenetic information complexity: is testing a tree easier than finding it?
abstract: Phylogenetic trees describe the evolutionary history of a group of present-day species from a common ancestor. These trees are typically reconstructed from aligned DNA sequence data. In this paper we analytically address the following question: Is the amount of sequence data required to accurately reconstruct a tree significantly more than the amount required to test whether or not a candidate tree was the 'true' tree? By 'significantly', we mean that the two quantities do not behave the same way as a function of the number of species being considered. We prove that, for a certain type of model, the amount of information required is not significantly different; while for another type of model, the information required to test a tree is independent of the number of leaves, while that required to reconstruct it grows with this number. Our results combine probabilistic and combinatorial arguments.
authors.affiliation: Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand. m.steel@math.canterbury.ac.nz
authors.forename: Mike
authors.initials: M
authors.lastname: Steel
authors.forename: Laszlo
authors.initials: L
authors.lastname: Székely
authors.forename: Elchanan
authors.initials: E
authors.lastname: Mossel
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D003198:Computer Simulation; D008957:Models, Genetic; D010802:Phylogeny; D011336:Probability; D017422:Sequence Analysis, DNA