A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees

DOI10.1016/J.DAM.2023.09.033zbMATH Open1530.92156arXiv2111.10456OpenAlexW3214928829MaRDI QIDQ6180645FDOQ6180645

Authors: Egor Lappo, Noah A. Rosenberg 

Publication date: 2 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: To a given gene tree topology $G$ and species tree topology $S$ with leaves labeled bijectively from a fixed set $X$, one can associate a set of ancestral configurations, each of which encodes a set of gene lineages that can be found at a given node of a species tree. We introduce a lattice structure on ancestral configurations, studying the directed graphs that provide graphical representations of lattices of ancestral configurations. For a matching gene tree topology and species tree topology, we present a method for defining the digraph of ancestral configurations from the tree topology by using iterated cartesian products of graphs. We show that a specific set of paths on the digraph of ancestral configurations is in bijection with the set of labeled histories -- a well-known phylogenetic object that enumerates possible temporal orderings of the coalescences of a tree. For each of a series of tree families, we obtain closed-form expressions for the number of labeled histories by using this bijection to count paths on associated digraphs. Finally, we prove that our lattice construction extends to nonmatching tree pairs, and we use it to characterize pairs $(G,S)$ having the maximal number of ancestral configurations for a fixed $G$. We discuss how the construction provides new methods for performing enumerations of combinatorial aspects of gene and species trees.

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

Recommendations

• On the number of non-equivalent ancestral configurations for matching 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
• The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
• Coalescent histories for discordant gene trees and species trees
• Enumeration of compact coalescent histories for matching gene trees and species trees

zbMATH Keywords

latticespartial ordersgene treesancestral configurationsspecies treeslabeled histories

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15) Trees (05C05)

Cites Work

• Phylogeny. Discrete and random processes in evolution
• Title not available (Why is that?)
• Lattice Theory: Foundation
• Title not available (Why is that?)
• Graph multiplication
• The probabilities of rooted tree-shapes generated by random bifurcation
• Properties of phylogenetic trees generated by Yule-type speciation models
• The probability distribution of ranked gene trees on a species tree
• 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
• Enumeration of coalescent histories for caterpillar species trees and \(p\)-pseudocaterpillar gene trees
• The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
• Enumeration of binary trees compatible with a perfect phylogeny
• Combinatorial and stochastic properties of ranked tree‐child networks
• Introduction to lattice theory with computer science applications
• On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees
• The distributions under two species-tree models of the total number of ancestral configurations for matching gene trees and species trees

Cited In (1)

• The distributions under two species-tree models of the total number of ancestral configurations for matching gene trees and species trees

This page was built for publication: A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees

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