Publication

Abstract : Genes, the functional segments of DNA, can be modeled akin to DNA by quaternary strings. Pevzner and Waterman posed various problems pertaining to DNA, e.g. DNA physical mapping, DNA sequencing, and DNA sequence comparison. DNA sequence comparison methods aim to compute the genetic mutation distance. Genetic mutation, a change that happens within a gene, can be modeled by an operation like a transposition or a reversal over a string where a string models a gene. The complexity of transforming quaternary strings under a given operation is equivalent to the complexity of computing the corresponding genetic mutation distance. We show that the string transformation distance under signed prefix reversals, translocations and transreversals is NP-complete.