Enumeration of coalescent histories for caterpillar species trees and p-pseudocaterpillar gene trees

DOI10.1016/J.AAM.2021.102265MaRDI QIDQ820935zbMATH OpenOpenAlexFDO

Authors Egor Alimpiev, Noah A. Rosenberg

Publication date 29 September 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

phylogeneticsCatalan numbersDyck pathscoalescent historiesmonotonic paths

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15) Exact enumeration problems, generating functions (05A15) Taxonomy, cladistics, statistics in mathematical biology (92B10)

Abstract: For a fixed set $X$ containing $n$ taxon labels, an ordered pair consisting of a gene tree topology $G$ and a species tree $S$ bijectively labeled with the labels of $X$ possesses a set of coalescent histories -- mappings from the set of internal nodes of $G$ to the set of edges of $S$ describing possible lists of edges in $S$ on which the coalescences in $G$ take place. Enumerations of coalescent histories for gene trees and species trees have produced suggestive results regarding the pairs $(G,S)$ that, for a fixed $n$, have the largest number of coalescent histories. We define a class of 2-cherry binary tree topologies that we term $p$-pseudocaterpillars, examining coalescent histories for non-matching pairs $(G,S)$, in the case in which $S$ has a caterpillar shape and $G$ has a $p$-pseudocaterpillar shape. Using a construction that associates coalescent histories for $(G,S)$ with a class of "roadblocked" monotonic paths, we identify the $p$-pseudocaterpillar labeled gene tree topology that, for a fixed caterpillar labeled species tree topology, gives rise to the largest number of coalescent histories. The shape that maximizes the number of coalescent histories places the "second" cherry of the $p$-pseudocaterpillar equidistantly from the root of the "first" cherry and from the tree root. A symmetry in the numbers of coalescent histories for $p$-pseudocaterpillar gene trees and caterpillar species trees is seen to exist around the maximizing value of the parameter $p$. The results provide insight into the factors that influence the number of coalescent histories possible for a given gene tree and species tree.

Recommendations

• Enumeration of compact coalescent histories for matching gene trees and species trees
• Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees
• Coalescent histories for discordant gene trees and species trees
• Computing the probability of gene trees concordant with the species tree in the multispecies coalescent
• Determining species tree topologies from clade probabilities under the coalescent
• Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherries
• Extracting coevolving characters from a tree of species
• Algorithmic improvements to species delimitation and phylogeny estimation under the multispecies coalescent
• On coalescence analysis using genealogy rooted trees

Cites work

• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• A \textit{Mathematica} version of Zeilberger's algorithm for proving binomial coefficient identities
• Analytic combinatorics
• Catalan Numbers
• Catalan's trapezoids
• Coalescent histories for discordant gene trees and species trees
• Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherries
• Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees
• There are no caterpillars in a wicked forest

Cited in

(8)

• Enumeration of lonely pairs of gene trees and species trees by means of antipodal cherries
• Enumeration of compact coalescent histories for matching gene trees and species trees
• The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
• Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees
• There are no caterpillars in a wicked forest
• A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees
• The distributions under two species-tree models of the total number of ancestral configurations for matching gene trees and species trees
• How to Obtain the Complete List of Caterpillars

This page was built for publication: Enumeration of coalescent histories for caterpillar species trees and \(p\)-pseudocaterpillar gene trees

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