Combinatorial views on persistent characters in phylogenetics

DOI10.1016/J.AAM.2020.102046MaRDI QIDQ2182613zbMATH OpenOpenAlexFDO

Authors Kristina Wicke, Mareike Fischer

Publication date 26 May 2020

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

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

zbMATH Keywords

maximum parsimonyFitch algorithmpersistent characterstree balance\(X\)-splitssackin index

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10) Trees (05C05) Enumeration in graph theory (05C30) General biology and biomathematics (92B05)

Abstract: The so-called binary perfect phylogeny with persistent characters has recently been thoroughly studied in computational biology as it is less restrictive than the well known binary perfect phylogeny. Here, we focus on the notion of (binary) persistent characters, i.e. characters that can be realized on a phylogenetic tree by at most one $0ightarrow1$ transition followed by at most one $1ightarrow0$ transition in the tree, and analyze these characters under different aspects. First, we illustrate the connection between persistent characters and Maximum Parsimony, where we characterize persistent characters in terms of the first phase of the famous Fitch algorithm. Afterwards we focus on the number of persistent characters for a given phylogenetic tree. We show that this number solely depends on the balance of the tree. To be precise, we develop a formula for counting the number of persistent characters for a given phylogenetic tree based on an index of tree balance, namely the Sackin index. Lastly, we consider the question of how many (carefully chosen) binary characters together with their persistence status are needed to uniquely determine a phylogenetic tree and provide an upper bound for the number of characters needed.

Recommendations

• Combinatorial perspectives on Dollo-\(k\) characters in phylogenetics
• The binary perfect phylogeny with persistent characters
• scientific article; zbMATH DE number 637307
• Research in Computational Molecular Biology
• A colored graph approach to perfect phylogeny with persistent characters
• The combinatorics of evolutionary trees---a survey
• Remarks on Hadamard conjugation and combinatorial phylogenetics
• The compatibility of binary characters on phylogenetic networks: Complexity and parameterized algorithms
• Combinatorial properties of phylogenetic diversity indices
• On the combinatorics of rooted binary phylogenetic trees

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A colored graph approach to perfect phylogeny with persistent characters
• Phylogeny. Discrete and random processes in evolution
• The Steiner problem in phylogeny is NP-complete
• The binary perfect phylogeny with persistent characters

Cited in

(3)

• Combinatorial perspectives on Dollo-\(k\) characters in phylogenetics
• Sharp upper and lower bounds on a restricted class of convex characters
• A colored graph approach to perfect phylogeny with persistent characters

Describes a project that uses

Uses Software

• SackinMinimizer
• SPhyR
• Mathematica

This page was built for publication: Combinatorial views on persistent characters in phylogenetics

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