全错位排列问题的DNA计算模型

胡娟

【摘 要】组合数学中的一个很重要问题全错位排列问题其应用非常广，利用0-1规划可将此问题转化为可满足性问题，通过DNA分子之间产生的发夹结构，利用琼脂糖凝胶可得到满足问题的可行解，便于求解三元以上的全错位排列。

【关键词】全错位排列问题；DNA计算；凝胶电泳

中图分类号： TP301.6 文献标识码： A 文章编号： 2095-2457（2018）19-0101-002

DOI：10.19694/j.cnki.issn2095-2457.2018.19.045

DNA Computational Model for Error Permutation Problem

HU Juan

（The Foundation department of Huainan Vocational Technical College，Huainan Anhui 232001，China）

【Abstract】A very important problem in combinatorial mathematics is that the problem of total dislocation arrangement is very widely used. Using 0-1 programming， this problem can be converted into a satisfying problem through the hairpin structure generated between DNA molecules. A feasible solution to satisfy the problem can be obtained by agarose gel， and it is convenient to solve the total dislocation arrangement above three yuan.

【Key words】

0 引言

作为一种新型的计算方法，DNA计算的基本方法是将要解决的问题转化为DNA编码，再利用DNA分子的结构特点和不同核苷酸中四种碱基配对，通过各种生物酶及生化反应来得到所求问题的解。DNA计算最早是在1994年，Adleman博士用DNA计算解决了哈密顿有向路问题。它的运算速度及超大的存储量是目前计算机无法比拟的。也正因为如此，越来越多的学者用它解决了一个有一个NP完全问题。如最大团问题，最小覆盖问题及邮路一致性问题都用DNA计算得到了很好的解决。

目前DNA的实现方式走过了三个阶段：初级阶段---试管；过渡阶段---表面；成功阶段---芯片。对于组合数学的一个非常重要的问题全错位排列问题，也有不少学者给出过解决方法，本文采用DNA计算模型来解决全错位排列问题，此方法更便于求解三元以上的全错位排列问题。

1 全错位排列问题

全错位排列问题最初是由著名的数学家伯努利提出的，作为组合数学中的一个重要的问题，它又被著名的数学家欧拉称其为“错装信封问题”。此问题大意为：有一个人写了n封不同的信，他用n个不同的信封来装这些信，问他把这些信全都装错的装法有多少种？后来此问题又被数学家用数学语言描述为：对于一个n元集合{1，2，...，n}来说，若它的全排列i1i2...in满足条件ij≠j（1？燮j？燮n），则称其此全排列为集合{1，2，...，n}的一个错排。简单说为第一个元素不能在第一位，第二个元素不能在第二位，第n个元素不能在第n位的全排列。目前做的较多的为三元集合的错排问题。算法也有很多，有分类求解法，递推关系求解法和多项式求解法。

下面我们以含有3元集合1，2，3的全错位排列为例，求出其所有全错位排列，问题即为对于数字1，2，3来说，数字1，2，3都不能在自己原来位置上的全排列。分析此问题用下列记号[2]：若第二位排数字1，记为a；若第一位排数字2，记为b；若第一位排数字3，记为c。则其否命题记为a'，b'，c'，对此问题根据0-1规划将其可以转化成可满足性问题：如果数字1不在第二位上，那么数字3在第二位上；如果数字2在第一位上，那么数字3便不能在第一位上；如果数字1在第三位上，那么数字2便不能在第三位上。从而可以得到下面的范式：

现在即要求出满足上式的所有可能解就可得出问题的解。

2 DNA计算的算法及其操作过程

2.1 基本算法

（1）利用0-1规划对所给问题的变量取值为0，1，生成其所有可能的组合；

（2）为了保留可行解，依次利用范式中的约束条件排除非可行解；

（3）从而得到剩余的可行解；

（4）重复（2）（3），排除掉所有非可行解，得到满足范式中的约束条件可行解。

2.2 DNA编码

对于含有的3元集合的全错位排列问题，第一步先合成初始6种DNA链，用a，b，c和a'，b'，c'表示，其特殊补链用表示（如图1所示）。其中a，b，c对应的值表示为1，a'，b'，c'表示0。第二步由a，b，c和a'，b'，c'合成8种DNA片段放入数据池中，由三部分表示，前一部分是不参与反应，中间部分为a，b，c和a'，b'，c'的前四个碱基的补，后面部分为a，b，c和a'，b'，c'的后四个碱基的补（如图2所示）。

（4）试管中即为满足范式的所有解。通过检验可知该问题的解为：101和010，即231和312为3元集合1，2，3全错位排列。

3 结论

本文就组合数学中的一个很重要问题全错位排列问题给出DNA计算模型，利用0-1规划将此问题转化为可满足性问题，通过DNA分子之间产生的发夹结构，利用琼脂糖凝胶得到满足问题的可行解，由于操作中只用到了琼脂糖凝胶电泳，减小了实验过程中的误差，提高了求解的准确性和可操作性，便于求解3元以上的全错位排列。

【参考文献】

[1]刘建军，刘芹英.欧拉对经典组合学的贡献[J]自然科学史研究，2003（4）：361-367.

[2]孙侠，殷志详等.全错位排列问题的基于表面的DNA计算模型[J].生物数学学报，2009，24（3）：513-517.

[3]方刚，张社民，朱岩等，基于三链核酸的DNA计算[J].生物信息学，2009，7（3）：181-185.

[4]宋勃生，殷志详等DNA自主装的可满足性问题模型[J].小型微型计算机系统2011，9（32）：1872-1875.

[5]Even S，Ltai A，Shamir A.On the complexity of time table and multi-commodity flow，problems[J].Siam Journal on Computing，1976，5（4）：691-703.

[6]ZHIXIANG YIN，MIN CHEN.Apply AcryditeTM Gel Separation to Solve Time–Table Problem[C]//Telkomnika Indonesian Journal of Electrical Engineering 2012，10（5）：1111-1116.

[10]Pillay N，Banzhaf W.A study of heuristic combinationa for hyperheuristic systems for the uncapacitated examination timetabling problem[J].European Journal of Operational Research，2009，197（2）：482-491.

[7]孫侠，殷志详，赵前进等.基于三链DNA结构的全错位排列问题算法[J].滁州学院学报，2012，2（14）：18-20.