The Binary Perfect Phylogeny with Persistent characters
Preprint
Abstract
The near-perfect phylogeny over binary set of characters has been proposed as an extension of the too restrictive model of the perfect phylogeny in order to model biological events such as homoplasy. However the model appears to be too general to model some situations and is computationally inefficient on some instances. In this paper we consider the problem of reconstructing a near-perfect phylogeny where only a type of homoplasy is allowed in the tree: we consider back mutations according to notion of {\em persistency}, that is characters can be gained and lost at most once. The notion of persistency leads to the problem of the Persistent Perfect Phylogeny (referred as P-PPH). By exploring combinatorial properties of the problem we develop an exact algorithm for solving the P-PPH problem that in the worst case runs in time that is exponential in the number of characters, but is polynomial in the number of species. Indeed, we show that the P-PPH problem can be restated as a special case of the Incomplete Perfect Phylogeny, that is finding a completion of characters of an incomplete matrix. Then, we show that this last problem can be reduced to a graph-problem, since the completion of a character corresponds to a graph-operation (reduction) on vertices of a graph. An experimental analysis shows the applicability of the model to incorporate biological complexity due to back mutations events in the data.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Reducing Multi-state to Binary Perfect Phylogeny with Applications to Missing, Removable, Inserted, and Deleted DataLecture Notes in Computer Science, 2010
- Extensions and Improvements to the Chordal Graph Approach to the Multi-state Perfect Phylogeny ProblemLecture Notes in Computer Science, 2010
- A Linear-Time Algorithm for the Perfect Phylogeny Haplotype ProblemAlgorithmica, 2007
- Constructing Near-Perfect Phylogenies with multiple homoplasy eventsBioinformatics, 2006
- A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) ProblemJournal of Computational Biology, 2006
- Incomplete Directed Perfect PhylogenySIAM Journal on Computing, 2004
- Generating samples under a Wright–Fisher neutral model of genetic variationBioinformatics, 2002
- Efficient algorithms for inferring evolutionary treesNetworks, 1991