基于分子信标的全错位排列问题的DNA计算模型

聂 茜,殷志祥

(安徽理工大学理学院，安徽 淮南 232001)

基于分子信标的全错位排列问题的DNA计算模型

聂 茜,殷志祥

(安徽理工大学理学院，安徽 淮南 232001)

全错位排列问题是组合数学的一个重要的问题，将问题转化成范式的形式，利用分子信标对满足性问题进行求解，给分子信标进行编码，对分子信标的识别区被其补链杂交时进行受力分析，设计分子信标的茎杆，当其识别区被其补链完全杂交时，茎杆被破坏打开并产生荧光，从而给出全错位排列问题的另一种DNA计算模型。

全错位排列问题；分子信标；DNA计算

自从电子计算机问世以来，其对社会的发展起到了巨大的促进作用。随着科学技术的不断进步，电子计算机在解决如组合优化问题以及工程领域复杂问题时已经不能满足需要。科学家们经过努力探索，一种利用DNA进行计算的DNA计算机应运而生。DNA分子计算具有高信息度，高并行性的特点，使得DNA计算机在计算速度及存储容量上拥有绝对的优势。

分子信标是一种核酸探针，它是由圆形的分子识别区，茎杆和连接荧光素及荧光淬灭分子的连接臂三个部分组成，能将核酸的序列结构信息转变为荧光信号，具有较高的灵敏度和选择性[1]。基于分子信标的DNA模型是由殷志祥等在2003年首次提出的[2]。分子信标DNA计算模型是对可满足性问题的约束变量进行编码，放置在分子信标的识别区，通过识别区和靶序列杂交，根据茎杆是否被破坏而线性展开判断可满足性问题的的子句是否满足。……