Publication

Abstract : Genes can be modeled by strings defined over a finite alphabet. Pevzner and Waterman posed various problems pertaining to DNA (a string with an alphabet of size four), i.e. DNA physical mapping, DNA sequencing, and DNA sequence comparison (mimicking genetic mutations). Genetic mutations, the changes that happen within a gene, can be modeled by operations like transpositions and reversals over strings. The complexity of transforming strings under such operations is of primary interest. We show that the string transformation distance under cut-and-paste moves, prefix reversal/transpositions, and translocations is NP-complete.