TY - GEN
T1 - On the design of codes for DNA computing
AU - Milenkovic, Olgica
AU - Kashyap, Navin
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33746718103&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746718103&partnerID=8YFLogxK
U2 - 10.1007/11779360_9
DO - 10.1007/11779360_9
M3 - Conference contribution
AN - SCOPUS:33746718103
SN - 3540354816
SN - 9783540354819
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 100
EP - 119
BT - Coding and Cryptography - International Workshop, WCC 2005, Revised Selected Papers
PB - Springer
T2 - International Workshop on Coding and Cryptography, WCC 2005
Y2 - 14 March 2005 through 18 March 2005
ER -