Hairpin formation in DNA computation presents limits for large NP-complete problems

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 pn,l be the probability that a n-mer DNA strand is a (n,l)-hairpin format, and qn,l(m) be the probability that m ones are chosen at random from 4n n-mer oligonucleotides such that at least one of the m ones is a (n,l)-hairpin format. Then, q^(m)n,1 = 1-(1-Pn,l)^m=mpn,l. If we require qn,l(m)