Construction of Constant GC-Content DNA Codes via a Variable Neighbourhood Search Algorithm

Derek Smith, Roberto Montemanni

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid


DNA codes are sets of words of fixed length n over the alphabet {A,C,G,T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper the construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework. The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests.
Iaith wreiddiolSaesneg
Tudalennau (o-i)311 - 326
Nifer y tudalennau15
CyfnodolynJournal of Mathematical Modelling and Algorithms
Rhif cyhoeddi3
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 1 Medi 2008

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Construction of Constant GC-Content DNA Codes via a Variable Neighbourhood Search Algorithm'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn