Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T02:26:15.525Z Has data issue: false hasContentIssue false
  • English
  • Français

Teasing Apart Two Trees

Published online by Cambridge University Press:  01 November 2007

M. A. STEEL  and
L. A. SZÉKELY
M. A. STEEL
Affiliation:
Biomathematics Research Centre,Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand (e-mail: m.steel@math.canterbury.ac.nz)
L. A. SZÉKELY
Affiliation:
Department of Mathematics, University of South Carolina, Columbia SC, USA (e-mail: szekely@math.sc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A widely studied model for generating binary sequences is to ‘evolve’ them on a tree according to a symmetric Markov process. We show that under this model distinguishing the true (model) tree from a false one is substantially ‘easier’ (in terms of the sequence length needed) than determining the true tree. The key tool is a new and near-tight Ramsey-type result for binary trees.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 6 , November 2007 , pp. 903 - 922
Copyright
Copyright © Cambridge University Press 2007

References

[1]Alon, N., and Spencer, J. H. (1992) The Probabilistic Method, Wiley, New York.Google Scholar
[2]Bininda-Emonds, O. R. P., Brady, S. G., Kim, J. and Sanderson, M. J. (2001) Scaling of accuracy in extremely large phylogenetic trees. Pacific Symposium on Biocomputing 6 547–558.Google Scholar
[3]Colonius, H. and Schulze, H. H. (1981) Tree structures for proximity data. British J. Math. Statist. Psych. 34 167–180.CrossRefGoogle Scholar
[4]Daskalakis, C., Mossel, E. and Roch, S. (2006) Optimal phylogenetic reconstruction. Proc 38th annual ACM Symposium on Theory of Computing (STOC) 159–68. ACM Press, New York.Google Scholar
[5]Dekker, M. C. H. (1986) Reconstruction methods for derivation trees. Master's thesis, Vrije Universiteit, Amsterdam.Google Scholar
[6]Erdod, P. L., Steel, M. A., Székely, L. A. and Warnow, T. J. (1999) A few logs suffice to build (almost) all trees I. Random Struct. Alg. 14 153–184.Google Scholar
[7]Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000) Broadcasting on trees and the Ising model. Adv. Appl. Probab. 10 410–433.Google Scholar
[8]Guindon, S. and Gascuel, O. (2003) A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Systematic Biology 52 696–704.CrossRefGoogle ScholarPubMed
[9]Lovász, L. (1979) Combinatorial Problems and Exercises, Akadémiai Kiadó, Budapest, and North-Holland.Google Scholar
[10]Mason, K. (1996) On a matter of uncertain parentage. Honours III project, University of Canterbury.Google Scholar
[11]Mossel, E. (1998) Recursive reconstruction on periodic trees. Random Struct. Alg. 13 81–97.3.0.CO;2-O>CrossRefGoogle Scholar
[12]Mossel, E. (2004) Phase transitions in phylogeny Trans. Amer. Math. Soc. 356 2379–2404.CrossRefGoogle Scholar
[13]Mossel, E. and Peres, Y. (2003) Information flow on trees. Ann. Appl. Probab. 13 817–844.CrossRefGoogle Scholar
[14]Neyman, J. (1971) Molecular studies of evolution: A source of novel statistical problems. In Statistical Decision Theory and Related Topics(Gupta, S. S. and Yackel, J., eds), New York, Academic Press, pp. 1–27.Google Scholar
[15]Rokas, A. and Carroll, S. B. (2005) More genes or more taxa? The relative contribution of gene number and taxon number to phylogenetic accuracy. Mol. Biol. Evol. 22 1337–1344.CrossRefGoogle ScholarPubMed
[16]Semple, C. and Steel, M. (2003) Phylogenetics, Oxford University Press.CrossRefGoogle Scholar
[17]Stamatakis, A. P., Ludwig, T. and Meier, H. (2004). A fast program for maximum likelihood-based inference of large phylogenetic tress. In Proc. 2004 ACM Symposium on Applied Computing, ACM Press, New York, pp. 197–201.CrossRefGoogle Scholar
[18]Steel, M. (1989) Distributions on bicoloured evolutionary trees. PhD thesis, Massey University, Palmerston North, New Zealand.Google Scholar
[19]Steel, M. and Charleston, M. (1995) Five surprising properties of parsimoniously coloured trees. Bull. Math. Biol. 57 367–375.CrossRefGoogle Scholar
[20]Steel, M. A., Hendy, M. D. and Penny, D. (1998) Reconstructing phylogenies from nucleotide pattern frequencies: A survey and some new results. Discrete Appl. Math. 88 367–396.CrossRefGoogle Scholar
[21]Steel, M. A. and Székely, L. A. (1999) Inverting random functions. Ann. Combin. 3 103–113.CrossRefGoogle Scholar
[22]Steel, M. A. and Székely, L. A. (2002) Inverting random functions II: Explicit bounds for the discrete maximum likelihood estimation, with applications. SIAM J. Discrete Math. 15 562–575.CrossRefGoogle Scholar