On the design of codes for DNA computing

Olgica Milenkovic, Navin Kashyap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we describe a broad class of problems arising in the context of designing codes for DNA computing. We primarily focus on design considerations pertaining to the phenomena of secondary structure formation in single-stranded DNA molecules and non-selective cross-hybridization. Secondary structure formation refers to the tendency of single-stranded DNA sequences to fold back upon themselves, thus becoming inactive in the computation process, while non-selective cross-hybridization refers to unwanted pairing between DNA sequences involved in the computation process. We use the Nussinov-Jacobson algorithm for secondary structure prediction to identify some design criteria that reduce the possibility of secondary structure formation in a code-word. These design criteria can be formulated in terms of constraints on the number of complementary pair matches between a DNA codeword and some of its shifts. We provide a sampling of simple techniques for enumerating and constructing sets of DNA sequences with properties that inhibit non-selective hybridization and secondary structure formation. Novel constructions of such codes include using cyclic reversible extended Goppa codes, generalized Hadamard matrices, and a binary mapping approach. Cyclic code constructions are particularly useful in light of the fact we prove that the presence of a cyclic structure reduces the complexity of testing DNA codes for secondary structure formation.

Original languageEnglish (US)
Title of host publicationCoding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers
PublisherSpringer
Pages100-119
Number of pages20
ISBN (Print)3540354816, 9783540354819
DOIs
StatePublished - 2006
Externally publishedYes
EventInternational Workshop on Coding and Cryptography, WCC 2005 - Bergen, Norway
Duration: Mar 14 2005Mar 18 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3969 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Workshop on Coding and Cryptography, WCC 2005
Country/TerritoryNorway
CityBergen
Period3/14/053/18/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On the design of codes for DNA computing'. Together they form a unique fingerprint.

Cite this