On symmetries in phylogenetic trees

MaRDI QIDQ311529zbMATH OpenFDO

Authors Éric Fusy

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.07432, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p25

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bijectionphylogenetic treesrandom generationtanglegrams

Mathematics Subject Classification ID

Trees (05C05)

Abstract: Billey et al. [arXiv:1507.04976] have recently discovered a surprisingly simple formula for the number $a_n(sigma)$ of leaf-labelled rooted non-embedded binary trees (also known as phylogenetic trees) with $ngeq1$ leaves, fixed (for the relabelling action) by a given permutation $sigmainfrak{S}_n$. Denoting by $lambdavdashn$ the integer partition giving the sizes of the cycles of $sigma$ in non-increasing order, they show by a guessing/checking approach that if $lambda$ is a binary partition (it is known that $a_n(sigma)=0$ otherwise), then ${\displaystyle }$ a_n(sigma)=prod_{i=2}^{ell(lambda)}(2(lambda_i+cdots+lambda_{ell(lambda)})-1), ${\displaystyle }$ and they derive from it a formula and random generation procedure for tanglegrams (and more generally for tangled chains). Our main result is a combinatorial proof of the formula, which yields a simplification of the random sampler for tangled chains.

Review text

Summary: \textit{S. Billey} et al. [``On the enumeration of tanglegrams and tangled chains, Preprint, \url{arXiv:1507.04976}] have recently discovered a surprisingly simple formula for the number \(a_n(\sigma)\) of leaf-labelled rooted non-embedded binary trees (also known as phylogenetic trees) with \(n\geqslant 1\) leaves, fixed (for the relabelling action) by a given permutation \(\sigma\in\mathfrak{S}_n\). Denoting by \(\lambda\vdash n\) the integer partition giving the sizes of the cycles of \(\sigma\) in non-increasing order, they show by a guessing/checking approach that if \(\lambda\) is a binary partition (it is known that \(a_n(\sigma)=0\) otherwise), then \[ a_n(\sigma)=\prod_{i=2}^{\ell(\lambda)}(2(\lambda_i+\cdots+\lambda_{\ell(\lambda)})-1), \] and they derive from it a formula and random generation procedure for tanglegrams (and more generally for tangled chains). Our main result is a combinatorial proof of the formula for \(a_n(\sigma)\), which yields a simplification of the random sampler for tangled chains.

Recommendations

• On trees, tanglegrams, and tangled chains
• On the enumeration of tanglegrams and tangled chains
• Isomorphism and symmetries in random phylogenetic trees
• Computation of the expected number of leaves in a tree having a given automorphism, and related topics
• Counting tanglegrams with species

Cites work

• Counting tanglegrams with species
• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• On the enumeration of tanglegrams and tangled chains

Cited in

(16)

• Computation of the expected number of leaves in a tree having a given automorphism, and related topics
• Counting tanglegrams with species
• Some families of trees arising in permutation analysis
• scientific article; zbMATH DE number 5998808 (Why is no real title available?)
• Generalized Regularity and the Symmetry of Branches of Botanological Networks
• Isomorphism and symmetries in random phylogenetic trees
• On the enumeration of tanglegrams and tangled chains
• Distribution of the Symmetric Difference Metric on Phylogenetic Trees
• Asymptotically normal distribution of some tree families relevant for phylogenectics, and of partitions without singletons
• Evolution maps and symmetry
• On trees, tanglegrams, and tangled chains
• On Symmetries of Non-Plane Trees in a Non-Uniform Model
• Some simple varieties of trees arising in permutation analysis
• Sampling planar tanglegrams and pairs of disjoint triangulations
• The flip graph on planar layouts of a planar tanglegram is almost a hypercube
• An algorithm for uniform generation of unlabeled (Pólya) trees

This page was built for publication: On symmetries in phylogenetic trees

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