Paper Info
Title
The binary perfect phylogeny with persistent characters
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 perfect phylogeny 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.
Year
DOI
Venue
2011
10.1016/j.tcs.2012.05.035
Theor. Comput. Sci.
Keywords
DocType
Volume
IP-PP problem,Persistent Perfect Phylogeny,binary perfect phylogeny model,binary perfect phylogeny,incomplete binary matrix,Incomplete Directed Perfect Phylogeny,persistent character,graph operation,graph formulation,P-PP problem,Incomplete Perfect Phylogeny
Journal
454,
ISSN
Citations 
PageRank 
0304-3975
7
0.72
References 
Authors
11
4
Name
Order
Citations
PageRank
Paola Bonizzoni150252.23
Chiara Braghin21058.86
Riccardo Dondi315914.12
Gabriella Trucco46811.86