孙 侠，殷志祥，赵前进，许 峰

（安徽理工大学 理学院，安徽 淮南 232001）

基于三链DNA结构的全错位排列问题算法

孙 侠，殷志祥，赵前进，许 峰

（安徽理工大学 理学院，安徽 淮南 232001）

目前，一种新型的DNA计算模型——三链DNA计算模式正越来越受到人们的关注。已经证实，DNA单链能在RecA蛋白的介导下与同源的双链DNA匹配成稳定的三链DNA结构，利用此三链核酸提取目的DNA序列是完全可行的。文章提出了全错位排列问题的基于三链DNA的计算模型，由于表示可能解的链都是双链，彼此不会错配，也不会形成发夹结构，这样就大大降低了编码复杂度和计算错误率。

三链DNA结构；抗原中介；全错位排列问题

DNA计算是一种以DNA和相关的某些生物酶作为最基本材料的，基于某种生化反应原理的新型分子生物计算方法。自1994年，美国加利福尼亚大学的Adleman［1］博士提出DNA计算的思想以来，DNA计算领域的研究有了长足的发展。许多NP—完全问题和困难计算问题都得到了解决，如中国邮递员问题，图的着色问题，匹配问题，图的最大团问题，最小覆盖问题，0－1规划问题等［2－6］。以前的DNA计算方法都是基于Watson－Crick原则，利用碱基间的互补配对来完成基本的运算。随着实验的技术的不断提高，近年来许多研究者在实验中相继证实分子可以以其它结构存在，比如三链状结构。至今已发现的三链结构有三股螺旋结构和三股发辫结构。对三链DNA的研究主要是医学方面，也有人尝试用三链DNA解决有关问题，方刚等［7］用三链DNA计算模型解决了3－SAT问题、三顶点着色问题，杨静等［8］利用三链DNA计算模型解决了0－1整数规划问题。……