Isomorphism and Symmetries in Random Phylogenetic Trees

2009/01/06 by Miklos Bona, Bona, Miklos, Philippe Flajolet +1
Mathematics · #05A16 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05A16 #msc:60C05

paper · pdf · doi:10.48550/arxiv.0901.0696

14 pages

arxiv created 2009/01/06 · arxiv updated 2009/12/01

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.

Related

• The probability of random trees being isomorphic
• On asymptotic joint distributions of cherries and pitchforks for random phylogenetic trees
• On symmetries in phylogenetic trees
• Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons
• Maximal clades in random binary search trees