2011/10/31 by Paola Bonizzoni, Chiara Braghin, Bonizzoni, Paola +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Engineering #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Finance #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.1110.6739
openalex publication_date 2011/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.