巩成艳，殷志祥，赵鑫月

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

基于自组装纳米颗粒探针的全错位排列问题的DNA计算模型

巩成艳，殷志祥*，赵鑫月

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

全错位排列问题是组合数学中的一类重要问题，可转化为范式的形式，利用自组装纳米颗粒探针对满足性问题进行求解。将纳米金颗粒和DNA序列进行结合，形成纳米金颗粒探针的识别区，并且成拱形结构。当识别区与其补链发生杂交反应时，拱形结构打开并发出荧光，从而给出了全错位排列问题的一种新的DNA计算模型。与传统的DNA计算模型不同，本文将纳米技术和DNA计算理论相结合。

DNA计算；自组装；纳米颗粒；全错位排列问题

1994年，美国的Adleman博士首次利用DNA编码技术解决了具有7个顶点的有向哈密尔顿路径问题，并首次提出DNA分子计算技术[1]。由于DNA分子计算技术具有巨大的并行性和非凡的信息密度等优点，而高性能计算技术一直是计算机科学家的研究热点，同时也满足计算机技术发展的需要。近年来，研究者们对DNA分子计算技术进行了一系列研究，用该技术解决了很多的复杂问题，如3-SAT问题、最大团问题、骑士问题和最大独立集问题等[2-6]。

全错位排列问题是组合数学中的一类重要问题。孙侠给出了全错位排列问题的基于表面[7]、基于芯片[8]和基于三链[9]的DNA计算模型。

纳米材料近来被广泛应用于纳米生物学领域。纳米金颗粒已经成为用于感测分析物最受欢迎的材料之一，因为它制备便宜，有较好的稳定性和生物相容性。……