  The perfect phylogeny is one of the most used models in different areas of
computational biology. In this paper we consider the problem of the Persistent
Perfect Phylogeny (referred as P-PP) recently introduced to extend the perfect
phylogeny model allowing persistent characters, that is characters can be
gained and lost at most once. We define a natural generalization of the P-PP
problem obtained by requiring that for some pairs (character, species), neither
the species nor any of its ancestors can have the character. In other words,
some characters cannot be persistent for some species. This new problem is
called Constrained P-PP (CP-PP).
  Based on a graph formulation of the CP-PP problem, we are able to provide a
polynomial time solution for the CP-PP problem for matrices having an empty
conflict-graph. In particular we show that all such matrices admit a persistent
perfect phylogeny in the unconstrained case. Using this result, we develop a
parameterized algorithm for solving the CP-PP problem where the parameter is
the number of characters. A preliminary experimental analysis of the algorithm
shows that it performs efficiently and it may analyze real haplotype data not
conforming to the classical perfect phylogeny model.
