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.

This publication has 8 references indexed in Scilit: