The binary perfect phylogeny with persistent characters

In this paper we propose a graph-based solution of the problem of the reconstruction of the persistent perfect phylogeny (in short P-PP problem) that is obtained by restating the problem as a variant of the Incomplete Directed Perfect Phylogeny, called Incomplete Perfect Phylogeny with Persistent Completion (IP-PP problem). We show a polynomial-time algorithm that finds a solution for the input matrices described by an e-empty conflict-graph. Then we use it to develop an optimized version of the exact algorithm, having a a worst time complexity that is polynomial in the number n of rows of the matrix and exponential in the number m of characters. An experimental analysis shows that the new optimized version outperforms the previously proposed algorithm and has a wider applicability, since it can solve all input matrices within fixed time bounds, while the previous algorithm was not able to finish on some of them.