Back close

On complexity of transforming strings

Publisher : Proceedings of 11th International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010

Campus : Amritapuri

School : School of Engineering

Department : Computer Science

Year : 2010

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.

Admissions Apply Now