Paper Info
Title
Sticky-free and overhang-free DNA languages
Abstract
An essential step of any DNA computation is encoding the input data on single or double DNA strands. Due to the biochemical properties of DNA, complementary single strands can bind to one another forming double-stranded DNA. Consequently, data-encoding DNA strands can sometimes interact in undesirable ways when used in computations. It is crucial thus to analyze properties that guard against such phenomena and study sets of sequences that ensure that no unwanted bindings occur during any computation. This paper formalizes and investigates properties of DNA languages that guarantee their robusteness during computations. After defining and investigating several types of DNA languages possessing good encoding properties, such as sticky-free and overhang-free languages, we give algorithms for deciding whether regular DNA languages are invariant under bio-operations. We also give a method for constructing DNA languages that, in addition to being invariant and sticky-free, possess error-detecting properties. Finally, we present the results of running tests that check whether several known gene languages (the set of genes of a given organism) as well as the input DNA languages used in Adleman's DNA computing experiment, have the defined properties.
Year
DOI
Venue
2003
10.1007/s00236-003-0118-7
Acta Inf.
Keywords
Field
DocType
Theoretical DNA computing,DNA encodings,codes,formal languages.
Gene,Formal language,Computer science,DNA,Theoretical computer science,Invariant (mathematics),Encoding (memory),DNA computing,Computation
Journal
Volume
Issue
ISSN
40
2
0001-5903
Citations 
PageRank 
References 
24
1.69
10
Authors
4
Name
Order
Citations
PageRank
Lila Kari11123124.45
Stavros Konstantinidis228331.10
Elena Losseva3443.48
Geoff Wozniak4252.05