Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-31
Computer Science
Data Structures and Algorithms
13 pages, 3 figures
Scientific paper
The near-perfect phylogeny over binary set of characters has been proposed as an extension of the too restrictive model of the perfect phylogeny in order to model biological events such as homoplasy. However the model appears to be too general to model some situations and is computationally inefficient on some instances. In this paper we consider the problem of reconstructing a near-perfect phylogeny where only a type of homoplasy is allowed in the tree: we consider back mutations according to notion of {\em persistency}, that is characters can be gained and lost at most once. The notion of persistency leads to the problem of the Persistent Perfect Phylogeny (referred as P-PPH). By exploring combinatorial properties of the problem we develop an exact algorithm for solving the P-PPH problem that in the worst case runs in time that is exponential in the number of characters, but is polynomial in the number of species. Indeed, we show that the P-PPH problem can be restated as a special case of the Incomplete Perfect Phylogeny, that is finding a completion of characters of an incomplete matrix. Then, we show that this last problem can be reduced to a graph-problem, since the completion of a character corresponds to a graph-operation (reduction) on vertices of a graph. An experimental analysis shows the applicability of the model to incorporate biological complexity due to back mutations events in the data.
Bonizzoni Paola
Braghin Chiara
Dondi Riccardo
Trucco Gabriella
No associations
LandOfFree
The Binary Perfect Phylogeny with Persistent characters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Binary Perfect Phylogeny with Persistent characters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Binary Perfect Phylogeny with Persistent characters will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-147419