Paper Info
Title
On properties of bond-free DNA languages
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
2005
10.1016/j.tcs.2004.12.032
Theor. Comput. Sci.
Keywords
DocType
Volume
undesirable bond,double-stranded DNA sequence,single strand,uniform algorithm,bond-free DNA language,undesirable way,DNA language,DNA word,double DNA strand,68Q22,DNA computing,68Q50,Binary word operation,uniform formal language inequation
Journal
334
Issue
ISSN
Citations 
1-3
Theoretical Computer Science
15
PageRank 
References 
Authors
0.90
9
3
Name
Order
Citations
PageRank
Lila Kari11123124.45
Stavros Konstantinidis228331.10
Petr Sosík347968.66