Publication Type:

Journal Article

Source:

Discrete Mathematics, Algorithms and Applications, Volume 03, Number 03, p.269-286 (2011)

URL:

http://www.worldscientific.com/doi/abs/10.1142/S1793830911001206

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.

Cite this Research Publication

Dr. Bhadrachalam Chitturi, “A note on complexity of genetic mutations”, Discrete Mathematics, Algorithms and Applications, vol. 03, pp. 269-286, 2011.

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