The binary perfect phylogeny with persistent characters

DOI10.1016/J.TCS.2012.05.035MaRDI QIDQ714807zbMATH OpenOpenAlexFDO

Authors Paola Bonizzoni, Chiara Braghin, Riccardo Dondi, Gabriella Trucco

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Computational methods for problems pertaining to biology (92-08)

Abstract: The binary perfect phylogeny model is too restrictive to model biological events such as back mutations. In this paper we consider a natural generalization of the model that allows a special type of back mutation. We investigate the problem of reconstructing a near perfect phylogeny over a binary set of characters where characters are persistent: characters can be gained and lost at most once. Based on this notion, we define the problem of the Persistent Perfect Phylogeny (referred as P-PP). We restate the P-PP problem as a special case of the Incomplete Directed Perfect Phylogeny, called Incomplete Perfect Phylogeny with Persistent Completion, (refereed as IP-PP), where the instance is an incomplete binary matrix M having some missing entries, denoted by symbol ?, that must be determined (or completed) as 0 or 1 so that M admits a binary perfect phylogeny. We show that the IP-PP problem can be reduced to a problem over an edge colored graph since the completion of each column of the input matrix can be represented by a graph operation. Based on this graph formulation, we develop an exact algorithm for solving the P-PP problem that is exponential in the number of characters and polynomial in the number of species.

Recommendations

• A colored graph approach to perfect phylogeny with persistent characters
• Species-Driven Persistent Phylogeny
• scientific article; zbMATH DE number 1615277
• Incomplete Directed Perfect Phylogeny
• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees

Cites work

• A linear-time algorithm for the perfect phylogeny haplotype problem
• An Important Connection Between Network Motifs and Parsimony Models
• Efficient algorithms for inferring evolutionary trees
• Incomplete Directed Perfect Phylogeny
• Introduction to algorithms
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Cited in

(10)

• Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
• Incomplete Directed Perfect Phylogeny
• Incomplete directed perfect phylogeny in linear time
• Combinatorial perspectives on Dollo-\(k\) characters in phylogenetics
• A colored graph approach to perfect phylogeny with persistent characters
• Combinatorial views on persistent characters in phylogenetics
• When and how the perfect phylogeny model explains evolution
• Character-based phylogeny construction and its application to tumor evolution
• Mathematical models and solutions for the analysis of human genotypes
• Hypothesis testing in perfect phylogeny for a bounded number of characters

This page was built for publication: The binary perfect phylogeny with persistent characters

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