唐新玉　殷志祥

摘要：针对全错位排列这类NP 完全问题，提出了一种基于DNA 自组装的全错位排列问题计算模型。该模型利用了DNA 分子间的自组装能力，在具体操作时只用到凝胶电泳技术，在一定程度上减少了实验误差。

关键词：全错位排列问题；可满足问题；DNA 自组装

中图分类号：O29 文献标志码：A

文章编号：1672-1098（2014）01-0080-03

自文献[1]利用 DNA 计算方法解决了哈密尔顿路径问题以后，越来越多的学者开始关注 DNA 计算并提出解决图论问题的方法，如 0-1 规划问题，图着色问题，最小生成树问题等。

DNA 自组装是依赖分子间非共价键作用力自发的完成由小分子形成较大且复杂的结构。文献[2]、文献[3]首次利用 DNA 分子构成了自组装 Tile 结构，并利用其中一种瓦片结构建立了多种复杂的算法模型。2000年，文献[4]通过实验给出了自组装 DNA 计算模型求解累积异或运算的实现过程和方法。2002 年，文献[5]将自组装 DNA 计算的基本思想用于求解布尔逻辑表达式并将其实现逻辑电路。2004年，文献[6]利用 DX Tile 结构实现了一维元胞自动机，在此基础上分析证明了用 DNA Tile 自组装结构实现任何元胞自动机的可行性。Tile 自组装还被用来解决组合优化问题[7-8]，2008年，文献[9]在前任的基础上提出了求解可满足性问题的非确定性自组装模型。

全错位排列是组合数学中常见的一类问题，文献[10-11]给出了基于表面、基于芯片以及基于三链的 DNA 计算模型，与以往模型相比，本文给出的模型操作更为简单，更易得出可行解。

1全错位排列问题

全错位排列问题即“装错信封问题”，可用数学语言描述如下：