DNA纳米颗粒共聚体在图的连通度问题中的应用

王艳钗，张　会，董亚非,

(1.陕西师范大学计算机科学学院，陕西西安 710119； 2.陕西师范大学生命科学学院，陕西西安 710119)

DNA纳米颗粒共聚体在图的连通度问题中的应用

王艳钗1，张会2，董亚非1,2

(1.陕西师范大学计算机科学学院，陕西西安 710119； 2.陕西师范大学生命科学学院，陕西西安 710119)

本文提出了一种利用DNA纳米金颗粒共聚体的自组装过程解决图论中一个NP完全问题—连通度问题的DNA计算方法，构建了解决图的连通度问题的三维DNA自组装计算模型.根据设计的算法，首先需要根据具体的图的连通度问题设计用于自组装的DNA纳米金颗粒共聚体，然后根据算法经过一系列实验设计来求解连通度问题.本文利用Visual DSD仿真该实验的可行性，为下一步DNA自组装计算模型的应用提供了可行的方案.

DNA计算；DNA纳米金颗粒；图的连通度；三维模型

1　引言

1994年，Adleman[1]首次利用线性DNA 分子解决了一个7个顶点的Hamilton路问题.随后，许多科学家的目光被吸引到分子计算领域.1995年，Lipton[2]建立了解决可满足问题的DNA计算机.两年后，Ouyang等[3]提出了解决最大团问题的DNA计算模型.最近，张成[4,5]利用环形DNA分子求解了最大团问题同时利用自组装DNA链置换设计分子逻辑计算模型.以上方法都是利用DNA分子计算NP完全问题.近年来，很多研究学者提出了利用如RNA[6]、质粒[7]和瓦片[8,9]等多种不同的分子作为工具进行计算.2007年，Brun[10]利用瓦片进行了加法和乘法运算.目前利用DNA自组装引导纳米粒子形成三维纳米结构的技术极大地推进了许多基础科学问题……