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

Derek Smith, Roberto Montemanni

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)311 - 326
Number of pages15
JournalJournal of Mathematical Modelling and Algorithms
Issue number3
Publication statusPublished - 1 Sept 2008


  • DNA codes
  • lower bounds
  • heuristic algorithms
  • variable neighbourhood search


Dive into the research topics of 'Construction of Constant GC-Content DNA Codes via a Variable Neighbourhood Search Algorithm'. Together they form a unique fingerprint.

Cite this