Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-13T00:50:10.340Z Has data issue: false hasContentIssue false
  • English
  • Français

Exchangeable and sampling-consistent distributions on rooted binary trees

Part of: Graph theory Mathematical biology in general Combinatorial probability

Published online by Cambridge University Press:  14 January 2022

Benjamin Hollering  and
Seth Sullivant
Benjamin Hollering*
Affiliation:
North Carolina State University
Seth Sullivant*
Affiliation:
North Carolina State University
*
*Postal address: North Carolina State University, Department of Mathematics, Box 8205, Raleigh, NC 27695, USA.
*Postal address: North Carolina State University, Department of Mathematics, Box 8205, Raleigh, NC 27695, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a notion of finite sampling consistency for phylogenetic trees and show that the set of finitely sampling-consistent and exchangeable distributions on n-leaf phylogenetic trees is a polytope. We use this polytope to show that the set of all exchangeable and sampling-consistent distributions on four-leaf phylogenetic trees is exactly Aldous’ beta-splitting model, and give a description of some of the vertices for the polytope of distributions on five leaves. We also introduce a new semialgebraic set of exchangeable and sampling consistent models we call the multinomial model and use it to characterize the set of exchangeable and sampling-consistent distributions. Using this new model, we obtain a finite de Finetti-type theorem for rooted binary trees in the style of Diaconis’ theorem on finite exchangeable sequences.

Keywords

Beta-splitting modelmultinomial modelrandom trees

MSC classification

Primary: 05C05: Trees
Secondary: 60C05: Combinatorial probability 92B10: Taxonomy, cladistics, statistics
Type
Original Article
Information
Journal of Applied Probability , Volume 59 , Issue 1 , March 2022 , pp. 60 - 80
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. (1996). Probability distributions on cladograms. In Random Discrete Structures (IMA Volumes Math. Appl. Vol. 76), eds Aldous, D. and Pemantle, R., Springer, New York, pp. 1–18.CrossRefGoogle Scholar
Bernstein, D. I., Ho, L. S. T., Long, C., Steel, M., St. John, K. and Sullivant, S. (2015). Bounds on the expected size of the maximum agreement subtree. SIAM J. Discrete Math. 29, 2065–2074.10.1137/140997750CrossRefGoogle Scholar
Bryant, D., McKenzie, A. and Steel, M. (2003). The size of a maximum agreement subtree for random binary trees. In Bioconsensus (DIMACS Series in Discrete Math. Theoret. Comput. Sci. Vol. 61), American Mathematical Society, Providence, RI, pp. 55–65.CrossRefGoogle Scholar
Coronado, T. M., Mir, A., Rosselló, F. and Valiente, G. (2019). A balance index for phylogenetic trees based on rooted quartets. J. Math. Biol. 79, 1105–1148.10.1007/s00285-019-01377-wCrossRefGoogle ScholarPubMed
de Vienne, D. M., Giraud, T. and Martin, O. (2007). A congruence index for testing topological similarity between trees. Bioinformatics 23, 3119–3124.CrossRefGoogle ScholarPubMed
Diaconis, P. (1977). Finite forms of de Finetti’s theorem on exchangeability. Synthese 36, 271–281.10.1007/BF00486116CrossRefGoogle Scholar
Diaconis, P. and Janson, S. (2008). Graph limits and exchangeable random graphs. Rend. Mat. Appl. 28, 33–61.Google Scholar
Ford, D. J. (2006). Probabilities on Cladograms: Introduction to the Alpha Model. PhD thesis, Stanford University.Google Scholar
Forman, N. (2018). Mass-structure of weighted real trees. Preprint, arXiv:1801.02700.Google Scholar
Forman, N., Haulk, C. and Pitman, J. (2018). A representation of exchangeable hierarchies by sampling from random real trees. Prob. Theory Relat. Fields 172, 1–29.CrossRefGoogle Scholar
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.10.1214/07-AOP377CrossRefGoogle Scholar
Lauritzen, S. L., Rinaldo, A. and Sadeghi, K. (2017). On exchangeability in network models. Preprint, arXiv:1709.03885.Google Scholar
Lovász, L. (2012). Large Networks and Graph Limits (Colloquium Publications Vol. 60), American Mathematical Society, Providence, RI.Google Scholar
McCullagh, P., Pitman, J. and Winkel, M. (2008). Gibbs fragmentation trees. Bernoulli 14, 988–1002.10.3150/08-BEJ134CrossRefGoogle Scholar
Wakeley, J. (2008). Coalescent Theory: An Introduction. W. H. Freeman, New York.Google Scholar