Publication Type:

Conference Paper

Source:

Proceedings of 11th International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, CSREA (2010)

URL:

https://www.researchgate.net/profile/Bhadrachalam_Chitturi/publication/221051413_On_Complexity_of_Transforming_Strings/links/57b453c108ae19a365fae14b.pdf

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.

Cite this Research Publication

Dr. Bhadrachalam Chitturi, “On complexity of transforming strings”, in Proceedings of 11th International Conference in Bioinformatics and Computational Biology, BIOCOMP 2010, 2010.

207
PROGRAMS
OFFERED
6
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS