Combinatorial perspectives on Dollo-k characters in phylogenetics

• Published in: Advances in applied mathematics 2021-10, Vol.131, p.102252, Article 102252
• Main Authors: Bouckaert, Remco, Fischer, Mareike, Wicke, Kristina
• Format: Article
• Language: English
• Subjects: Dollo parsimony; Fitch algorithm; Persistent characters; Sackin index; Spanning trees
• ISSN: 0196-8858; 1090-2074
• DOI: 10.1016/j.aam.2021.102252

•Generalization of persistent characters to Dollo-k characters.•Linear time spanning tree algorithm for finding a Dollo-k labelling of given character.•Polynomial time algorithm to calculate the number of Dollo-k characters for a tree.•Proof that the difference between Dollo and Fitch parsimony can be arbitrarily large. 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 labelling 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 labellings are publicly available in the Babel package for BEAST 2.