Good encodings for DNA-based solutions to combinatorial problems
Good encodings for DNA-based solutions to combinatorial problems
复制标题
DOI：
10.1090/dimacs/044/20
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Deaton;R. C. Murphy;M. Garzon;D. Franceschetti;S. E. Stevens
中科院分区：
文献类型：
--
作者：
R. Deaton;R. C. Murphy;M. Garzon;D. Franceschetti;S. E. Stevens
Adleman通过在DNA的寡核苷酸中编码哈密尔顿图的顶点和边，杂交寡核苷酸以产生潜在的答案，并提取对应于哈密尔顿路径的DNA来解决哈密尔顿路径问题。根据DNA反应发生的条件，假阳性的可能性，或者看似正确的哈密尔顿路径问题的错误解决方案是可能的。实验艾德了这种可能性。产生假阳性的主要机制是杂交严格性，其取决于反应条件，其中最重要的是温度。取决于温度，两个寡核苷酸可以杂交，而它们的碱基对之间不精确匹配。为了使基于DNA的组合问题解决方案成为可行和实用的技术，必须消除假阳性的可能性。这可以通过将哈密顿图的顶点和边编码在DNA寡核苷酸或码字中来实现，所述DNA寡核苷酸或码字是彼此的最小距离，其取决于温度。这种可靠的编码消除了假阳性的风险，这得到了实验性试验的支持。编码是由遗传算法搜索可能的码字空间。Hamming界被证明是在不引入假Hamiltonian路径的可能性的情况下可以在DNA中编码的顶点数量的上限。
Adleman has solved the Hamiltonian path problem by encoding the vertices and edges of the Hamiltonian graph in oligonucleotides of DNA, hybridizing the oligonucleotides to produce potential answers, and extracting the DNA which corresponds to the Hamiltonian path. Depending on the conditions under which the DNA reactions occur, the possibility of false positives, or wrong solutions to the Hamiltonian path problem which appear correct, are possible. This possibility was veri ed by experiment. The primary mechanism for the production of false positives is hybridization stringency that depends on the reaction conditions, of which the most important is temperature. Depending on the temperature, two oligonucleotides can hybridize without exact matching between their base pairs. For DNA-based solutions to combinatorial problems to become a viable and practical technology, the possibility of false positives must be eliminated. This can be accomplished by encoding the vertices and edges of the Hamiltonian graph in DNA oligonucleotides, or codewords, that are a minimum distance, which depends on temperature, from each other. This reliable encoding eliminated the risk of a false positive, which was supported by an experimental trial. The encoding was produced by a genetic algorithm search of the space of possible codewords. The Hamming bound was shown to be an upper bound on the number of vertices that could be encoded in DNA without introducing the possibility of false Hamiltonian paths.