一种求解Ramsey数的DNA计算机算法(2)

　　DNA计算机算法的性能指标包括：生物的复杂性、算法中需要使用到的DNA分子链的数量与链的长度、测试试管数、杂交错误率等。

　　4 编码问题对DNA计算的影响

　　DNA计算中最主要的是编码问题，原因有：①DNA计算中序列的合成质量与编码有直接联系；②DNA计算能不能按照最初设计的目标进行，编码质量具有直接影响；③解空间的大小受编码质量的影响；④在DNA计算中最主要的难点是检测解。

　　编码问题研究步骤：①利用Ramsey数的长度来计算每个编码的长度[4]，确定编码的数目；②使用DNA计算机中的算法，利用杂交的方式来确定产生的编码约束；③在上述基础上，将编码的长度和相应的编码确定出来。

　　利用杂交确定编码的约束性，温度、生物酶、编码之间的距离等一些因素都会直接影响到编码。利用降低杂交时产生的非特异性来进行编码，步骤如下：①将编码受到的各种约束明确出来；②在明确的约束上，将约束转换成数学约束；③针对编码的约束，给出具体编码算法进行编码。

　　5 DNA计算模型子运算实现

　　实现DNA计算模型中的子运算，使用酶切技术或PCR等技术方法如下：利用限制内切酶对DNA内部进行切割，酶切技术的要点是切割的地方、大小、方法的不同。如今酶切技术已经在DNA计算机算法中广泛应用，例如：使用酶切技术来对非解空间进行删除，可以选择几种内切酶，通过酶切的反应将非解的空间进行删除，操作方法是：①将解空间的DNA链均匀分成几份，之后在每份中加入相应的内切酶，使用内切酶来切断对应在某一位置上的DNA序列，待反应结束，将这些全部合并，这个时候中间不含有的条边将同时存在某一位置上的DNA序列中。同样的方法也使用在删除位置的对应点为0或者1的DNA序列；②当前在生物技术中最常用的DNA体外增加法，就是PCR技术，也可以将DNA在计算中定量化，PCR技术是根据完全图顶点的着色来进行处理的；③除上面两种技术外，还可以将DNA计算机算法与完善思想的方法相结合，把非解空间进行删除。根据不同的生化反应选取不同的技术，反馈在DNA计算机算法的编码中，针对不同的反应，采取综合的编码方式，应用在不同反应的编码约束中。生物学领域中有一个重要技术，就是对DNA序列的测定技术。在使用DNA计算机算法的时候，很多时候都需要对DNA链的序列进行分析。

　　6 结语

　　DNA计算模型的扩展基于Ad leman-Lip non模型和粘贴模型解空间的结合，这种模型优点有：少量的编码、简单的求解过程、实现自动化容易等。该模型对DNA的计算机算法理论进行了研究分析，扩大了DNA计算机算法的应用范围，并对求解Ramsey数中的DNA计算机方法进行了说明[5]。

　　在规模很大的Ramsey数的求解问题上[6]，目前还只能在以下两个方面进行探索：①DNA计算机模型的扩展性要好，编码技术要有更好的性能，保证多个项式一起求解问题时，DNA的容量和链的长度增长不只是在指数方面；②对存储技术方面的问题进行研究，使生物方面的技术更加完善与成熟，保证每个试管中可以装下更多的DNA药物分子，能存储问题的全部解空间。

　　参考文献参考文献：

　　[1]陈红，吴康，许晓东，等.九个经典Ramsey数R（3，t）的新下界[J].数学杂志，2011，31（3）：582586.

　　[2] 刘大瑾，白路锋.关于完全三部图的Ramsey数[J].南京理工大学学报：自然科学版，2010，34（3）：406408.

　　[3] 孙玉芹.关于边Ramsey数研究的综述[J].黑龙江大学自然科学学报，2012，29（1）：3438，41.

　　[4] 谢建民，姚兵，毛耀忠，等.Ramsey数R（K3，K16-e）的一个下界[J].数学的实践与认识，2012，42（5）：203208.

　　[5] 李肯立，郭里，唐卓，等.一种求解Ramsey数的DNA计算机算法[J].计算机研究与发展，2011，48（3）：447454.

　　[6] 刘恩来.一种求解Ramsey数的计算机算法[D].扬州：扬州大学，2013.