  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.
