利用双链DNA编码节点和质粒求解的有向Hamilton路径问题

摘要

DNA计算可以大规模并行处理和组合运算,解决某些难解问题,如有向Hamilton路径问题.以质粒DNA为框架,将节点用双链DNA编码,筛选最短Hamilton路径的方法,对有效解进行最大程度的分离,排除不可行解,避免误差进一步放大.此方法可以提高反应过程中编码的稳定性,减少分子错配的可能性,进行试管生化反应后,经分离鉴定得到最短路径.