title: Hairpin formation in DNA computation presents limits for large NP-complete problems.
abstract: Recently, several DNA computing paradigms for NP-complete problems were presented, especially for the 3-SAT problem. Can the present paradigms solve more than just trivial instances of NP-complete problems? In this paper we show that with high probability potentially deleterious features such as severe hairpin loops would be likely to arise. If DNA strand x of length n and the 'complement' of the reverse of x have l match bases, then x forms a hairpin loop and is called a (n,l)-hairpin format. Let gamma=2l/n. Then gamma can be considered as a measurement of the stability of hairpin loops. Let p(n,l) be the probability that a n-mer DNA strand is a (n,l)-hairpin format, and q(n,l)((m)) be the probability that m ones are chosen at random from 4(n) n-mer oligonucleotides such that at least one of the m ones is a (n,l)-hairpin format. Then, q(n,l)((m))=1-(1-p(n,l))(m)=mp(n,l). If we require q(n,l)((m))<a, where a<1, then m<ln(1-a)/ln(1-p(n,l))=a/p(n,l). It means that we can only solve the instances of size m of NP-complete problems. Clearly the greater p(n,l), the smaller m, and the smaller a the smaller m. In this paper, we show p(n,l) is high. Therefore, the present DNA computing paradigms cannot solve large NP-complete problems. For example, if n=20, used in Adleman and Lipton's paradigm, gamma=50% and a=50%, then m is almost 12.
authors.affiliation: Department of Mathematical Sciences, National Laboratory for AI, Tsinghua University, 100084 Beijing, PR China. dli@math.tsinghua.edu.cn
authors.forename: Dafa
authors.initials: D
authors.lastname: Li
authors.forename: Hongtao
authors.initials: H
authors.lastname: Huang
authors.forename: Xinxin
authors.initials: X
authors.lastname: Li
authors.forename: Xiangrong
authors.initials: X
authors.lastname: Li
mesh_terms: D000465:Algorithms; D055592:Biophysical Phenomena; D001703:Biophysics; D004247:DNA / Q000737:chemistry*; D008962:Models, Theoretical; D009690:Nucleic Acid Conformation; D011336:Probability
chemical_list: D004247:DNA