Yang Chia-Ning, Yang Chang-Biau
Department of Medical Radiation Technology, I-Shou University, No. 1, Section 1, Hsueh-Cheng Road, Ta-Hsu Hsiang, Kaohsiung 840, Taiwan.
Biosystems. 2005 Jul;81(1):1-9. doi: 10.1016/j.biosystems.2005.01.001. Epub 2005 Feb 10.
Among various DNA computing algorithms, it is very common to create an initial data pool that covers correct and incorrect answers at first place followed by a series of selection process to destroy the incorrect ones. The surviving DNA sequences are read as the solutions to the problem. However, algorithms based on such a brute force search will be limited to the problem size. That is, as the number of parameters in the studied problem grows, eventually the algorithm becomes impossible owing to the tremendous initial data pool size. In this theoretical work, we modify a well-known sticker model to design an algorithm that does not require an initial data pool for SAT problem. We propose to build solution sequences in parts to satisfy one clause in a step, and eventually solve the whole Boolean formula after a number of steps. Accordingly, the size of data pool grows from one sort of molecule to the number of solution assignments. The proposed algorithm is expected to provide a solution to SAT problem and become practical as the problem size scales up.
在各种DNA计算算法中，首先创建一个涵盖正确和错误答案的初始数据池，然后通过一系列选择过程来销毁错误答案，这是非常常见的做法。存活下来的DNA序列被视为问题的解决方案。然而，基于这种暴力搜索的算法将受到问题规模的限制。也就是说，随着所研究问题中参数数量的增加，最终由于初始数据池规模巨大，该算法将变得不可行。在这项理论工作中，我们修改了一个著名的粘贴模型，以设计一种不需要为SAT问题创建初始数据池的算法。我们建议逐步构建解决方案序列，以一步满足一个子句，最终经过若干步骤解决整个布尔公式。相应地，数据池的规模从一种分子增长到解决方案赋值的数量。预计所提出的算法将为SAT问题提供解决方案，并随着问题规模的扩大而变得实用。
