Hylogenetic information complexity: Is testing a tree easier than finding it? Export

@misc{citeulike:2998773, 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 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.}, archivePrefix = {arXiv}, author = {Steel, Mike and Szekely, Laszlo and Mossel, Elchanan}, citeulike-article-id = {2998773}, citeulike-linkout-0 = {http://arxiv.org/abs/0807.1756}, citeulike-linkout-1 = {http://arxiv.org/pdf/0807.1756}, eprint = {0807.1756}, keywords = {bio, information, phylogeny}, month = {Jul}, posted-at = {2008-07-14 13:55:03}, priority = {2}, title = {Hylogenetic information complexity: Is testing a tree easier than finding it?}, url = {http://arxiv.org/abs/0807.1756}, year = {2008} }

TY - ELEC ID - citeulike:2998773 L3 - citeulike-article-id:2998773 N2 - 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 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. TI - Hylogenetic information complexity: Is testing a tree easier than finding it? KW - bio KW - information KW - phylogeny AU - Steel, Mike AU - Szekely, Laszlo AU - Mossel, Elchanan PY - 2008/Jul/10/ UR - http://arxiv.org/abs/0807.1756 ER -