On symmetries in phylogenetic trees

zbMATH Open1344.05045arXiv1602.07432MaRDI QIDQ311529FDOQ311529

Éric Fusy

Publication date: 13 September 2016

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

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.

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the enumeration of tanglegrams and tangled chains
• Counting tanglegrams with species
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen

Cited In (9)

• On the enumeration of tanglegrams and tangled chains
• Evolution maps and symmetry
• Title not available (Why is that?)
• On Symmetries of Non-Plane Trees in a Non-Uniform Model
• Sampling planar tanglegrams and pairs of disjoint triangulations
• Title not available (Why is that?)
• Generalized Regularity and the Symmetry of Branches of Botanological Networks
• Counting tanglegrams with species
• Distribution of the Symmetric Difference Metric on Phylogenetic 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)