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.
The binary perfect phylogeny with persistent characters
C. Braghin;G. Trucco
2012
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
TCS8913.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
555.89 kB
Formato
Adobe PDF
|
555.89 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.