DNA codes that avoid secondary structures

Olgica Milenkovic, Navin Kashyap

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

Abstract

In this paper, we consider the problem of designing codewords for DNA storage systems and DNA computers that are unlikely to fold back onto themselves to form undesirable secondary structures. Secondary structure formation causes a DNA codeword to become less active chemically, thus rendering it useless for the purpose of DNA computing. It also defeats the read-back mechanism in a DNA storage system, so that information stored in such a folded DNA codeword cannot be retrieved. Based on some simple properties of a dynamic-programming algorithm, known as Nussinov's method, which is an effective predictor of secondary structure given the sequence of bases in a DNA codeword, we identify some design criteria that reduce the possibility of secondary structure formation in a codeword. These design criteria can be formulated in terms of the requirement that the Watson-Crick distance between a DNA codeword and a number of its shifts be larger than a given threshold. This paper addresses both the issue of enumerating DNA sequences with such properties and the problem of practical DNA code construction.

Original languageEnglish (US)
Title of host publicationProceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05
Pages288-292
Number of pages5
DOIs
StatePublished - 2005
Externally publishedYes
Event2005 IEEE International Symposium on Information Theory, ISIT 05 - Adelaide, Australia
Duration: Sep 4 2005Sep 9 2005

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2005
ISSN (Print)2157-8099

Other

Other2005 IEEE International Symposium on Information Theory, ISIT 05
Country/TerritoryAustralia
CityAdelaide
Period9/4/059/9/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'DNA codes that avoid secondary structures'. Together they form a unique fingerprint.

Cite this