Asymptotic properties of the number of matching coalescent histories for caterpillar-like families of species trees

preprint2015arXivOpen access

Abstract

Coalescent histories provide lists of species tree branches on which gene tree coalescences can take place, and their enumerative properties assist in understanding the computational complexity of calculations central in the study of gene trees and species trees. Here, we solve an enumerative problem left open by Rosenberg (IEEE/ACM Transactions on Computational Biology and Bioinformatics 10: 1253-1262, 2013) concerning the number of coalescent histories for gene trees and species trees with a matching labeled topology that belongs to a generic caterpillar-like family. By bringing a generating function approach to the study of coalescent histories, we prove that for any caterpillar-like family with seed tree tt, the sequence (hn)n≥0(h_n)_{n\geq 0} describing the number of matching coalescent histories of the nnth tree of the family grows asymptotically as a constant multiple of the Catalan numbers. Thus, hn∼βtcnh_n \sim β_t c_n, where the asymptotic constant βt>0β_t > 0 depends on the shape of the seed tree tt. The result extends a claim demonstrated only for seed trees with at most 8 taxa to arbitrary seed trees, expanding the set of cases for which detailed enumerative properties of coalescent histories can be determined. We introduce a procedure that computes from tt the constant βtβ_t as well as the algebraic expression for the generating function of the sequence (hn)n≥0(h_n)_{n\geq 0}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.