James K D, Boles A R, Henckel D, Ellington A D
Department of Chemistry, Indiana University, Bloomington, IN 47405, USA.
Nucleic Acids Res. 1998 Nov 15;26(22):5203-11. doi: 10.1093/nar/26.22.5203.
Several different computational problems have been solved using DNA as a medium. However, the DNA computations that have so far been carried out have examined a relatively small number of possible sequence solutions in order to find correct sequence solutions. We have encoded a search algorithm in DNA that required the evaluation of >16 000 000 possible sequence solutions in order to find a single, correct sequence solution. Experimental evaluation of the search algorithm revealed bounds for the accuracies of answers to other large, computationally complex problems and suggested methods for the optimization of DNA computations in general. Short oligonucleotide substrates performed substantially better than longer substrates. Large, computationally complex problems whose evaluation requires hybridization and ligation can likely best be encoded and evaluated using short oligonucleotides at mesophilic temperatures.
利用DNA作为媒介已经解决了几个不同的计算问题。然而，迄今为止所进行的DNA计算为了找到正确的序列解决方案，只检验了相对较少数量的可能序列解决方案。我们已经在DNA中编码了一种搜索算法，该算法需要评估超过16000000种可能的序列解决方案，以便找到一个单一的正确序列解决方案。对该搜索算法的实验评估揭示了其他大型计算复杂问题答案准确性的界限，并提出了一般优化DNA计算的方法。短寡核苷酸底物的表现明显优于长底物。对于那些评估需要杂交和连接的大型计算复杂问题，很可能最好在中温下使用短寡核苷酸进行编码和评估。
