Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-06T13:00:22.298Z Has data issue: false hasContentIssue false
  • English
  • Français

Generalized Markov branching trees

Part of: Stochastic processes

Published online by Cambridge University Press:  17 March 2017

Harry Crane
Harry Crane*
Affiliation:
Rutgers University
*
* Postal address: Department of Statistics and Biostatistics, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854, USA. Email address: hcrane@stat.rutgers.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.

Motivated by the gene tree/species tree problem from statistical phylogenetics, we extend the class of Markov branching trees to a parametric family of distributions on fragmentation trees that satisfies a generalized Markov branching property. The main theorems establish important statistical properties of this model, specifically necessary and sufficient conditions under which a family of trees can be constructed consistently as sample size grows. We also consider the question of attaching random edge lengths to these trees.

Keywords

Markov branching treeexchangeable random partitionexchangeable fragmentationbeta-splitting modelcoalescent processhidden Markov model

MSC classification

Primary: 60G09: Exchangeability 60G05: Foundations of stochastic processes
Secondary: 92D10: Genetics
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 1 , March 2017 , pp. 108 - 133
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Abraham, R.,Delmas, J.-F. and He, H. (2012).Pruning Galton‒Watson trees and tree-valued Markov processes.Ann. Inst. H. Poincaré Prob. Statist.48,688–705.Google Scholar
[2] Aldous, D. (1996).Probability distributions on cladograms.In Random Discrete Structures(IMA Vol. Math. Appl. 76),Springer,New York,pp.1–18.Google Scholar
[3] Aldous, D. (1998).Tree-valued Markov chains and Poisson Galton‒Watson distributions.In Microsurveys in Discrete Probability(DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41),American Mathematical Society,Providence, RI,pp.1–20.Google Scholar
[4] Aldous, D. and Pitman, J. (1998).Tree-valued Markov chains derived from Galton‒Watson processes.Ann. Inst. H. Poincaré Statist. 34,637–686.Google Scholar
[5] Aldous, D.,Krikun, M. and Popovic, L. (2008).Stochastic models for phylogenetic trees on higher-order taxa.J. Math. Biol. 56,525–557.Google Scholar
[6] Berestycki, N. and Pitman, J. (2007).Gibbs distributions for random partitions generated by a fragmentation process.J. Statist. Phys. 127,381–418.CrossRefGoogle Scholar
[7] Bertoin, J. (1996).Lévy Processes.Cambridge University Press.Google Scholar
[8] Bertoin, J. (2006).Random Fragmentation and Coagulation Processes(Camb. Stud. Adv. Math. 102).Cambridge University Press.CrossRefGoogle Scholar
[9] Burke, C. J. and Rosenblatt, M. (1958).A Markovian function of a Markov chain.Ann. Math. Statist. 29,1112–1122.Google Scholar
[10] Crane, H. (2013).Consistent Markov branching trees with discrete edge lengths.Electron. Commun. Prob. 18,14pp.Google Scholar
[11] Crane, H. (2013).Some algebraic identities for the α-permanent.Linear Algebra Appl. 439,3445–3459.Google Scholar
[12] Crane, H. (2014).The cut-and-paste process.Ann. Prob. 42,1952–1979.Google Scholar
[13] Crane, H. (2015).Clustering from categorical data sequences.J. Amer. Statist. Assoc. 110,810–823.Google Scholar
[14] Crane, H. (2015).Generalized Ewens‒Pitman model for Bayesian clustering.Biometrika 102,231–238.Google Scholar
[15] Crane, H. (2016).The ubiquitous Ewens sampling formula.Statist. Sci. 31,1–19.(Rejoinder: 31,37–39.)Google Scholar
[16] Evans, S. N. (2008).Probability and Real Trees(Lecture Notes Math. 1920).Springer,Berlin.CrossRefGoogle Scholar
[17] Evans, S. N. and Winter, A. (2006).Subtree prune and regraft: a reversible real tree-valued Markov process.Ann. Prob. 34,918–961.Google Scholar
[18] Ewens, W. J. (1972).The sampling theory of selectively neutral alleles.Theoret. Pop. Biol. 3,87–112.Google Scholar
[19] Felsenstein, J. (2004).Inferring Phylogenies.Sinauer,Sunderland.Google Scholar
[20] Haas, B. and Miermont, G. (2012).Scaling limits of Markov branching trees with applications to Galton‒Watson and random unordered trees.Ann. Prob. 40,2589–2666.CrossRefGoogle Scholar
[21] Haas, B.,Miermont, G.,Pitman, J. and Winkel, M. (2008).Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models.Ann. Prob. 36,1790–1837.Google Scholar
[22] Hudson, R. (1983).Properties of a neutral allele model with intragenic recombination.Theoret. Pop. Biol. 23,183–201.CrossRefGoogle ScholarPubMed
[23] Kingman, J. F. C. (1982).The coalescent.Stoch. Process. Appl. 13,235–248.Google Scholar
[24] McCullagh, P.,Pitman, J. and Winkel, M. (2008).Gibbs fragmentation trees.Bernoulli 14,988–1002.Google Scholar
[25] McVean, G. and Cardin, N. (2005).Approximating the coalescent with recombination.Phil. Trans. R. Soc. London 360,1387–1393.Google Scholar
[26] Pitman, J. (1995).Exchangeable and partially exchangeable random partitions.Prob. Theory Relat. Fields 102,145–158.Google Scholar
[27] Pitman, J. (2006).Combinatorial Stochastic Processes(Lecture Notes Math. 1875).Springer,Berlin.Google Scholar
[28] Tajima, F. (1983).Evolutionary relationship of DNA sequences in finite populations.Genetics 105,437–460.Google Scholar
[29] Wang, Y. et al. (2014).A new method for modeling coalescent processes with recombination.BMC Bioinformatics 15,12pp.Google Scholar