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.

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

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

Cited in

(13)

• Some families of trees arising in permutation analysis
• Isomorphism and symmetries in random phylogenetic trees
• On trees, tanglegrams, and tangled chains
• scientific article; zbMATH DE number 5998808 (Why is no real title available?)
• Counting tanglegrams with species
• Generalized Regularity and the Symmetry of Branches of Botanological Networks
• Some simple varieties of trees arising in permutation analysis
• Evolution maps and symmetry
• Asymptotically normal distribution of some tree families relevant for phylogenectics, and of partitions without singletons
• Distribution of the Symmetric Difference Metric on Phylogenetic Trees
• On Symmetries of Non-Plane Trees in a Non-Uniform Model
• Sampling planar tanglegrams and pairs of disjoint triangulations
• On the enumeration of tanglegrams and tangled chains

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)