{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:08:47Z","timestamp":1762297727083},"reference-count":27,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s1793830911001206","type":"journal-article","created":{"date-parts":[[2011,5,11]],"date-time":"2011-05-11T06:42:17Z","timestamp":1305096137000},"page":"269-286","source":"Crossref","is-referenced-by-count":9,"title":["A NOTE ON COMPLEXITY OF GENETIC MUTATIONS"],"prefix":"10.1142","volume":"03","author":[{"given":"BHADRACHALAM","family":"CHITTURI","sequence":"first","affiliation":[{"name":"Department of Computer Science, Amrita Vishwa Vidyapeetham University, Amritapuri Campus, Clappana P. O., Kollam 690525, Kerala, India"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00175"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1069"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2005.48"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9077-1"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.045"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_30"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197331995"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103971"},{"key":"rf13","first-page":"105","volume":"16","author":"Cohen D. S.","journal-title":"Discrete Appl. Math."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.01.011"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24597-1_16"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322090"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90068-2"},{"key":"rf19","first-page":"473","volume":"3341","author":"Goldstein A.","journal-title":"Lecture Notes Comput. Sci."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00092-9"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00061-3"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0874"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1137\/060664252"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14553-7_7"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_50"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.05.011"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48686-0_7"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103433550"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.01.010"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02017-9_10"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.078"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830911001206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:12:41Z","timestamp":1565194361000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830911001206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":27,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1142\/S1793830911001206"],"URL":"https:\/\/doi.org\/10.1142\/s1793830911001206","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]}}}