Paper Info
Title
Preventing undesirable bonds between DNA codewords
Abstract
The input data for DNA computing must be encoded into the form of single or double DNA strands. As complementary parts of single strands can bind together forming a double-stranded DNA sequence, one has to impose restrictions on these sets of DNA words (=languages) to prevent them from interacting in undesirable ways. We recall a list of known properties of DNA languages which are free of certain types of undesirable bonds. Then we introduce a general framework in which we can characterize each of these properties by a solution of a uniform formal language inequation. This characterization allows us among others to construct (i) a uniform algorithm deciding in polynomial time whether a given DNA language possesses any of the studied properties, and (ii) in many cases also an algorithm deciding whether a given DNA language is maximal with respect to the desired property.
Year
DOI
Venue
2004
10.1007/11493785_16
DNA
Keywords
Field
DocType
dna codewords,undesirable bond,double-stranded dna sequence,single strand,uniform algorithm,dna computing,undesirable way,dna language,uniform formal language inequation,double dna strand,dna word,polynomial time,dna sequence,formal language
Discrete mathematics,Combinatorics,Formal language,Inequation,DNA,DNA sequencing,Regular language,Time complexity,Mathematics,DNA computing
Conference
Volume
ISSN
ISBN
3384
0302-9743
3-540-26174-5
Citations 
PageRank 
References 
5
0.54
8
Authors
3
Name
Order
Citations
PageRank
Lila Kari11123124.45
Stavros Konstantinidis228331.10
Petr Sosík347968.66