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 perfectphylogeny 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.
The binary perfect phylogeny with persistent characters / P. Bonizzoni, C. Braghin, R. Dondi, G. Trucco. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 454(2012 Oct 05), pp. 51-63.
|Titolo:||The binary perfect phylogeny with persistent characters|
|Parole Chiave:||linear-time algorithm; tree|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||5-ott-2012|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.tcs.2012.05.035|
|Appare nelle tipologie:||01 - Articolo su periodico|