DNA链置换反应网络在求解可满足问题中的应用

摘要

DNA链置换是一种非常重要的分子自组装方法，因其操作性强、实验条件简单而被广泛应用于DNA计算中。可满足问题是非确定性多项式问题(NP问题)中的一个经典问题，文章利用DNA链置换反应网络来求解可满足问题，利用Visual DSD语言设计DNA链。求解过程主要分为3个反应模块，即变量转换模块、求和模块和阈值比较模块。变量转换模块是将不同变量所代表的DNA链通过链置换反应转换成同一条链；求和模块是将转换后的链浓度进行相加；在阈值比较模块中，由于浓度的检测会存在一定的误差，为此设计了2个链置换反应检测是否有荧光显示来判断可行解，若有荧光显示则为可行解，反之不是。通过Visual DSD仿真软件得到了变量转换模块相对应的链置换反应网络图、变量仿真图以及阈值比较图。该方法可用来求解多个变量的可满足性问题。文章利用上述方法成功解决了一个5变量的可满足问题。

关键词

Visual DSD / 阈值比较 / 反应网络 / DNA链置换