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.
|Titolo:||The binary perfect phylogeny with persistent characters|
|Data di pubblicazione:||set-2012|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Citazione:||The binary perfect phylogeny with persistent characters / P. Bonizzoni, A.P. Carrieri, R. Dondi, G. Trucco. ((Intervento presentato al 13. convegno Italian Conference on Theoretical Computer Science (ICTCS) tenutosi a Varese nel 2012.|
|Appare nelle tipologie:||14 - Intervento a convegno non pubblicato|