Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-18T01:06:44.543Z Has data issue: false hasContentIssue false

Isomorphism and Symmetries in Random Phylogenetic Trees

Published online by Cambridge University Press:  14 July 2016

Miklós Bóna*
Affiliation:
University of Florida
Philippe Flajolet*
Affiliation:
INRIA
*
∗ Postal address: Department of Mathematics, University of Florida, 358 Little Hall, PO Box 118105, Gainesville, FL 32611–8105, USA.
∗∗ Postal address: Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France. Email address: philippe.flajolet@inria.fr
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.

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.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2009