The binary perfect phylogeny with persistent characters
From MaRDI portal
Publication:714807
DOI10.1016/J.TCS.2012.05.035zbMATH Open1250.92035arXiv1110.6739OpenAlexW2072719910MaRDI QIDQ714807FDOQ714807
Authors: Paola Bonizzoni, Chiara Braghin, Riccardo Dondi, Gabriella Trucco 
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1110.6739
Recommendations
Applications of graph theory (05C90) Problems related to evolution (92D15) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Introduction to algorithms
- Efficient algorithms for inferring evolutionary trees
- Incomplete Directed Perfect Phylogeny
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- A linear-time algorithm for the perfect phylogeny haplotype problem
- An Important Connection Between Network Motifs and Parsimony Models
Cited In (10)
- Combinatorial perspectives on Dollo-\(k\) characters in phylogenetics
- Incomplete directed perfect phylogeny in linear time
- Mathematical models and solutions for the analysis of human genotypes
- Character-based phylogeny construction and its application to tumor evolution
- Combinatorial views on persistent characters in phylogenetics
- A colored graph approach to perfect phylogeny with persistent characters
- Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees
- When and how the perfect phylogeny model explains evolution
- Incomplete Directed Perfect Phylogeny
- 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)
