Isomorphism and symmetries in random phylogenetic trees

DOI10.1239/JAP/1261670685MaRDI QIDQ3402055zbMATH OpenOpenAlexWikidataFDO

Authors Miklós Bóona, Philippe Flajolet

Publication date 2 February 2010

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.0696

zbMATH Keywords

analytic combinatoricscombinatorial probabilitygenerating functionlimit distributionsphylogenetic treesrandom treesingularity analysissymmetries and automorphisms

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: The probability that two randomly selected phylogenetic trees of the same size are isomorphic is found to be asymptotic to a decreasing exponential modulated by a polynomial factor. The number of symmetrical nodes in a random phylogenetic tree of large size obeys a limiting Gaussian distribution, in the sense of both central and local limits. The probability that two random phylogenetic trees have the same number of symmetries asymptotically obeys an inverse square-root law. Precise estimates for these problems are obtained by methods of analytic combinatorics, involving bivariate generating functions, singularity analysis, and quasi-powers approximations.

Recommendations

• On the number of vertices of each rank in phylogenetic trees and their generalizations
• Distribution of the Symmetric Difference Metric on Phylogenetic Trees
• On symmetries in phylogenetic trees
• The distribution of the number of automorphisms of random trees
• Limit theorems for patterns in phylogenetic trees

Cites work

• A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics
• Analytic combinatorics
• Central and local limit theorems applied to asymptotic enumeration
• Distribution statistique de l'ordre d'un élément du groupe symétrique. (Statistical distribution of the order of an element of the symmetric group)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 867647 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• scientific article; zbMATH DE number 3090543 (Why is no real title available?)
• Indexed dendrograms on random dissimilarities
• On convergence rates in the central limit theorems for combinatorial structures
• On some problems of a statistical group-theory. III
• The average height of binary trees and other simple trees
• The expected number of symmetries in locally restricted trees. II
• The Expected order of a Random Permutation
• The height of random binary unlabelled trees
• The number of trees
• The On-Line Encyclopedia of Integer Sequences

Cited in

(27)

• On the number of unary-binary tree-like structures with restrictions on the unary height
• Enumeration and asymptotics of restricted compositions having the same number of parts
• \(k\)-protected vertices in unlabeled rooted plane trees
• Distinct fringe subtrees in random trees
• Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models
• Counting phylogenetic networks
• Associative and commutative tree representations for Boolean functions
• Quantification and statistical analysis of topological features of recursive trees
• The shape of random tanglegrams
• Psi-series method for equality of random trees and quadratic convolution recurrences
• On the number of vertices of each rank in phylogenetic trees and their generalizations
• On symmetries in phylogenetic trees
• The distribution of height and diameter in random non-plane binary trees
• Asymptotically normal distribution of some tree families relevant for phylogenectics, and of partitions without singletons
• scientific article; zbMATH DE number 871916 (Why is no real title available?)
• The isometry group of phylogenetic tree space is $S_n$
• On Symmetries of Non-Plane Trees in a Non-Uniform Model
• A central limit theorem for additive functionals of increasing trees
• Symmetrization of Jordan dialgebras
• Diagonal Asymptotics for Products of Combinatorial Classes
• Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
• Counting general phylogenetic networks
• Distribution of tree parameters by martingale approach
• The distribution of the number of automorphisms of random trees
• Symmetry in randomness: additive functionals and symmetries of random trees and tree-like graphs
• The likely maximum size of twin subtrees in a large random tree
• The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Isomorphism and symmetries in random phylogenetic trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3402055)