基于DNA链置换与荧光标记的0-1规划问题的计算模型.pdfVIP

第43卷第11期 数学的实践与认识 V01．43，No．11 2013年6月 MATHEMATICSINPRACTICEANDTHEORY Jun．，2013 ．．t··，l’·l’，l、 l信息科学i ～。。。ttt。‘。·tt一 基于DNA链置换与荧光标记的0．1 规划问题的计算模型 马丽娜，，董亚非h，张成z，刘西奎s (1．陕西师范大学生命科学学院，陕西西安710062) (2．北京大学信息科学技术学院，北京100871) (3．山东科技大学信息科学与工程学院，山东青岛266590) 摘要：DNA链置换技术和荧光标记是近年生物计算领域的新兴的方法，并且因为它 们都有着操作简单的优势而成为DNA计算的常用方法．DNA自组装算法是以DNA 分子作为数据存储和运算的一种新型计算模式．为了提高算法的特异性和检测的灵 敏度，在自组装算法的基础上，首次将DNA链置换技术和荧光标记结合引入到自组 装模型中，提出了一个解决0-1规划问题的DNA计算新模型．与以往DNA计算模型 相比，该模型提高了运算的可靠性和准确性，而且可以逐步缩小解空间，降低运算的 复杂度，同时也使检测的方法更加灵活，易于引入到其他自组装算法模型中． 关键词：DNA链置换；荧光标记；0-1规划；自组装算法 1引言 近年来，DNA分子计算无论在理论上，应用模型的建立上，还是实验与检测技术上都取得 了惊人的进展，已逐渐成为了分子计算领域的发展领头羊，并且越发倾向从理论走向实验实 路径问题(HPPD)，于是科学家们纷纷试图利用其解决多种困难数学问题，如可满足性问题， 的模型，这就为DNA计算机从理论模型论证到计算芯片应用提供了可能．随后，清华大学的 Wu[5】对此方法又做了进一步的改进．虽然初生的DNA计算与传统电子计算还有着很大差 距，但是DNA计算在求解图与组合优化中的一些困难的NP．完全问题上具有内在并行性， 海量信息存储能力等独特优势还是吸引了人们的目光． 机(Cellular 程[7-8】．该模型目前在生物计算中得到了良好的应用． 链置换技术是利用DNA分子单链间的粘贴，通过加入输入链来释放另一条DNA链(图 收稿日期：2012．04．01 资助项目：国家自然科学基金6097000561272246) +通讯作者 1l期 马丽娜，等：基于DNA链置换与荧光标记的0—1规划问题的计算模型 153 米技术上使用立足点链置换反应[10]．立足点链置换可以导致机械器件通过DNA控制．链置 碱基配对的特异性和可预测性，DNA分子在纳米尺度成为了一种强大而且多用途的工程材 料．可以使用链置换控制DNA纳米结构的自组装．通过程序化的互补链杂交，能构造出多样 化快速增长的DNA纳米结构和纳米器件．尽管它起初聚焦于静态结构的白组装，然而DNA 纳米技术现在也已经越来越吸引工程系统上有趣的动态特性．各种原件——包括环路，催 化放大器，分子马达，自主的和重新配置的纳米结构，已经在最近合理的使用DNA链置换反 的寡核苷酸链输入作为反应的催化剂使得DNA链置换循环进行【15】． ——，．r百Gb^p ’ C1” + FG a ∽．r r㈨，II姒Il………………………一 CA(”rAAACT：(TAGAC(1CGATGGTACT、(GTCT耵(AC从GT+ I|iI l I l l¨Il I l I|II l l 圃 C C ／妒