DNA-based Learning Algorithms and their Applications

我们考虑了含有大量DNA链的试管的概率解释，并提出了利用试管中DNA链数的总体计算和基于概率解释的概率逻辑推理。我们应用了基于dna的大规模并行穷尽搜索来解决DNF布尔公式的计算学习问题。我们提出了将任何k项DNF公式编码到DNA链上的新方法，利用DNA聚合酶的杂交和引物扩展来评估编码的DNF公式的真值赋值，并找到与给定示例一致的DNF公式。通过使用这些方法，我们证明了k项DNF公式类和一般DNF公式类在DNA计算机上是有效可学习的。我们将翻译机制与四碱基密码子技术相结合，开发了一种计算有限自动机的分子机器。我们已经报道了一些实验结果，我们已经成功地在大肠杆菌的四碱基密码子的体外翻译系统上实现了有限自动机。

We have considered a probabilistic interpretation of the test tube which contains a large amount of DNA strands, and proposed a population computation using a number of DNA strands in the test tube and a probabilistic logical inference based on the probabilistic interpretation.We have applied a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF Boolean formulae. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth value assignment by using hybridization and primer extension with DNA polymerase, and find a consistent DNF formula with the given examples. By employing these methods, we have shown that the class of k-term DNF formulae and the class of general DNF formulae are efficiently learnable on DNA computer.We have employed the translation mechanism combined with four-base codon techniques to develop a molecular machine which computes finite automata (finite-state machine). We have reported some experimental results where we have succeeded to implement a finite automaton on an E.coli in vitro translation system with four-base codons.