Combinatorial perspectives on Dollo-k characters in phylogenetics

DOI10.1016/J.AAM.2021.102252MaRDI QIDQ820928zbMATH OpenOpenAlexFDO

Authors Mareike Fischer, Kristina Wicke, Remco Bouckaert

Publication date 29 September 2021

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

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

zbMATH Keywords

Dollo parsimonyFitch algorithmpersistent charactersSackin indexspanning trees

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: Recently, the perfect phylogeny model with persistent characters has attracted great attention in the literature. It is based on the assumption that complex traits or characters can only be gained once and lost once in the course of evolution. Here, we consider a generalization of this model, namely Dollo parsimony, that allows for multiple character losses. More precisely, we take a combinatorial perspective on the notion of Dollo-$k$ characters, i.e. traits that are gained at most once and lost precisely $k$ times throughout evolution. We first introduce an algorithm based on the notion of spanning subtrees for finding a Dollo-$k$ labeling for a given character and a given tree in linear time. We then compare persistent characters (consisting of the union of Dollo-0 and Dollo-1 characters) and general Dollo-$k$ characters. While it is known that there is a strong connection between Fitch parsimony and persistent characters, we show that Dollo parsimony and Fitch parsimony are in general very different. Moreover, while it is known that there is a direct relationship between the number of persistent characters and the Sackin index of a tree, a popular index of tree balance, we show that this relationship does not generalize to Dollo-$k$ characters. In fact, determining the number of Dollo-$k$ characters for a given tree is much more involved than counting persistent characters, and we end this manuscript by introducing a recursive approach for the former. This approach leads to a polynomial time algorithm for counting the number of Dollo-$k$ characters, and both this algorithm as well as the algorithm for computing Dollo-$k$ labelings are publicly available in the Babel package for BEAST 2.

Recommendations

• Combinatorial views on persistent characters in phylogenetics
• When and how the perfect phylogeny model explains evolution
• Species-Driven Persistent Phylogeny
• The binary perfect phylogeny with persistent characters
• A colored graph approach to perfect phylogeny with persistent characters

Cites work

• A colored graph approach to perfect phylogeny with persistent characters
• Combinatorial views on persistent characters in phylogenetics
• Dated Ancestral Trees from Binary Trait Data and Their Application to the Diversification of Languages
• Reducibility among combinatorial problems
• The binary perfect phylogeny with persistent characters

Cited in

(4)

• Combinatorial views on persistent characters in phylogenetics
• Genomic tableaux and combinatorial K-theory
• Leveraging constraints plus dynamic programming for the large Dollo parsimony problem
• A Sankoff-Rousseau-like algorithm for minimizing lateral gene transfers and losses on single origin characters

Describes a project that uses

Uses Software

• BEAST
• bioperl
• SPhyR

This page was built for publication: Combinatorial perspectives on Dollo-\(k\) characters in phylogenetics

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