第３１卷第１２期 计 算 机 学 报 ＶｏＩ．３１ Ｎｏ．１２ Ｄｅｃ．２００８ ２００８年１２月 ０Ｆ ＣＯＭＰＵＴＥＲＳ ＣＨＩＮＥＳＥ ＪＯＵＲＮＡＬ 基于ＤＮＡ计算自组装模型的Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ算法破译 陈智华 （华中科技大学控制科学与工程系 武汉４３００７４） 摘要ＤＮＡ自组装计算模型是近年来引人关注的计算模型，已有基于自组装模型的二进制加法、乘法以及有限 域中的加法和乘法的讨论．文中利用ＤＮＡ自组装模型设计的模乘系统，实现了素数Ｐ的本原根ｇ连续乘方后模Ｐ 的数的排列，从而可以在线性时间内求解离散对数，为破译Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ密钥交换算法提供了新的生物方法．该 模乘系统使用了＠（ｐ）种自组装类型，组装的时间复杂度为Ｏ（ｐ一１）．系统最后组装结果提取出报告链后，经过 ＰＣＲ和凝胶电泳读取离散对数结果．该模型扩展了ＤＮＡ自组装计算模型的应用，为求取离散对数提供了新思路． 关键词ＤＮＡ计算；ＤＮＡ自组装模型；离散对数；整数排序；ＰＣＲ ＴＰ３０１ 中图法分类号Ｂｒｅａｋｉｎｇ ｔｈｅ Ｄｉｆｆｉｅ‘Ｈｅｌｌｍａｎ Ｋｅｙ Ｅｘｃｈａｎｇｅ Ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ Ｔｉｌｅ Ａｓｓｅｍｂｌｙ Ｍｏｄｅｌ ＣＨＥＮ Ｚｈｉ—ＨＨａ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｎｔｒｏｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕａｚｈｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ．Ｗｕｈａｎ ４３００７４） Ａｂｓｔｒａｃｔ Ｒｅｃｅｎｔ ｅｘｐｅｒｉｍｅｎｔｓ ｈａｖｅ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈａｔ ｔｈｅ ｓｉｍｐｌｅ ｂｉｎａｒｙ ａｒｉｔｈｍｅｔｉｃ ａｎｄ ｌｏｇｉｃａｌ ｏｐｅｒａｔｉｏｎｓ ｃａｎ ｂｅ ｃｏｍｐｕｔｅｄ ｂｙ ｔｈｅ ｓｅｌｆ－ａｓｓｅｍｂｌｙ ＤＮＡ ｔｉｌｅｓ．Ｔｈｉｓ ｐａｐｅｒ ｓｈｏｗｓ ｈｏｗ ｔｈｅ ｔｉｌｅ ａｓ— ｓｅｍｂｌｙ ｐｒｏｃｅｓｓ ｃａｎ ｂｅ ｕｓｅｄ ｔｏ ｂｒｅａｋ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ｋｅｙ ｅｘｃｈａｎｇｅ．Ｉｎ ｏｒｄｅｒ ｔｏ ａｃｈｉｅｖｅ ｔｈｉｓ，ｔｈｅ ａｕｔｈｏｒ ｕｓｅｄ ｔｉｌｅ ｓｙｓｔｅｍｓ ｔｏ ｃｏｎｓｔｒｕｃｔ ｔｈｅ ｉｎｔｅｇｅｒｓ ｐｅｒｍｕｔａｔｉｏｎ ｆｒｏｍ １ ｔｏ Ｐ一１ ｂａｓｅｄ ｏｎ ｔｈｅ ｔｒｕｔｈ ｔａｂｌｅ ｏｆ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｎｕｍｂｅｒｓ ｍｏｄｕｌａｒ Ｐ：ｇ ｒｏｏｄ Ｐ，ｇ。ｒｏｏｄ Ｐ，…，ｇＰ～ｒｏｏｄ Ｐ．Ｔｈｅ ｏｕｔｐｕｔ ｏｆ ｔｈｅ ｓｙｓｔｅｍｓ ｃａｎ ｂｅ ｒｅａｄ ｂｙ ｔｈｅ ｓｔａｎｄａｒｄ ｓｅｑｕｅｎｃｅ—ｒｅａｄｉｎｇ ｏｐｅｒａｔｉｏｎ ｔｈａｔ ｕｓｅｓ ａ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ＰＣＲ ａｎｄ ｇｅｌ ｅｌｅｃｔｒｏｐｈｏｒｅｓｉｓ．Ｔｈｒｏｕｇｈ ｔｈｅ ｐｒｏｃｅｓｓｅｓ ｏｆ ｔｉｌｅ ｓｙｓｔｅｍｓ，ｗｅ ｃａｎ ｐｉｃｋ ｏｕｔ ｔｈｅ ｄｉｓｃｒｅｔｅ ｌｏｇ— ａｒｉｔｈｍ ｒｅｓｕｌｔ ｗｈｉｃｈ ｉｓ ｔｈｅ ｓｅｃｒｅｔ ｋｅｙ ｉｎ ｔｈｅ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ａｌｇｏｒｉｔｈｍ．Ｓｏ ｔｈｅ ｋｅｙ ｅｘｃｈａｎｇｅ ｂｙ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｎｓａｆｅ．Ｔｈｅ ｓｙｓｔｅｍ ｃａｎ ｂｅ ｃａｒｒｉｅｄ ｏｕｔ ｉｎ＠（Ｐ一１）ａｓｓｅｍｂｌｙ ｔｉｍｅ ｗｉｔｈ＠（ ）ｔｉｌｅｓ．Ｔｈｅ ｍｅｔｈｏｄｓ ｅｘｔｅｎｄ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｓｅｌｆ－ａｓｓｅｍｂｌｙ ｍｏｄｅ１． Ｋｅｙｗｏｒｄｓ ｔｉｏｎ；ＰＣＲ ＤＮＡ ｃｏｍｐｕｔｉｎｇ；ＤＮＡ ｓｅｌｆ—ａｓｓｅｍｂｌｙ ｍｏｄｅｌ；ｄｉｓｃｒｅｔｅ ｌｏｇａｒｉｔｈｍ；ｉｎｔｅｇｅｒｓ ｐｅｒｍｕｔａ— ｌ ＩｎｔｒＯｄｕｃｔｉＯｎ Ａｄｌｅｍａｎ’ｓ ｐｉｏｎｅｅｒｉｎｇ ｓｔｕｄｙ［ 一。］ｓｅｔ ｔｈｅ ｓｔａｇｅ ｓｉｂｉｌｉｔｙ ｏｆ ｍｏｌｅｃｕｌａｒ ｃｏｍｐｕｔｉｎｇ ａｐｐｒｏａｃｈｅｓ ｔｏ ｓｏｌｖｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ．Ｂｉｏ—ｉｎｓｐｉｒｅｄ ｃｏｍｐｕｔａｔｉｏｎ ｃｏｕｌｄ ｂｅ ｕｓｅｄ ｔｏ ｓｏｌｖｅ ｃｏｍｐｌｅｘ ｍａｔｈｅｍａｔｉｃａｌ ｐｒｏｂ一 １ｅｍｓｌ＿３Ｌ ．Ｗｉｔｈ ｔｈｅ ｖａｓｔ ｐａｒａｌｌｅｌｉｓｍ ａｎｄ ｈｉｇｈ ｄｅｎｓｉ— ｔｙ ｓｔｏｒａｇｅ，ＤＮＡ ｃｏｍｐｕｔｉｎｇ ｉｓ ｅｍｐｌｏｙｅｄ ｔｏ ｓｏｌｖｅ ｍａｎｙ ｃｏｍｂｌｎａｔｏｒｉａ１ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｓｕｃｈ ａｎ ｅｌｅｇａｎｔ ｉｄｅａ ｉｎｓｐｉｒｅｄ ｐｅｏｐｌｅ ｔｏ ａｐｐｌｙ ＤＮＡ ｃｏｒｎ— ｐｕｔｉｎｇ ｔｏ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｓｙｓｔｅｍｓ ｉｎ ｓｕｃｈ ｆｉｅｌｄｓ： ｂｒｅａｋｉｎｇ ｃｒｙｐｔｏｓｙｓｔｅｍｓ，ｅｎｃｒｙｐｔｉｏｎ ａｎｄ ｄｅｃｒｙｐ一 ｆｏｒ ｔｈｅ ｎｅｗ ｆｉｅｌｄ ｏｆ ｂｉｏ—ｃｏｍｐｕｔｉｎｇ ｒｅｓｅａｒｃｈ．Ｕｓｉｎｇ ｔｈｅ ｖａｓｔ ｐａｒａｌｌｅｌｉｓｍ ｔｏ ｄｏ ｔｈｅ ｃｏｍｂｉｎａｔｏｒｉａ１ ｓｅａｒｃｈ ａｍｏｎｇ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｐｏｓｓｉｂｌｅ ｓｏｌｕｔｉｏｎｓ ｒｅｐｒｅ— ｓｅｎｔｅｄ ｂｙ ＤＮＡ ｓｔｒａｎｄｓ，Ａｄｌｅｍａｎ ｈａｓ ｓｏｌｖｅｄ ｓｏｍｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｓｅａｒｃｈ ｐｒｏｂｌｅｍｓ ｓｕｃｈ ａｓ ｔｈｅ Ｈａｍｉｌ— ｔｏｎｉａｎ ｐａｔｈ ｐｒｏｂｌｅｍ￣１］，ａｎｄ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈｅ ｆｅａ— 收稿日期：２００８—０４—１８；最终修改稿收到日期：２００８—１０—１５．本课题得到国家自然科学基金（６０８０３１１３，６０５３３０１０，６０６７４１０６）和国家“八六三，， 高技术研究发展计划项目基金（２００６ＡＡ０１２１０４）资助．陈智华，女，１９７６年生，博士研究生，讲师，研究方向为基于ＤＮＡ计算的信息安全、 智能控制算法．Ｅ—ｍａｉｌ；ｃｈｅｎｚｈｉｈｕａ＠ｍａｉｌ．ｂｕｓｔ．ｅｄｕ．ｅｎ． １２期 陈智华：基于ＤＮＡ计算自组装模型的Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ算法破译 ２１ｌ７ ｔｉｏｎ．ｈｉｄｉｎｇ ｍｅｓｓａｇｅ ａｎｄ ａｕｔｈｅｎｔｉｃａｔｉｏｎ。ｗｈｉｃｈ ｒｅ— ｑｕｉｒｅ ａｎ ｅｎｏｒｍｏｕｓ ａｍｏｕｎｔ ｏｆ ｃｏｍｐｕｔａｔｉｏｎ． ｔｈｅ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅｌ ｔｏ ｉｍｐｌｅｍｅｎｔ ａｒｂｉｔｒａｒｙ ｃｉｒ— ｃｕｌｔｓ［ ．Ｓｉｍｉｌａｒｌｙ，Ｒｏｔｈｅｍｕｎｄ ｅｔ ａ１．ｈａｖｅ ｉｍｐｌｅ— Ａ ｎｕｍｂｅｒ ｏｆ ｐｒｏｐｏｓａｌｓ ｈａｖｅ ｂｅｅｎ ｏｆｆｅｒｅｄ ｆｏｒ ｍｅｎｔｅｄ ａ ＤＮＡ ｔｉｌｅ ｓｙｓｔｅｍ ｔｈａｔ ｃｏｕｌｄ ｃｏｍｐｕｔｅ ｔｈｅ Ｘ０Ｒ ｆｕｎｃｔｉｏｎ ａｎｄ ｒｅｓｕｌｔ ｉｎ ａ Ｓｉｅｒｐｉｎｓｋｉ ｔｒｉａｎ— ｇｌｅ［ ．ｂｒｅａｋｉｎｇ ｃｏｎｖｅｎｔｉｏｎａｌ ｅｒｙｐｔｏｇｒａｐｈｉｃ ｓｙｓｔｅｍｓ ｂｙ ＤＮＡ ｃｏｍｐｕｔｉｎｇ． Ｆｏｒ ｅｘａｍｐｌｅ，Ｂｏｎｅｈ ａｎｄ Ｂｒｕｎ ｐｒｏｐｏｓｅｄ ｔｈｅｏｒｅｔｉｃａｌｌｙ ｔｈｅ ｓｙｓｔｅｍｓ Ａｄｌｅｍａｎ ｈａｖｅ ｐｒｏｐｏｓｅｄ ＤＮＡ ｃｏｍｐｕｔｉｎｇ ｍｅｔｈ— ｔｈａｔ ｃｏｕｌｄ ｃｏｍｐｕｔｅ ｔｈｅ ｓｕｍ ａｎｄ ｐｒｏｄｕｃｔ ｏｆ ｔｗｏ ｎｕｍｂｅｒｓ ｕｓｉｎｇ ｔｈｅ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅｌ［１ ７］．Ｈｅ ｆｏｕｎｄ ｔｈａｔ ｔｈｅ ａｄｄｉｎｇ ａｎｄ ｍｕｌｔｉｐｌｙｉｎｇ ｃａｎ ｂｅ ｄｏｎｅ ｏｄｓ ｔｏ ｂｒｅａｋ ｔｈｅ Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ（ＤＥＳ）． Ｃｈａｎｇ ａｎｄ Ｇｕｏ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈａｔ ｆａｃｔｏｒｉｎｇ ｔｈｅ ｐｒｏｄｕｃｔ ｏｆ ｔｗｏ ｌａｒｇｅ ｐｒｉｍｅ ｎｕｍｂｅｒｓ ｃｏｕｌｄ ｂｅ ｃｏｍ— ｐｌｅｔｅｄ ｔｈｒｏｕｇｈ ｂｉｏｌｏｇｉｃａｌ ｏｐｅｒａｔｉｏｎｓ ｕｓｉｎｇ ａ ｍｏｌｅｃ— ｕｓｉｎｇ＠（１）ｔｉｌｅｓ ａｎｄ ｔｈｅ ｔｗｏ ｃｏｍｐｕｔａｔｉｏｎｓ ｃａｎ ｂｅ ｃａｒｒｉｅｄ ｏｕｔ ｉｎ ｌｉｎｅａｒ ｔｉｍｅ ｉｎ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅｌｓ． ｕｌａｒ ｃｏｍｐｕｔｅｒ［ ．Ｆｕｒｔｈｅｒｍｏｒｅ。ｔｈｉｓ ｒｅｓｕｌｔ ｉｎｄｉｃａ— ｔｅｄ ｔｈａｔ ｔｈｅ ｃｒｙｐｔｏｓｙｓｔｅｍｓ ｕｓｉｎｇ ｐｕｂｌｉｃ—ｋｅｙ ｗｅｒｅ ｐｅｒｈａｐｓ ｉｎｓｅｃｕｒｅ ａｎｄ ａｌｓｏ ｐｒｅｓｅｎｔｅｄ ｔｈｅ ｃｌｅａｒ ｅｖｉ— ｄｅｎｃｅ ｏｆ ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ＤＮＡ ｃｏｍｐｕｔｉｎｇ ｔｏ ｐｅｒｆｏｒｍ ｃｏｍｐｌｉｃａｔｅｄ ｍａｔｈｅｍａｔｉｃａｌ ｏｐｅｒａｔｉｏｎｓ．Ｇｅｈａｎｉ ｐｒｅｓ— ｅｎｔｅｄ ｓｏｍｅ ｐｒｏｃｅｄｕｒｅｓ ｆｏｒ ＤＮＡ— ｂａｓｅｄ ｃｒｙｐｔｏｇｒａ—— ｐｈｙ ｂａｓｅｄ ｏｎ ＯＴＰ ．Ｖａｒｉｏｕｓ ｍｏｄｉｆｉｅｄ ＤＮＡ ｓｔｅｇ— ａｎｏｇｒａｍ ｍｅｔｈｏｄｓ ｗｅｒｅ ｐｒｏｐｏｓｅｄ ｉｎ ｏｒｄｅｒ ｔｏ ｉｍ— ｐｒｏｖｅ ｔｈｅ ｓｅｃｕｒｉｔｙ．Ｌｅｉｅｒ ｐｒｅｓｅｎｔｅｄ ｔｗｏ ｄｉｆｆｅｒｅｎｔ ｃｒｙｐｔｏｇｒａｐｈｉｃ ａｐｐｒｏａｃｈｅｓ ｂａｓｅｄ ｏｎ ＤＮＡ ｂｉｎａｒｙ ｓｔｒａｎｄｓ￣ ．Ｔｈｅ ｆｉｒｓｔ ａｐｐｒｏａｃｈ ｈｉｄ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ＤＮＡ ｂｉｎａｒｙ ｓｔｒａｎｄｓ ａｎｄ ｔｈｅ ｓｅｃｏｎｄ ａｐｐｒｏａｃｈ ｄｅ— ｓｉｇｎｅｄ ａ ｍｏｌｅｃｕｌａｒ ｃｈｅｃｋｓｕｍ．Ｃｈｅｎ ｐｒｏｐｏｓｅｄ ａ ｎｏ— ｖｅｌ ｄｅｓｉｇｎ ｏｆ ＤＮＡ——ｂａｓｅｄ ｍｏｌｅｃｕｌａｒ ｃｒｙｐｔｏｇｒａ—— ｐｈｙＬ ．Ｔｈｅｙ ｐｒｅｓｅｎｔｅｄ Ｃａｒｂｏｎ ｎａｎｏ—ｔｕｂｅ ｂａｓｅｄ ｍｅｓｓａｇｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ａｎｄ ＤＮＡ——ｂａｓｅｄ ｃｒｙｐｔｏｓｙｓ—— ｔｅｒｎ．Ｃｌｅｌｌａｎｄ ｈａｖｅ ｄｅｍｏｎｓｔｒａｔｅｄ ａｎ ａｐｐｒｏａｃｈ ｏｆ ｓｔｅｇａｎｏｇｒａｍ ｂｙ ｈｉｄｉｎｇ ｓｅｃｒｅｔ ｍｅｓｓａｇｅｓ ｅｎｃｏｄｅｄ ａｓ ＤＮＡ ｓｔｒａｎｄｓ ａｍｏｎｇ ａ ｍｕｌｔｉｔｕｄｅ ｏｆ ｒａｎｄｏｍ ＤＮＡｓ［”］． Ｈｏｗｅｖｅｒ，ｍｏｓｔ ｏｆ ｔｈｅｓｅ ｐｒｏｐｏｓａｌｓ ｉｍｐｌｅｍｅｎ— ｔｅｄ ｃｏｍｐｕｔｉｎｇ ｐｒｏｃｅｓｓｅｓ ｂｙ ｐｅｒｆｏｒｍｉｎｇ ａ ｓｅｒｉｅｓ ｏｆ ｂｉｏｃｈｅｍｉｃａｌ ｒｅａｃｔｉｏｎｓ ｏｎ ａ ｓｅｔ ｏｆ ＤＮＡ ｍｏｌｅｃｕｌｅｓ． ｗｈｉｃｈ ｒｅｑｕｉｒｅ ｈｕｍａｎ ｉｎｔｅｒｖｅｎｔｉｏｎ ａｔ ｅａｃｈ ｓｔｅｐ． Ｔｈｕｓ，ｔｈｅ ｄｉｆｆｉｃｕｌｔｉｅｓ ｏｆ ｓｕｃｈ ｍｅｔｈｏｄｓ ｆｏｒ ＤＮＡ ｃｏｍｐｕｔｉｎｇ ａｒｅ ｔｈａｔ ｔｈｅ ｌａｒｇｅ ｎｕｍｂｅｒｓ ｏｆ ｌａｂｏｒａｔｏｒｙ ｐｒｏｃｅｄｕｒｅｓ ａｎｄ ｔｈｅ ｔｉｍｅ ｃｏｎｓｕｍｉｎｇ，ｗｈｉｃｈ ｇｒｏｗ ｗｉｔｈ ｔｈｅ ｓｉｚｅ ｏｆ ｐｒｏｂｌｅｍｓ． ２ Ｔｉｌｅ Ｓｅｌｆ－Ａｓｓｅｍｂｌｅ Ｍｏｄｅｌ Ｔｈｅ ｔｉｌｅ ｓｅｌｆ—ａｓｓｅｍｂｌｙ ｍｏｄｅ１．ｗｈｉｃｈ ｉｓ ａ ｆｏｒ— ｍａｌ ｍｏｄｅｌ ｗｉｔｈ ｔｈｅ ｓｅｌｆ－ａｓｓｅｍｂｌｙ ｍｏｌｅｃｕｌｅｓ ｃｏｎ— ｓｔｒａｉｎｅｄ ｏｎ ａ ｓｑｕａｒｅ ｌａｔｔｉｃｅ。ｉｓ ａｎ ｅｘｔｅｎｓｉｏｎ ｆｏｒ ｔｈｅ ｔｉｌｉｎｇ ｔｈｅｏｒｙ ｏｆ Ｗａｎｇ ｔｉｌｅｓ［ ｔｈａｔ ｉｎｃｌｕｄｅ ａ ｓｐｅｃｉｆｉｃ ｇｒｏｗｔｈ ｍｅｃｈａｎｉｓｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｐｈｙｓｉｃｓ ｏｆ ｍｏｌｅｃｕ一 １ａｒ ｓｅｌｆ—ａｓｓｅｍｂｌｙ．Ｔｈｅ ｆｉｒｓｔ ｅｘｐｅｒｉｍｅｎｔａ１ ｄｅｍｏｎ— ｓｔｒａｔｉｏｎ ｏｆ ｃｏｍｐｕｔａｔｉｏｎ ｕｓｉｎｇ ＤＮＡ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｗａｓ ｉｎ［１３３．Ｉｔ ｇａｖｅ ａ ｔｗｏ ｌａｙｅｒ，１ｉｎｅａｒ ａｓｓｅｍｂｌｙ ０ｆ ＴＸ ｔｉｌｅｓ ｔｈａｔ ｐｅｒｆｏｒｍｅｄ ａ ｂｉｔ—ｗｉｓｅ ｃｕｍｕｌａｔｉｖｅ ＸＯＲ ｃｏｍｐｕｔａｔｉｏｎ．Ｂａｒｉｓｈ ｅｔ ａ１．ｄｅｍｏｎｓｔｒａｔｅｄ ａ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｓｙｓｔｅｍ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｔｈａｔ ｃｏｕｌｄ ｃｏｐｙ ａｎ ｉｎｐｕｔ ｈｉｔ ａｎｄ ｃｏｕｎｔ ｉｔ ｉｎ ｂｉｎａｒｙ［ ．Ｃｏｏｋ ｅｔ ａ１．ｕｓｅｄ Ｈｅ ｔｈｅｎ ｃｏｍｂｉｎｅｄ ｔｈｏｓｅ ｓｙｓｔｅｍｓ ｔｏ ｃｒｅａｔｅ ｔｗｏ ｎｅｗ ｓｙｓｔｅｍｓ ｗｉｔｈ ｍｏｒｅ ｃｏｍｐｌｅｘ ｂｅｈａｖｉｏｕｒ ｔｏ ｆａｃｔｏｒ ｎｕｍｂｅｒｓ ａｎｄ ｓｏｌｖｅ ｓｕｂｓｅｔ ｓｕｍ ｐｒｏｂｌｅｍｓ［ 一 ． Ｓｏ ＤＮＡ ｎａｎｏｓｔｒｕｅｔｕｒｅｓ ｐｒｏｖｉｄｅ ａ ｎｏｖｅ１ ｍｅｔｈ— ｏｄｏｌｏｇｙ ｆｏｒ ｕｓ ｔｏ ｒｅｓｏｌｖｅ ａｌ１ ｋｉｎｄｓ ｏｆ ｍａｔｈｅｍａｔｉｃａ１ ａｎｄ ｅｏｍｂｉｎａｔｏｒｉａ１ ｐｒｏｂｌｅｍｓ．Ｎｏｗ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ＤＮＡ ｔｉｌｅｓ ａｒｅ ｍｏｒｅ ａｎｄ ｍｏｒｅ ｕｎｉｖｅｒｓａ１． ３ Ｂｒｅａｋｉｎｇ ｔｈｅ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ Ａｌｇｏｒｉｔｈｍ ｉｎ ＤＮＡ Ｓｅｌｆ－Ａｓｓｅｍｂｌｅ Ｍｏｄｅｌｓ ３．１ Ｄｉｒｆｉｅ－Ｈｅｌｌｍａｎ Ｐｒｏｂｌｅｍ Ｉｎ ｔｈｅ ｓｉｍｐｌｅｓｔ ｆｏｒｍ ｏｆ ｔｈｅ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ｓｃｈｅｍｅ，ｅｖｅｒｙｏｎｅ ｉｓ ａｓｓｕｍｅｄ ｔｏ ｋｎｏｗ ａ ｌａｒｇｅ ｐｒｉｍｅ ｎｕｍｂｅｒ Ｐ ａｎｄ ｏｎｅ ｏｆ ｉｔｓ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｇ．Ｉｆ ｔｗｏ ｅｎｔｉｔｉｅｓ Ａ ａｎｄ Ｂ ｗｉｓｈ ｔｏ ａｇｒｅｅ ｏｎ ａ ｓｅｃｒｅｔ ｒａｎ— ｄｏｒａ ｖａｌｕｅ，ｔｈｅｎ Ｓｔｅｐ １． Ａ ｃｈｏｏｓｅｓ ａ ｒａｎｄｏｍ ｅｌｅｍｅｎｔ ∈ ｛１…Ｐ｝ａｎｄ ｓｅｎｄｓ ｔｏ Ｂ ｔｈｅ ｖａｌｕｅ ｇ ｒｏｏｄ Ｐ，ａｎｄ Ｓｔｅｐ ２． Ｂ ｃｈｏｏｓｅｓ ａ ｒａｎｄｏｍ ｅｌｅｍｅｎｔ Ｙ∈｛１… Ｐ｝ａｎｄ ｓｅｎｄｓ ｔｏ Ａ ｔｈｅ ｖａｌｕｅ ｇ ｍｏｄ Ｐ． Ｔｈｅ ｒａｎｄｏｍ ｖａｌｕｅ ｕｐｏｎ ｗｈｉｃｈ Ａ ａｎｄ Ｂ ｈａｖｅ ａｇｒｅｅｄ ｉｓ ｇ ｍｏｄ Ｐ，ｗｈｉｃｈ ｂｏｔｈ ｃａｎ ｃａｌｃｕｌａｔｅ： Ａ：Ａ ｃａｎ ｃａｌｃｕｌａｔｅ ｇ ｍｏｄ Ｐ ｆｒｏｍ ｚ ａｎｄ ｇ ｍｏｄ Ｐ ｖｉａ（ｇ ） ｍｏｄ ：ｇ ｒｏｏｄ Ｐ，ａｎｄ Ｂ：Ｂ ｃａｎ ｃａｌｃｕｌａｔｅ ｇ ｏｒｏｄ Ｐ ｆｒｏｍ Ｙ ａｎｄ ｇ ｒｏｏｄ Ｐ ｖｉａ（ｇ ｙ ｒｏｏｄ Ｐ—ｇ ｒｏｏｄ Ｐ． Ｔｈｅ Ｄｉｆｆｉｅ’—Ｈｅｌｌｍａｎ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ａｐｐｌｉｅａ—— ｔｉｏｎｓ ｈａｖｅ ｂｅｅｎ ｗｅｌｌ—ｓｔｕｄｉｅｄ ｉｎ ｔｈｅ ｗｏｒｌｄ ｏｆ ｃｏｒｎ— ｐｕｔａｔｉｏｎａｌ ｃｒｙｐｔｏｇｒａｐｈｙ．Ｉｔ ｈａｓ ｅｖｅｎ ｇａｉｎｅｄ ａｃｃｅｐｔ— ａｎｃｅ ｉｎ ａｐｐｌｉｅｄ ｃｒｙｐｔｏｇｒａｐｈｙ，ａｎｄ ｉｓ ｕｓｅｄ ｆｏｒ ｋｅｙ— ａｇｒｅｅｍｅｎｔ ｉｎ ｓｕｃｈ ｗｉｄｅｓｐｒｅａｄ ｐｒｏｔｏｃｏｌｓ ａｓ ＳＳＨ ａｎｄ ＴＬＳ．Ｈｅｒｅ，ａ ｍｏｌｅｃｕｌａｒ ｓｅｌｆ—ａｓｓｅｍｂｌｅ ｍｏｄｅｌ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｓｅａｒｃｈ ｔｈｅ ｓｅｃｒｅｔ ｅｌｅｍｅｎｔｓ．ｚ ａｎｄ ｙ． ｔｈｅｎ ｔｈｅ ｓｅｃｒｅｔ ｒａｎｄｏｍ ｖａｌｕｅ ｇ ｒｏｏｄ Ｐ ｃａｎ ｂｅ ｃａｌ— ｃｔ１１ａｔｅｄ． ３．２ Ｍｏｄｅｌｓ ｏｆ Ａｌｇｏｒｉｔｈｍｉｃ Ｓｅｌｆ－Ａｓｓｅｍｂｌｙ Ｔｈｅ ａｂｓｔｒａｃｔ ｏｆ ｔｉｌｅ ｓｅｌｆ－ａｓｓｅｍｂｌｙ ｍｏｄｅｌ， ｗｈｉｃｈ ｐｒｏｖｉｄｅｓ ａ ｒｉｇｏｒｏｕｓ ｆｒａｍｅｗｏｒｋ ｆｏｒ ａｎａｌｙｚｉｎｇ ａｌｇｏｒｉｔｈｍｉｃ ｓｅｌｆ—ａｓｓｅｍｂｌｙ，ｗａｓ ｏｒｉｇｉｎａｌｌｙ ｐｒｏｐｏｓｅｄ ｂｙ Ｒｏｔｈｅｍｕｎｄ ａｎｄ Ｗｉｎｆｒｅｅ［２０＿．Ｔｈｅ ｍｏｄｅｌ ｃｏｎｓｉｄ— ｅｒｓ ｔｈｅ ａｓｓｅｍｂｌｙ ｏｆ ｒｉｇｉｄ ｓｑｕａｒｅ ｏｂｊｅｃｔｓ ｏｒ ｔｉｌｅｓ． Ｅｌｅｍｅｎｔａｒｙ ｓｔｅｐｓ ｉｎ ｔｈｅ ｍｏｄｅ１ ａｒｅ ｓｉｍｐｌｅ ａｓｓｅｍ— ｂｌｉｅｓ ｓｔａｒｔｉｎｇ ｆｒｏｍ ａ ｓｉｎｇｌｅ ｓｅｅｄ ｔｉｌｅ ａｎｄ ｂｏｏｓｔｉｎｇ ２１１８ 计 算 机 学 报 ２００８拒 ｂｙ ｔｈｅ ａｄｄｉｔｉｏｎ ｏｆ ｓｉｎｇｌｅ ｔｉｌｅｓ，ｙｅｔ ｔｈｅ ｆｏｒｍｅｄ ｓｔｒｕｃｔｕｒｅｓ ｍａｙ ｂｅ ｓｕｒｐｒｉｓｉｎｇｌｙ ｃｏｍｐｌｅｘ．Ｅａｃｈ ｕｎｉｔ ｏｆ ａｓｓｅｍｂｌｙ ｉｓ ａ ｓｑｕａｒｅ ｗｉｔｈ ｇｌｕｅｓ ｏｆ ｖａｒｉｏｕｓ ｔｙｐｅｓ ｏｎ ｅａｃｈ ｅｄｇｅ．Ｔｈｅ ｔｉｌｅ“ｆｌｏａｔｓ”ｏｎ ａ ｔｗｏ ｄｉｍｅｎ— ｓｉｏｎａｌ ｐｌａｎｅ ａｎｄ ｔｗｏ ｔｉｌｅｓ ｍａｙ ｓｔｉｃｋ ｗｈｅｎ ｔｈｅｙ ｃｏｌ— ｌｉｄｅ ｉｆ ｔｈｅｉｒ ａｂｕｔｔｉｎｇ ｓｉｄｅｓ ｈａｖｅ ｃｏｍｐａｔｉｂｌｅ ｇｌｕｅｓ． Ｆｏｒｍａｌｌｙ，ａ ｔｉｌｅ ｏｖｅｒ ａ ｓｅｔ ｏｆ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｉｓ ａ ４－ｔｕｐｌｅ｛ Ｎ，盯Ｅ， ｓ， ｗ）∈ ｉｎｄｉｃａｔｉｎｇ ｒｅｓｐｅｃ— ｔｉｖｅｌｙ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｏｆ ｔｈｅ ｎｏｒｔｈ，ｅａｓｔ， ｓｏｕｔｈ ａｎｄ ｗｅｓｔ ｓｉｄｅｓ．Ａ ｐｏｓｉｔｉｏｎ ｉｓ ａｎ ｅｌｅｍｅｎｔ ｏｆ Ｚ ．Ｔｈｅ ｓｅｔ ｏｆ ｄｉｒｅｃｔｉｏｎｓ Ｄ一｛Ｎ，Ｅ，Ｓ，Ｗ｝ｉｓ ａ ｓｅｔ ｏｆ ｆｏｕｒ ｆｕｎｃｔｉｏｎｓ ｆｒｏｍ ｐｏｓｉｔｉｏｎｓ ｔｏ ｐｏｓｉｔｉｏｎｓ， ｉ．ｅ．Ｚ ｔｏ Ｚ ｓｕｃｈ ｔｈａｔ ｆｏｒ ａｌｌ ｐｏｓｉｔｉｏｎｓ（．２７，Ｙ）， Ｎ（ｘ， ）一（ｚ， ＋１），Ｅ（ｘ， ）一（ｚ＋１， ），Ｓ（ｘ， ）一 （ｚ，Ｙ一１），Ｗ（ｚ，Ｙ）一（ 一１， ）．Ｔｈｅ ｐｏｓｉｔｉｏｎｓ （ｚ， ）ａｎｄ（１ｚ ，ｙ ）ａｒｅ ｎｅｉｇｈｂｏｒｓ ｉｆｆ ３ｄ Ｅ Ｄ ｓｕｃｈ ｔｈａｔ ｄ（ｘ， ）一（ｚ ，Ｙ ）．Ｆｏｒ ａ ｔｉｌｅ ｔ，ｆｏｒ ｄＥＤ，ｗｅ ｒｅｆｅｒ ｔｏ ｂｄｄ（￡）ａｓ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎ ｏｆ ｔｉｌｅ ｔ ｏｎ ｄ’ｓ ｓｉｄｅ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｉｓ ｄｅｆｉｎｉｔｉｏｎ，ｔｉｌｅｓ ｍａｙ ｎｏｔ ｂｅ ｒｏｔａｔｅｄ．Ａ ｓｐｅｃｉａｌ ｔｉｌｅ ｅｍｐｔｙ一｛ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ， “ｌ１），ｒｅｐｒｅｓｅｎｔｓ ｔｈｅ ａｂｓｅｎｃｅ ｏｆ ａｌｌ ｏｔｈｅｒ ｔｉｌｅｓ． Ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｉｎｔｅｒａｃｔｉｏｎ ｂｅｔｗｅｅｎ ｔｉｌｅｓ．Ａ ｆｕｎｃｔｉｏｎ ｇ： ｔｏ爬，ｗｈｅｒｅ ｎｕｌｌ Ｅ ，ｉｓ ａ ｓｔｒｅｎｇｔｈ ｆｕｎｃｔｉｏｎ ｄｅｎｏｔｉｎｇ ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ，ｗｈｉｃｈ ｍａｙ ｂｅ ０，１，ｏｒ ２ （ｒｅｓｐｅｃｔｉｖｅｌｙ ｃａｌｌｅｄ ｎｕｌｌ， ｗｅａｋ， ａｎｄ ｓｔｒｏｎｇ ｂｏｎｄｓ）．Ｉｆ Ｖ ， Ｅ ，ｔｈｅｎ ｇ（盯，盯 ）一ｇ（ ，盯）ａｎｄ ｇ（ｎｕｌｌ，ｄ）一０． Ｌｅｔ Ｔ ｂｅ ａ ｆｉｎｉｔｅ ｓｅｔ ｏｆ ｔｉｌｅ—ｔｙｐｅｓ ｃｏｎｔａｉｎｉｎｇ ｔｈｅ ｅｍｐｔｙ ｔｉｌｅ．Ａ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｏｆ Ｔ ｉｓ ａ ｍａｐ ｆｒｏｍ Ｚ ｔｏ Ｔ．Ｆｏｒ ｔ Ｅ Ｔ，ｒ ｉｓ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｕｃｈ ｔｈａｔ Ｉ１ （ｉ，Ｊ）一ｔ ｉｆｆ（ｉ，Ｊ）一（ｚ，ｙ）ａｎｄ ｅｍｐｔｙ ｏｔｈｅｒｗｉｓｅ． Ａ ｔｉｌｅ ｓｙｓｔｅｍ ｉｓ ａ ｑｕａｄｒｕｐｌｅ Ｓ一（Ｔ，Ｓ，ｇ，ｒ）， ｗｈｅｒｅ Ｔ，ｇ ａｒｅ ａｓ ａｂｏｖｅ ａｎｄ Ｓ ｉｓ ａ ｓｅｔ ｏｆ ｓｕｐｅｒ ｔｉｌｅｓ ｃａｌｌｅｄ ｓｅｅｄ ｓｕｐｅｒｔｉｌｅｓ ｗｈｉｃｈ ａｓｓｅｍｂｌｙ ｂｅｇｉｎｓ ｗｉｔｈ， ｒ ｉｓ ｔｈｅ ｔｅｍｐｅｒａｔｕｒｅ． Ｉｆ Ａ ｉｓ ａ ｃｏｎｆｉｇｕｒａｔｉｏｎ，ｔｈｅｎ ｉｎ ｔｈｅ ｓｙｓｔｅｍ Ｓ，ａ ｔｉｌｅ ｔ ｃａｎ ｂｅ ａｔｔａｃｈｅｄ ｔｏ Ａ ａｔ ｐｏｓｉｔｉｏｎ（ｘ，ｙ）ａｎｄ ｐｒｏｄｕｃｅ ａ ｎｅｗ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ａ ｉｆｆ： １）（ｚ， ） Ａ， ２） ｄＥＤｇ（ｂｄｄ（ｆ），ｂｄｄ一１（Ａ（ （ ， ））））三三三ｒ， ３）Ｖ（ｕ， ）ＥＺ ；（ｕ， ）≠（ｚ，ｙ） Ａ （ｕ， ）一 Ａ（ｕ， ），ａｎｄ ４）Ａ （ｚ， ）一ｆ． Ｔｈａｔ ｉｓ。ａ ｔｉｌｅ ｃａｎ ｂｅ ａｔｔａｃｈｅｄ ｔｏ ａ ｃｏｎｆｉｇｕｒａ— ｔｉｏｎ ｏｎｌｙ ｉｎ ｅｍｐｔｙ ｐｏｓｉｔｉｏｎｓ ａｎｄ ｉｆ ｔｈｅ ｔｏｔａｌ ｓｔｒｅｎｇｔｈ ｏｆ ｔｈｅ ａｐｐｒｏｐｒｉａｔｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｏｎ ｔｈｅ ｔｉｌｅｓ ｉｎ ｎｅｉｇｈｂｏｒｉｎｇ ｐｏｓｉｔｉｏｎｓ ｍｅｅｔｓ ｏｒ ｅｘｃｅｅｄｓ ｔｈｅ ｔｅｍｐｅｒａｔｕｒｅ ｌ－． Ｇｉｖｅｎ ａ ｔｉｌｅ ｓｙｓｔｅｍ Ｓ一（Ｔ，Ｓ，ｇ，ｒ），ａ ｓｅｔ ｏｆ ｔｉｌｅｓ Ｉ１，ａｎｄ ａ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓ：Ｚ ｔｏ ｒ，ｉｆ ｔｈｅ ａｂｏｖｅ ｃｏｎｄｉｔｉｏｎｓ ａｒｅ ｓａｔｉｓｆｉｅｄ，ｏｎｅ ｍａｙ ａｔｔａｃｈ ｔｉｌｅｓ ｏｆ Ｔ ｔｏ Ｓ．Ｃｏｎｆｉｇｕｒａｔｉｏｎｓ ｐｒｏｄｕｃｅｄ ｂｙ ｒｅｐｅａｔｅｄ ａｔ— ｔａｃｈｍｅｎｔｓ ｏｆ ｔｉｌｅｓ ｆｒｏｍ Ｔ ａｒｅ ｓａｉｄ ｔｏ ｂｅ ｐｒｏｄｕｃｅｄ ｂｙ Ｓ ｏｎ Ｓ．Ｉｆ ｔｈｉｓ ｐｒｏｃｅｓｓ ｔｅｒｍｉｎａｔｅｓ，ｔｈｅ ｃｏｎｆｉｇｕ— ｒａｔｉｏｎ ｉｓ ｃａｌｌｅｄ ｔｈｅ ｆｉｎａ１ ｃｏｎｆｉｇｕｒａｔｉｏｎ．Ｉｆ ａｌｌ ｐｏｓｓｉ— ｂｌｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎｓ ａｒｅ ｉｄｅｎｔｉｃａｌ，ｔｈｅ ｔｉｌｅ ｓｙｓ— ｔｅｍ Ｓ ｉｓ ｓａｉｄ ｔｏ ｐｒｏｄｕｃｅ ａ ｕｎｉｑｕｅ ｆｉｎａｌ ｅｏｎｆｉｇｕｒａ— ｔｉｏｎ ｏｎ Ｓ． ３．３ Ｍｏｄｕｌａｒ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ Ｕｓｉｎｇ Ｓｅｌｆ－Ａｓｓｅｍｂｌｅ ＤＮＡ ｓｅｌｆ～ａｓｓｅｍｂｌｅ ｍｅｔｈｏｄｓ ｃｏｕｌｄ ｂｅ ｕｓｅｄ ｔｏ ｓｅａｒｃｈ ｔｈｅ ｒａｎｄｏｍ ｅｌｅｍｅｎｔ ｚ ｗｈｅｎ ｗｅ ｋｎｏｗ ｔｈｅ ｖａｌｕｅ ｇ．Ｐ．ａｎｄ ｇ ．Ｗｅ ｃｏｎｓｔｒｕｃｔ ａ ＤＮＡ ｓｅｌｆ－ａｓ— ｓｅｍｂｌｅ ｓｙｓｔｅｍ Ｓ＝（Ｔ，Ｓ，ｇ，ｒ）ｔｏ ｆｏｒｍ ｔｈｅ ｉｎｔｅｇｅｒｓ ｐｅｒｍｕｔａｔｉｏｎ ｆｒｏｍ １ ｔｏ Ｐ’——１ ｂａｓｅｄ ｏｎ ｔｈｅ ｔｒｕｔｈ ｔａ’— ｂｌｅ ｏｆ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｎｕｍｂｅｒｓ ｍｏｄｕｌａｒ Ｐ：ｇ ｍｏｄ Ｐ， ｇ ｍｏｄ Ｐ，…，ｇ ＿。ｒｏｏｄ Ｐ． Ａ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓ ｉｓ ｄｅｓｉｇｎｅｄ，ｉｆ ｃｏｎｄｉ— ｔｉｏｎｓ ａｒｅ ｓａｔｉｓｆｉｅｄ，ｔｈｅ ｔｉｌｅｓ ｉｎ ｔｈｅ ｓｅｔ Ｔ ｃａｎ ｂｅ ａｔ— ｔａｃｈｅｄ ｔｏ Ｓ ｏｎｅ ｂｙ ｏｎｅ ｕｎｔｉ１ ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａ— ｔｉｏｎｓ ｐｒｏｄｕｃｅ．Ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎｓ ｃａｎ ｂｅ ｅｘ— ｔｒａｃｔｅｄ，ａｎｄ ｔｈｅｎ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｖａｌｕｅ ｇ ，ａｎｄ ｇｙ．ｗｅ ｅｘｔｒａｃｔ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｌｅｎｇｔｈ ＤＮＡ ｓｅ— ｑｕｅｎｃｅ ｂｙ ＰＣＲ，ｔｈｅ ｌｅｎｇｔｈ ｊ ｕｓｔ ｍａｐｓ ｔｏ ｔｈｅ ｃｏｒｒｅ— ｓｐｏｎｄｉｎｇ ｒａｎｄｏｍ ｅｌｅｍｅｎｔ ｏｒ Ｙ．Ｔｈｅ ｓｙｓｔｅｍ ｕｓｅ ＠（１）ｔｙｐｅｓ ｔｏ ｃｏｎｓｔｒｕｃｔ Ｉ１ ａｎｄ ０（Ｐ）ｔｏ ｃｏｎｓｔｒｕｃｔ Ｔ．Ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｃａｎ ｂｅ ｒｅｆｅｒｒｅｄ ｔｏ ｔｈｅ ｕｎｉｑｕｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｃｏｒｏｌｌａｒｙ ， ｗｈｉｃｈ ｓｔａｔｅｓ ｔｈａｔ ｉｆ ａｌｌ ｔｈｅ ｔｉｌｅｓ ｉｎ ａ ｓｙｓｔｅｍ ｈａｖｅ ｕｎｉｑｕｅ ｅａｓｔ—ｓｏｕｔｈ ｏｒ ｗｅｓｔ—ｓｏｕｔｈ ｂｉｎｄｉｎｇ ｄｏｍａｉｎ ｐａｉｒｓ，ｔｈａｔ ｓｙｓｔｅｍ ａｌｗａｙｓ ｐｒｏｄｕｃｅｓ ａ ｕｎｉｑｕｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｏｎ ｓｏｍｅ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎｓ． Ｔｈｅ ｓｅｔ ｏｆ ｒ ｉｓ ｄｅｓｉｇｎｅｄ ａｓ：Ｉ１一｛Ｓ一＜ｓ，ｎｕｌｌ， ｎｕｌｌ，ｎｕｌｌ＞，Ｅ一＜ｅ，ｎｕｌｌ，ｎｕｌｌ，ｎｕｌ１），Ｇ一＜ｇ，ｎｕｌｌ， ｎｕｌｌ，ｎｕｌ１），ＳＬ一＜ｎｕｌｌ，１，ｓ，ｎｕｌ１），ＥＲ一（ｎｕｌｌ， ｎｕｌｌ，ｅ，１））．Ｔｈｅ ５ ｋｉｎｄｓ ｏｆ ｔｉｌｅｓ ａｒｅ ｕｓｅｄ ｔｏ ｃａｌｃｕ— ｌａｔｅ ｔｈｅ ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｆｉｇ．１（ａ）ｓｈｏｗｓ ａ ｇｒａｐｈｉｃａｌ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｒ，ｔｈｅ ｖａｌｕｅ ｉｎ ｔｈｅ ｍｉｄ— ｄｉｅ ｏｆ ｅａｃｈ ｔｉｌｅ ｔ ｒｅｐｒｅｓｅｎｔｓ ｔｈａｔ ｔｉｌｅ’ｓ （ｔ）ｖａｌｕｅ． Ｔｈｅｓｅ ｔｉｌｅｓ ｗｉｔｈ ｏｎｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ，ａｒｅ ｄｅｎｏｔｅｄ ａｓ ｂｄ，ａｎｄ ｌｅｔ ６ Ｎ（ ）ｂｅ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎ．Ｔｈｅ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｆｏｒ ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ｉｓ ｓｈｏｗｎ ｉｎ Ｆｉｇ．１（ｂ），ｉｎ ｗｈｉｃｈ ｔｈｅ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｇ ａｃｔｓ ａｓ ｃｏｎｔｉｎｕｏｕｓ ｍｕｌｔｉｐｌｉｅｒ．Ｔｗｏ ｓｐｅｃｉａｌ ｔｉｌｅｓ ａｒｅ ｄｅｎｏｔｅｄ ａｓ ｔｈｅ ｓｙｍｂｏｌｓ‘Ｓ’（ｗｉｔｈ ａ ｓｔｒｏｎｇ ｂｏｎｄ， ａｎｄ ｔｈｒｅｅ ｎｕｌｌ ｂｏｎｄｓ）ａｎｄ‘Ｅ’（ｗｉｔｈ ａ ｗｅａｋ ｂｏｎｄ， ａｎｄ ｔｈｒｅｅ ｎｕｌｌ ｂｏｎｄｓ）ｒｅｓｐｅｃｔｉｖｅｌｙ，ａｒｅ ｃａｌｌｅｄ ｂｏｕｎｄａｒｙ ｔｉｌｅｓ，ｗｈｉｃｈ ａｒｅ ｕｓｅｄ ｔｏ ｄｅｎｏｔｅ ｔｈｅ ｓｔａｒｔ ａｎｄ ｔｈｅ ｅｎｄ ｏｆ ｉｎｐｕｔ ｎｕｍｂｅｒｓ．Ｔｈｅｙ ｓｅｔ ｌｉｍｉｔｓ ｏｎ ｔｈｅ ｅｘｔｅｎｔ ｏｆ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｒ ｐａｔｔｅｒｎｉｎｇ．ａｎｄ ｗｉｌｌ ｆａｃｉｌｉｔａｔｅ ａ ｍｏｄｕｌａｒ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｐｒｏｃｅｓｓ．Ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｆｏｒ ｓｉｄｅ ｗｉｔｈ ｄｏｕｂｌｅ ｌｉｎｅ ｉｓ ｓｅｔ ２．Ｔｈｅｓｅ ａｒｅ ｔｈｅ ｆｏｒｍｓ ｗｅ ｓｔｏｒｅ ａｌｌ ｉｎｐｕｔｓ ｉｎ ｏｕｒ ｓｙｓｔｅｍ． １２期 陈智华：基于ＤＮＡ计算自组装模型的Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ算法破译 Ｆ 【 ２１１９ Ｓ 图圈 ｇ Ｇ （ａ） Ｅ ｇ ａ Ｓ ｔ 皿￣－－－Ｔｏｔｌｅ（…ｐ－圆１）ｔｉｌｅｓ ｈ ｅ Ｃ （ ｔ Ｆｉｇ．２口ｉｓ ｔｈｅ ｆａｃｉｅｎｄ，ｂ ｉｓ ｔｈｅ ｍｕｌｔｉｐｌｉｅｒ， ：（口×６）ｒｏｏｄｐ ａｎｄ ｔｈｅ ｔｉｌｅ’ｓ ｖａｌｕｅ口一“ ｎ Ｕ ｏ Ｕ Ｓ ｉｔｓ ｔｏｐ．Ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏｍａｉｎｓ ｆｏｒ ｓｉｄｅ ｗｉｔｈ ｄｏｕｂｌｅ ｌｉｎｅ ｉｓ ｓｅｔ ２．Ｆｉｇ．３（ｂ）ｓｈｏｗｓ ｔｈｅ ｍ Ｕ ｔ Ｆｉｇ．２ ｓｈｏｗｓ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｔｉｌｅ’ｓ ｆｏｒｍ ｕｓｅｄ ｉｎ ｐ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓ ｆｏｒ ｔｈｅ ｃｏｎｔｉｎｕｏｕｓ ｍｕｌｔｉｐｌｙｉｎｇ ｛ｈｅ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｇ ｍｏｄｕｌａｒ Ｐ．Ｆｉｇ．３（ｃ）ｓｈｏｗｓ ａ ｓａｍｐｌｅ ｏｆ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｗｈｉｃｈ ｅｎｃｏｄｅｓ ｔｈｅ 一 ３ ｍｏｄ ７．Ｔｈｅ ｓｔａｒｔ ｔｉｌｅ（ｂｏｕｎｄａｒｙ ｔｉｌｅ）ｗｈｉｃｈ ｉｓ ｄｅｓｃｒｉｂｅｄ ａｓ ｔｈｅ ｓｔａｒｔｉｎｇ ｐｏｉｎｔ ｉｓ ｏｎ ｔｈｅ ｌｅｆｔ ｓｉｄｅ． Ｎｏｔｅ ｔｈａｔ ｏｎｌｙ ｏｎｅ ｔｉｌｅ ｍａｙ ｂｅ ａｔｔａｃｈｅｄ ｔｏ ｔｈｉｓ ｃｏｎ— ｔｈｅ ｓｙｓｔｅｍ．Ｉｎ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｔｉｌｅ，ｔｈｅ ｗｅｓｔ ｓｉｄｅ ｅ ｒ ｓｔｏｒｅｓ ｔｈｅ ｖａｌｕｅ ｏｆ ｆａｃｉｅｎｄ，ｔｈｅ ｓｏｕｔｈ ｓｉｄｅ ｉｓ ｔｈｅ ｍｕｌｔｉｐｌｉｅｒ。ａｎｄ ｒｅｓｕｌｔ ｏｆ ｕ一（ａ＊６）ｒｏｏｄ Ｐ ｉｓ ｓｔｏｒｅｄ ｉｎ ｔｈｅ ｅａｓｔ ｓｉｄｅ．Ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｔｈｅ ｂｉｎｄｉｎｇ ｄｏ— ｍａｉｎｓ ｆｏｒ ｓｉｄｅ ｗｉｔｈ ｓｉｎｇｌｅ ｌｉｎｅ ｉｓ ｓｅｔ １．Ｔｈｅ ｃａｌｃｕ— ｌａｔｉｏｎ ｔｉｌｅｓ ａｒｒａｎｇｅ ｆｉｇｕｒｅｓ ｉｎ ｃａｌｃｕｌａｔｉｎｇ ｒｅｓｕｌｔｓ， ｆｉｇｕｒａｔｉｏｎ ｂｅｃａｕｓｅ ｒ一２．Ｆｉｇ．３（ｄ）ｇｉｖｅｓ ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｆｏｒ ｔｈｅ ｅｘａｍｐｌｅ，ａｎｄ ｔｈｅ ｒｅｐｏｒｔ ｓｔｒａｎｄ ｇｉｖｅｓ ｕｓ ｔｈｅ ｐｅｒｍｕｔａｔｉｏｎ：１×３ ｒｏｏｄ ７，１× ３ ｒｏｏｄ ７．…．１×３ ｍｏｄ ７． ｗｈｉｃｈ ｗｉｌ１ ｂｅ ｅｘｐｌａｉｎｅｄ ｉｎ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｓｅｃｔｉｏｎｓ． Ｆｉｇ．３（ａ）ｓｈｏｗｓ ｔｈｅ ｔｗｏ ｂｏｕｎｄａｒｙ ｔｉｌｅｓ ｕｓｅｄ ｉｎ ｔｈｅ ｔｉｌｅ ｓｙｓｔｅｍ ａｎｄ ｅａｃｈ ｔｉｌｅ’ｓ ｎａｍｅ ｉｓ ｗｒｉｔｔｅｎ ｏｎ ｂ１ ｂ２ 母口 （ａ）ｂｏｕｎｄａｒｙ ｔｉｌｅｓ （ｃ）ａ ｓａｍｐｌｅ ｏｆ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｆｏｒ ＝３ ｍｏｄ ７ （ｂ）ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓ （ｄ）ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｆｉｇ．３ Ｍｏｄｕｌａｒ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ｔｉｌｅ ｓｙｓｔｅｍ Ｌｅｍｍａ １．Ｌｅｔ 一｛１，２，…，Ｐ～１｝ａｎｄ Ｔ ｂｅ ｆ５（１，一１）一Ｅ； ｔｈｅ ｓｅｔ ｏｆ ｔｉｌｅｓ ｄｅｆｉｎｅｄ ｂｙ Ｆｉｇ．１（ｂ），ｌｅｔ ｇ一１，ｒ一２ ａｎｄ Ｓ ｂｅ ａ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ．Ｌｅｔ Ｙ—ｇ ｒｏｏｄ Ｐ， ｈｅｒｅ ｔｈｅ ｐｒｉｍｅ ｎｕｍｂｅｒ Ｐ ｄｅｔｅｒｍｉｎｅｓ ｔｈｅ ｓｅｔ’ｓ ｓｃａｌｅ ｌＳ（～Ｐ，一１）一Ｓ，Ｓ（一Ｐ，０）一ＳＬ； ｌ Ｖｉ∈｛１，…， 一１｝，ｓ（一ｉ，一１）一ｇ； ｌＦｏｒ ａｌｌ ｏｔｈｅｒ（ｚ， ）ＥＺ ，Ｓ（ｘ，Ｙ）＝ｅｍｐｔｙ． Ｉｔ ｉｓ ｃｌｅａｒ ｔｈａｔ ｔｈｅｒｅ ｉｓ ｏｎｌｙ ｏｎｅ ｐｏｓｉｔｉｏｎ ｗｈｅｒｅ ａ ｔｉｌｅ ｍａｙ ｂｅ ａｔｔａｃｈｅｄ ｔｏ Ｓ，ａｎｄ ａｆｔｅｒ ｔｈａｔ ｔｉｌｅ ａｔｔａ— ｏｆ Ｔ．Ｌｅｔ Ｓ一（Ｊｒ，Ｓ，ｇ，ｒ），ｔｈｅｎ，ｔｈｅｒｅ ｍｕｓｔ ｅｘｉｓｔ ｓｏｍｅ（ｚｏ， ０）ＥＺ ｓｕｃｈ ｔｈａｔ：Ｓ（ｚ。＋１， ０—１）一 Ｅ，Ｓ（ｘ０一Ｐ，ｙｏ一１）：Ｓ，Ｓ（ｚ０一Ｐ，ｙｏ）一ＳＬ；ｆｏｒ ｃｈｅｄ ｔｈｅｒｅ ｗｉｌｌ ａｌｓｏ ｏｎｌｙ ｂｅ ａ ｓｉｎｇｌｅ ｐｏｓｉｔｉｏｎ ｗｈｅｒｅ ａｌｌ ｉＥ｛１，２，…，Ｐ一１｝，６ Ｎ（Ｓ（ｚ。一ｉ，ｙ。一１）一ｇ， ａｎｄ ｏｔｈｅｒ ｐｏｓｉｔｉｏｎｓ（ｚ， ），（ ， ） Ｓ．Ｔｈｅｎ Ｓ ｐｒｏ— ｄｕｅｅｓ ａ ｕｎｉｑｕｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｆ ｂａｓｅｄ ｏｎ Ｓ ａｎｄ ｃａｎ ｇｉｖｅｓ ｕｓ ｔｈｅ ｐｅｒｍｕｔａｔｉｏｎ ｏｆ ｍｏｄｕｌａｒ Ｐ ｍｕｌｔｉｐｌｉ～ ａ ｔｉｌｅ ｍａｙ ｂｅ ａｔｔａｃｈｅｄ．Ｂｙ ｉｎｄｕｃｔｉｏｎ，ｆｏｒ Ｖ￡∈丁， ｔｈｅ ｄｕｐｌｅ（ｂｄｓ（￡），ｂｄｗ（ｆ）＞ｉｓ ｕｎｉｑｕｅ，ａｎｄ ｂｅｃａｕｓｅ ｒ＝２，ｉｔ ｆｏｌｌｏｗｓ ｔｈａｔ Ｓ ｐｒｏｄｕｃｅｓ ａ ｕｎｉｑｕｅ ｆｉｎａｌ ｃｏｎ— ｆｉｇｕｒａｔｉｏｎ ｏｎ Ｓ．Ｌｅｔ ｔｈａｔ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｂｅ Ｆ． ｃａｔｉｏｎ，ａｎｄ ｔｈｅ ａｓｓｅｍｂｌｙ ｔｉｍｅ ｉｓ＠（Ｐ一１）． Ｖ￡∈Ｔ，ｔｈｅ ｏｕｔｐｕｔ ｉｓ ｔｈｅ ｐｒｏｄｕｃｔ ｏｆ ｉｔｓ ｆｒｏｎｔ ｔｉｌｅ’ｓ ｏｕｔｐｕｔ ａｎｄ ｔｈｅ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｇ ｍｏｄｕｌａｒ Ｐｒｏｏｆ． Ｃｏｎｓｉｄｅｒ ｔｈｅ ｔｉｌｅ ｓｙｓｔｅｍ三＝｛１，２，…， Ｐ一１｝．Ｌｅｔ ｒ一｛Ｓ一＜ｓ，ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ＞，Ｅ一＜ｅ， ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ＞，Ｇ一（ｇ，ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ＞，ＳＬ一 Ｐ，ｔｈａｔ ｉｓ Ｖ１ ｉ Ｐ一１，ｂｄＥ（Ｆ（一ｉ，０））一 （ｂｄ￡（Ｆ（一ｉ一１，０））×ｇ）ｒｏｏｄ Ｐ．Ｗｈｅｎ ｔｈｅ ｒｉｇｈｔ ｂｏｕｎｄａｒｙ ｔｉｌｅ ＥＲ一（ｎｕｌｌ，ｎｕｌｌ，ｅ，１＞ｉｓ ａｔｔａｃｈｅｄ ｔｏ （ｎｕｌｌ，１，ｓ，ｎｕｌｌ＞，ＥＲ一＜ｎｕｌｌ， ｕｌｌ，ｅ，１＞｝． Ｌｅｔ ｔｈｅ ｓｅｅｄ ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓ：Ｚ ＋ｒ： ｔｈｅ ｐｏｓｉｔｉｏｎ（１，Ｏ），ｔｈｅ ｓｅｌｆ—ａｓｓｅｍｂｌｅ ｐｒｏｃｅｓｓ ｗｉｌ１ ２１２Ｏ 计 算 机 学 报 ２００８伍 ｔｅｒｍｉｎａｔｅ．Ｉｔ ｉｎｄｉｃａｔｅｓ ｔｈａｔ Ｓ一（Ｔ，Ｓ，ｇ，ｒ）ｃａｎ ｐｒｏ— ｄｕｃｅ ａ ｕｎｉｑｕｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｏｎ Ｓ ａｎｄ ｇｉｖｅ ｔｈｅ ｐｅｒｍｕｔａｔｉｏｎ ｏｆ １×ｇ ｍｏｄ Ｐ，１×ｇ ｒｏｏｄ Ｐ，…，１× ｇ 一ｍｏｄ Ｐ．Ｂｅｃａｕｓｅ ｏｆ ｒ一２，ｏｎｌｙ ３ ｔｉｌｅ ｗｉｔｈ ｔｗｏ ｓｕｆｆｉｃｉｅｎｔｌｙ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｅａｃｈ—ｏｔｈｅｒ．ＴＡＥ ｔｉｌｅｓ ａｒｅ ｕｓｅｄ ｉｎ ｏｕｒ ｔｉｌｅ ｓｙｓｔｅｍ．Ｆｉｇ．４（ａ）ｓｈｏｗｓ ｔｈｅ ａｂｓｔｒａｃｔ ｓｔｒｕｃｔｕｒｅ．Ｅａｃｈ ｔｉｌｅ ｉｓ ｍａｄｅ ｕｐ ｏｆ ｓｉｘ ＤＮＡ ｓｔｒａｎｄｓ．ａｎｄ ｔｈｅｒｅ ａｒｅ ｓｉｘ ｓｔｉｃｋｙ ｅｎｄｓ ｔｈａｔ ｃａｎ ｃｏｍｐｌｅｍｅｎｔ ａｎｄ ｌｉｇａｔｅ ｔｏｇｅｔｈｅｒ ｉｎ ｔｈｅ Ｗａｔｓｏｎ— Ｃｒｉｃｋ ｓｅｎｓｅ．Ｅａｃｈ ｔｉｌｅ ｃａｎ ｈａｖｅ ｆｒｏｍ ｏｎｅ ｔｏ ｓｉｘ ｓｔｉｃｋｙ ｅｎｄｓ．Ｎｏｎ—ｕｓｅｄ ｓｔｉｃｋｙ ｅｎｄｓ ｃａｎ ｂｅ ｂｅｎｔ ｉｎｔｏ ｎｅｉｇｈｂｏｒｓ ｍａｙ ａｔｔａｃｈ ａｔ ａｎｙ ｔｉｍｅ ｉｎ ｔｈｉｓ ｓｙｓｔｅｍ． Ａｎｄ ｔｈｅｎ ｎｏ ｔｉｌｅ ｍａｙ ｂｅ ａｔｔａｃｈｅｄ ｔｏ Ｓ ｕｎｔｉｌ ｉｔｓ ｌｅｆｔ ｎｅｉｇｈｂｏｒ ｈａｓ．Ｔｈｕｓ ｔｈｅ ａｓｓｅｍｂｌｙ ｔｉｍｅ ｔｏ ｇｉｖｅ ｕｓ ｔｈｅ ｐｅｒｍｕｔａｔｉｏｎ ｉｓ 一１ ｓｔｅｐｓ． ３．４ Ｅｘｔｒａｃｔｉｎｇ ｔｈｅ Ｒｅｐｏｒｔ Ｓｔｒａｎｄ 口 ｌｏｏｐｓ ｓｏ ｔｈａｔ ｔｈｅｙ ａｒｅ ｎｏｔ ｕｓｅｄ ａｓ ｓｔｉｃｋｙ ｅｎｄｓ． Ｎｏｔｅ ｔｈａｔ，ａ ｓｉｎｇｌｅ ｓｔｒａｎｄ ｏｆ ＤＮＡ（ｓｈｏｗｎ ｉｎ Ｆｉｇ．４（ｂ））ｐａｓｓｅｓ ｔｈｒｏｕｇｈ ｅａｃｈ ｔｉｌｅ ａｓｓｅｍｂｌｅｄ ａｎｄ ｔｈｕｓ ｃｏｎｔａｉｎｓ ａｌｌ ｉｎｔｅｇｅｒｓ ｓｔｏｒｅｄ ａｓ ｔｉｌｅ’ｓ ｖａｌｕｅ． Ｔｈｉｓ ｓｉｎｇｌｅ ｓｔｒａｎｄ ｏｆ ＤＮＡ ｉｓ ｃａｌｌｅｄ ｒｅｐｏｒｔｅｒ Ｔｏ ｉｍｐｌｅｍｅｎｔ ｏｕｒ ｍｅｔｈｏｄ ｏｆ ｍｏｄｕｌａｒ ｍｕｌｔｉ— ｐｌｉｃａｔｉｏｎ，ｗｅ ｈａｖｅ ｔｏ ｆｉｎｄ ｓｕｉｔａｂｌｅ ｎｕｃｌｅｏｔｉｄｅ ｓｅ— ｑｕｅｎｃｅｓ ｆｏｒ ｅｎｃｏｄｉｎｇ ａｌｌ ｔｈｅ ｓｙｍｂｏｌｓ ｕｓｅｄ ｉｎ ｏｕｒ ｃｏｍｐｕｔａｔｉｏｎ．Ａｎｄ ｗｅ ｈａｖｅ ｔｏ ｅｎｓｕｒｅ ｔｈａｔ ｔｈｅｓｅ ｓｅ— ｑｕｅｎｃｅｓ（ａｎｄ ｔｈｅｉｒ ｃｏｍｐｌｅｍｅｎｔａｒｙ ｓｅｑｕｅｎｃｅｓ）ａｒｅ ｓｔｒａｎｄ。ａｎｄ ｉｓ ａｌｓｏ ｔｈｅ ｒｅｓｕｌｔ ｓｔｒａｎｄ ｗｅ ｎｅｅｄ． ＴＡＥ ｔｉｌｅ ｓｔｒｕｃｔｕｒｅ ｎ （ｆ１）ＴＡＥｔｉｌｅ 三 Ｔｈｅ ａｂｓｔｒａｃｔ ｏｆ ＴＡＥ ｔｉｌｅ ＼ （ｂ）ｔｈｅ ｓｔｒｕｃｔｕｒｅｓ ｏｆ ｔｗｏ ＴＡＥ ｔｉｌｅ ａｓｓｅｍｂｌｅｄ Ｆｉｇ．４ Ｓｔｒｕｃｔｕｒｅｓ ｏｆ ｔｗｏ ＴＡＥ ｔｉｌｅ ａｓｓｅｍｂｌｅｄ Ａｔ ｔｈｅ ｅｎｄ ｏｆ ｓｅｌｆ－ａｓｓｅｍｂｌｅ ｐｒｏｃｅｓｓ，ｌｉｇａｓｅ ｉｓ Ｔｏ ｏｕｔｐｕｔ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｗｅ ｗｏｕｌｄ ｕｓｅ ａ ｍｏｄｉｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ ｓｔａｎｄａｒｄ ｓｅｑｕｅｎｃｅ— ｒｅａｄｉｎｇ ｏｐｅｒａｔｉｏｎ ｔｈａｔ ｕｓｅｓ ａ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ＰＣＲ ａｎｄ ｇｅ１ ｅ１ｅｃｔｒｏｐｈｏｒｅｓｉｓ．Ｕｓｉｎｇ ＰＣＲ ｗｅ ｃａｎ ｏｂｔａｉｎ ｓｔｒａｎｄｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｌｅｎｇｔｈｓ ｒｅｐｒｅｓｅｎｔｉｎｇ ｔｈｅ ｄｉｆｆｅｒ— ｅｎｔ ｅｘｐｏｎｅｎｔ ｚ ｉｎ ｔｈｅ ｒｅｓｕｌｔ ｓｔｒａｎｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｋｎｏｗｎ ｖａｌｕｅｓ ｏｆ ｔｈｅ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｇ ａｎｄ ｔｈｅ ａｄｄｅｄ ｔｏ ｓｅａｌ ｔｈｅ ｊｏｉｎｔｓ（ｓｅｅ Ｆｉｇ．５）ａｎｄ ｔｈｅｎ，ｔｈｅ ｔｅｍｐｅｒａｔｕｒｅ ｏｆ ｔｈｅ ｃｈａｍｂｅｒ ｉｓ ｉｎｃｒｅａｓｅｄ ｔｏ ｂｒｅａｋ ｕｐ ｔｈｅ ｔｉｌｅ ｓｔｒｕｃｔｕｒｅ ｉｎｔｏ ｓｉｎｇｌｅ ｓｔｒａｎｄｓ．Ｔｈｅ ｒｅｓｕｌｔ ｓｔｒａｎｄ ｉｓ ｔｈｅｎ ｅｘｔｒａｃｔｅｄ ｂｙ ａｆｆｉｎｉｔｙ ｐｕｒｉｆｉｃａｔｉｏｎ ｕｓｉｎｇ ｔｈｅ ｃｏｍｐｌｅｍｅｎｔ ｏｆ ｔｈｅ‘ＲＥＳ’ｓｅｑｕｅｎｃｅ．Ｔｈｅ ‘ＲＥＳ’ｎｕｃｌｅｏｔｉｄｅ ｓｅｑｕｅｎｃｅ ｗｏｕｌｄ ｃｏｎｔａｉｎ ｔｈｅ ｓｉｔｅ ｏｆ ａ ｒｅｓｔｒｉｃｔｉｏｎ ｅｎｚｙｍｅ ａｔ ｔｈｅ ｅｎｄ，ｓｏ ｔｈａｔ ｔｈｅ ‘ＲＥＳ’ｐｏｒｔｉｏｎ ｃａｎ ｂｅ ｃｕｔ—ｏｆｆ ｆｒｏｍ ｔｈｅ ｒｅｓｕｌｔ ｓｔｒａｎｄ ｂｙ ａｐｐｌｙｉｎｇ ｔｈｅ ａｐｐｒｏｐｒｉａｔｅ ｒｅｓｔｒｉｃｔｉｏｎ ｅｎ— ｚｙｍｅ．Ａｓ ａ ｒｅｓｕｌｔ ｗｅ ｗｉｌｌ ｇｅｔ ａｎ ｓｓＤＮＡ ｃｏｎｔａｉｎｉｎｇ ａｌｌ ｔｈｅ ｅｎｃｏｄｅｄ ｉｎｔｅｇｅｒｓ ｉｎ ｓｏｍｅ ｐｅｒｍｕｔａｔｉｏｎ．Ｔｈｉｓ ｓｔｒａｎｄ ｃａｎ ｔｈｅｎ，ｂｅ ｕｓｅｄ ｉｎ ｆｕｒｔｈｅｒ ｃｏｍｐｕｔａｔｉｏｎｓ． Ｔｈｅ ｒｅｐｏｒｔ ｓｔｒａｎｄ ｐａｓｓｉｎｇ ｔｈｒｏｕｇｈ ａｌｌ ｔｉｌｅｓ ｒｅｓｕｌｔ ｖａｌｕｅ Ｙ，ｗｅ ｓｔａｒｔ ＰＣＲ．Ｔｈｅ ｐａｒｔ ｏｆ ｒｅｐｏｒｔ ｓｔｒａｎｄ“ｇ—ｙ’’ｃａｎ ｂｅ ａｍｐｌｉｆｉｅｄ ｂｙ ＰＣＲ ｍｅｔｈｏｄ ｂｙ ｐｕｔｔｉｎｇ ｔｈｅ“ｇ”ａｓ ａ ｆｏｒｗａｒｄ ｐｒｉｍｅｒ ａｎｄ“Ｙ”ａｓ ａ ｒｅｖｅｒｓｅ ｐｒｉｍｅｒ．Ｔｈｅ ｎｅｅｄｅｄ ｓｔｒｉｎｇ ｃｏｕｌｄ ｂｅ ｇｅｌ ｐｕ— ｒｉｆｉｅｄ ｓｉｎｃｅ ｉｔｓ ｌｅｎｇｔｈ ｗｏｕｌｄ ｂｅ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｔｈｅ ｒｅｍａｉｎｉｎｇ ｓｅｑｕｅｎｃｅ．Ｔｈｅ ｃｏｒｒｅｓｐ０ｎｄｉｎｇ ｎｅｅｄｅｄ ｓｔｒｉｎｇ“１×ｇ ｍｏｄ Ｐ，１×ｇ ｒｏｏｄ Ｐ，…，ｙ一１ Ｘ ｇ ｒｏｏｄ Ｐ”ｃａｎ ｂｅ ｅｘｔｒａｃｔｅｄ，ｓｅｅ Ｆｉｇ．６（ａ）． Ａｓ ｗｅ ｋｎｏｗ，ｔｈｅ ｓｅｃｕｒｉｔｙ ｏｆ ｔｈｅ Ｄｉｆｆｉｅ—Ｈｅｌｌ— ｍａｎ ｋｅｙ ｅｘｃｈａｎｇｅ ｐｒｏｔｏｃｏｌ ｌｉｅｓ ｉｎ ｔｈｅ ｆａｃｔ ｔｈａｔ， Ｗｈｉｌｅ ｉｔ ｉｓ ｒｅｌａｔｉｖｅｌｙ ｅａｓｙ ｔｏ ｃａｌｃｕｌａｔｅ ｅｘｐｏｎｅｎｔｉａｌｓ （ａ）ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ：Ｆ ｃｏｎｔａｉｎ ｔｈｅ ｓｉｔｅ ｏｆ ａ ｒｅｓｔｒｉｃｔ’ｉｏｎ ｅｎｚｙｍｅ ｍｏｄｕｌｏ ａ ｐｒｉｍｅ。ｉｔ ｉｓ ｖｅｒｙ ｄｉｆｆｉｃｕｌｔ ｔｏ ｃａｌｃｕｌａｔｅ ｄｉｓ— ｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ．Ｈｅｒｅ ｉｓ ａｎ ｅｘａｍｐｌｅ，ｋｅｙ ｅｘ— ｃｈａｎｇｅ ｉｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｕｓｅ ｏｆ ｔｈｅ ｐｒｉｍｅ ｎｕｍｂｅｒ （ｂ）ｔｈｅ ｅｘｔｒａｃｔｅｄ ｒｅｐｏｒｔ ｓｔｒａｎｄ 户一７ ａｎｄ ａ ｐｒｉｍｉｔｉｖｅ ｒｏｏｔ ｏｆ Ｐ，ｉｎ ｔｈｉｓ ｃａｓｅ ｇ一３． Ｆｉｇ．５ Ｅｘｔｒａｃｔｉｎｇ ｔｈｅ ｒｅｐｏｒｔ ｓｔｒａｎｄ Ｔｈｅ ｅｎｔｉｔｉｅｓ Ａ ａｎｄ Ｂ ｓｅｌｅｃｔ ｓｅｃｒｅｔ ｋｅｙｓ ＸＡ ａｎｄ ＸＢ， ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｅａｃｈ ｃｏｍｐｕｔｅｓ ｈｉｓ ｏｒ ｈｅｒ ｐｕｂｌｉｃ ｋｅｙ： １２期 陈智华：基于ＤＮＡ计算自组装模型的Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ算法破译 ２１２１ （ａ）ｔｈｅ ｎｅｅｄｅｄ ｓｔｒａｎｄｓ ｂｙ ＰＣＲ ２０００，６ １０００，５ ７５０，４ ５００，３ ２５０，２ １Ｏ０．１ （ｄｂ，Ｘ） （ｂ）ｒｅａｄ ｏｕｔ Ｘ ｂｙ ｇｅｌ ｅｌｅｃｔｒｏｐｈｏｒｅｓｉｓ Ｆｉｇ．６ Ｒｅａｄ Ｏｕｔ Ｘ ｂｙ ｇｅｌ ｅｌｅｃｔｒｏｐｈｏｒｅｓｉｓ ａｆｔｅｒ ＰＣＲ ＹＡ一５ ａｎｄ ＹＢ一６．Ａｆｔｅｒ ｔｈｅｙ ｅｘｃｈａｎｇｅ ｐｕｂｌｉｃ ｋｅｙｓ，ｅａｃｈ ｏｎｅ ｃａｎ ｃｏｍｐｕｔｅ ｔｈｅ ｃｏｍｍｏｎ ｓｅｃｒｅｔ ｋｅｙ：Ｋ一（ｙＢ） ｍｏｄ Ｐ一（ＹＡ） ｏｒｏｄ Ｐ．Ｉｎ ｆａｃｔ， ｗｅ ｃｏｕｌｄ ｇｅｔ ｔｈｅ Ｐ，ｇ， ａｎｄ ＹＢ ｅａｓｉｌｙ．Ｗｅ ｕｓｅ ｔｈｅ ＤＮＡ ｔｉｌｅ ｓｙｓｔｅｍｓ ａｎｄ ｂｉｏｌｏｇｉｃａｌ ｔｅｃｈｎｏｌｏｇｉｅｓ ｔｏ ｇｅｔ ｔｈｅ ＸＡ ａｎｄ ＸＢ．Ｉｎ ｔｈｉｓ ｃａｓｅ，Ｐ一７，ｇ＝＝＝３ ａｎｄ ＹＡ一５，ｔｈｅ ｐａｒｔ ｏｆ ｒｅｐｏｒｔ ｓｔｒａｎｄ“３—５”ｃａｎ ｂｅ ａｍ— ｐｌｉｆｉｅｄ ｂｙ ＰＣＲ ｍｅｔｈｏｄ ｂｙ ｐｕｔｔｉｎｇ ｔｈｅ“３”ａｓ ａ ｆｏｒ— ｗａｒｄ ｐｒｉｍｅｒ ａｎｄ“５”ａｓ ａ ｒｅｖｅｒｓｅ ｐｒｉｍｅｒ．Ｔｈｅ ｎｅｅ— ｄｅｄ ｓｔｒｉｎｇ ｃｏｕｌｄ ｂｅ ｇｅｌ ｐｕｒｉｆｉｅｄ ｓｉｎｃｅ ｉｔｓ ｌｅｎｇｔｈ ｗｏｕｌｄ ｂｅ ｄｉｆｆｅｒｅｎｔ ｆｒｏｍ ｔｈｅ ｒｅｍａｉｎｉｎｇ ｓｅｑｕｅｎｃｅ。 ｓｅｅ Ｆｉｇ．６（ｂ）．Ｂａｓｅｄ ｏｎ ｔｈｅ ｒｅｌａｔｉｏｎ ｏｆ ｓｅｑｕｅｎｃｅ １ｅｎｇｔｈ ａｎｄ ｚ，ｗｅ ｃａｎ ｒｅａｄ ｏｕｔ ｔｈｅ ＸＡ一５．Ｔｈｅｎ Ｐ一７，ｇ一３ ａｎｄ ＹＢ一６，ｗｅ ｒｅｐｅａｔ ｔｈｅ ｓａｍｅ ｐｒｏ— ｇｒａｍｓ ａｎｄ ｒｅａｄ ｏｕｔ ｔｈｅ ＸＢ一３．Ｓｏ ｗｅ ｃａｎ ｃｏｍｐｕｔｅ ｔｈｅｉｒ ｃｏｍｍｏｎ ｓｅｃｒｅｔ Ｋ一６ ｒｏｏｄ ７—５。ｍｏｄ ７—６． Ｔｈｒｏｕｇｈ ｔｈｅ ｔｉｌｅ ｓｙｓｔｅｍ，ＰＣＲ ａｎｄ ｇｅｌ ｅｌｅｃｔｒｏ— ｐｈｏｒｅｓｉｓ，ｗｅ ｃａｎ ｂｒｅａｋ ｔｈｅ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ａｌｇｏ— ｒｉｔｈｉｎ。 ４ Ｃｏｎｃｌｕｓｉｏｎ ＤＮＡ ｓｅｌｆ ａｓｓｅｍｂｌｙ ｉｓ ｅｘｐｅｃｔｅｄ ｔｏ ｂｅ ｕｓｅｆｕ１ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｅｃｕｒｉｔｙ．Ｏｕｒ ｍｅｔｈｏｄ ｆｏｒ ｂｒｅａｋｉｎｇ Ｄｉｆ－ ｆｉｅ—Ｈｅｌｌｍａｎ ａｌｇｏｒｉｔｈｍ ｅｘｔｅｎｄｓ ｔｈｅ ｔｅｃｈｎｉｑｕｅ ｕｓｅｄ ｂｙ ＬａＢｅａｎ ｅｔ ａ１．Ｅｚ２］ｆｏｒ ｂｉｎａｒｙ ａｄｄｉｔｉｏｎ ａｎｄ ＸＯＲ． Ｔｈｅ ａｄｖａｎｔａｇｅ ｏｆ ｏｕｒ ｍｅｔｈｏｄｓ ｉｓ ｔｈａｔ ｏｎｃｅ ｔｈｅ ｉｎｉ— ｔｉａｌ ｓｔｒａｎｄｓ ａｒｅ ｃｏｎｓｔｒｕｃｔｅｄ．ｅａｃｈ ｐｅｒｍｕｔａｔｉｏｎ ｏｐ— ｅｒａｔｉｏｎ ｉｓ ｐｒｏｃｅｓｓｅｄ ｖｅｒｙ ｆａｓｔ ｔｈｒｏｕｇｈ ｔｈｅ ｓｅｌｆ— ａｓ—＋ ｓｅｍｂｌｙ ａｎｄ ｔｈｅ ｏｕｔｐｕｔ ｃａｎ ｂｅ ｄｉｒｅｃｔｌｙ ｐａｓｓｅｄ ａｓ ｉｎ— ｐｕｔ ｔｏ ａｎｏｔｈｅｒ ｃｏｍｐｕｔａｔｉｏｎ．Ｔｈｅ ｏｎｌｙ ｔｉｍｅ ｃｏｎｓｕ— ｍｉｎｇ ｏｐｅｒａｔｉｏｎ ｉｓ ｔｈｅ ｒｅａｄｉｎｇ ｏｆ ｔｈｅ ｏｕｔｐｕｔ． Ｔｈｅ ｐｅｒｍｕｔａｔｉｏｎ ｏｆ １×ｇ ｍｏｄ Ｐ．１×ｇ２ ｒｏｏｄ Ｐ．…，１×ｇ 一ｒｏｏｄ Ｐ ｃａｎ ｂｅ ａｃｈｉｅｖｅｄ ｂｙ ｔｈｅ ｓｅｌｆ— ａｓｓｅｍｂｌｙ ｓｙｓｔｅｍ．Ｔｈｅ ｔｉｌｅ ｓｙｓｔｅｍｓ ｕｓｅ＠（ ）ｉｎｐｕｔ ｔｉｌｅｓ ａｎｄ ｃｏｍｐｕｔｅ ｉｎ＠（Ｐ）ｓｔｅｐｓ．Ｗｅ ｅｘｔｒａｃｔ ｔｈｅ ｒｅｐｏｒｔ ｓｔｒａｎｄ ｉｎ ｔｈｅ ｆｉｎａｌ ｃｏｎｆｉｇｕｒａｔｉｏｎ，ｔｈｅｎ ｕｓｅ ＰＣＲ ａｎｄ ｇｅｌ ｅｌｅｃｔｒｏｐｈｏｒｅｓｉｓ ｔｏ ｒｅａｄ ｏｕｔ ｔｈｅ ｄｉｓ— ｃｒｅｔｅ ｌｏｇａｒｉｔｈｍｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｗｅ ｃａｎ ｃｏｍｐｕｔｅ ｔｈｅ ｃｏｍｍｏｎ ｓｅｃｒｅｔ ｋｅｙ ｕｓｅｄ ｉｎ Ｄｉｆｆｉｅ—Ｈｅｌｌｍａｎ ｓｃｈｅｍｅ． Ｔｈｅ ｂｏｔｔｌｅｎｅｃｋ ｏｆ ｔｈｅ ｓｅｌｆ—ａｓｓｅｍｂｌｙ ｓｙｓｔｅｍ ｉｓ ｔｈａｔ ｔｈｅ ｔｙｐｅｓ ｏｆ ｂａｓｉｃ ｉｎｐｕｔ ｔｉｌｅｓ ｉｓ ｌｉｎｅａｒ ｃｏｒｒｅｌａ— ｔｉｏｎ ｗｉｔｈ ｔｈｅ ｐｒｉｍｅ ｎｕｍｂｅｒ Ｐ．Ｔｈｅ ｎｅｅｄｅｄ ｉｎｐｕｔ ｔｉｌｅ ｔｙｐｅｓ ｗｉｌｌ ｉｎｃｒｅａｓｅ ｗｉｔｈ ｉｎｃｒｅａｓｉｎｇ Ｐ．Ｗｈｅｎ Ｐ ｉｓ ｌａｒｇｅ ｅｎｏｕｇｈ，ｉｔ ｉｓ ｖｅｒｙ ｄｉｆｆｉｃｕｌｔ ｔｏ ｆｉｎｄ ｅｎｏｕｇｈ ｄｉｓｔｉｎｃｔ ｔｙｐｅｓ ｔｉｌｅ ｔｏ ｃａｒｒｙ ｏｕｔ ｃｏｍｐｕｔａｔｉｏｎ．Ｉｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ｔｉｌｅ ｓｙｓｔｅｍ ｃａｎ ｂｒｅａｋ ｔｈｅ ｂｏｔｔｌｅｎｅｃｋ，ｔｈｅ ｓｙｓｔｅｍ ｗｏｕｌｄ ｂｅ ｍｏｒｅ ｍｅａｎｉｎｇｆｕ１． Ｔｈｅ ｎａｎｏｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｂｉｏｌｏｇｉｃａｌ ｔｅｃｈｎｏｌｏｇｙ ｈｏｌｄ ｔｒｅｍｅｎｄｏｕｓ ｐｒｏｍｉｓｅ．Ｂｕｔ ｍａｎｙ ｔｅｃｈｎｉｃａｌ ｈｕｒ— ｄｌｅｓ ｗｉｌｌ ｈａｖｅ ｔｏ ｂｅ ｏｖｅｒｃｏｍｅ ｂｅｆｏｒｅ ｃｏｍｐｌｅｘ ａｌｇｏ— ｒｉｔｈｍｉｃ ｓｅｌｆ—ａｓｓｅｍｂｌｙ ｃａｎ ｂｅ ｄｅｖｅｌｏｐｅｄ ｉｎｔｏ ａ ｐｒａｃ－ ｔｉｃａｌ ｃｏｍｍｅｒｃｉａｌ ｔｅｃｈｎｏｌｏｇｙ．Ｉｆ ｔｈｅ ｍｏｌｅｃｕｌａｒ ｗｏｒｄ ｃａｎ ｂｅ ｃｏｎｔｒｏｌｌｅｄ ａｔ ｗｉｌ１．ｉｔ ｍａｙ ｂｅ ｐｏｓｓｉｂｌｅ ｔｏ ａｃｈｉｅｖｅ ｖａｓｔｌｙ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｓｔｏｒａｇｅ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｅｃｕｒｉｔｙ． Ｒｅｆｅｒｅｎｃｅｓ Ａｄｌｅｍａｎ Ｌ Ｍ．Ｍｏｌｅｃｕｌａｒ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｓｏｌｕｔｉｏｎｓ ｔｏ ｃｏｍｂｉ— ｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ．Ｓｃｉｅｎｃｅ，１９９４，２６６：１０２１ １０２４ ［２］ Ａｄｌｅｍａｎ Ｌ Ｍ．Ｃｏｍｐｕｔｉｎｇ ｗｉｔｈ ＤＮＡ．Ｓｃｉｅｎｔｉｆｉｃ Ａｍｅｒｉｃａｎ． １９９８，２７９（２）：５４－６１ ［３３ Ｌｉｕ Ｌ Ｑ．１ ｉｕ Ｇ Ｗ，Ｘｕ Ｊ．Ｌｉｕ Ｙ Ｃ．‘Ｓｏｌｉｄ ｐｈａｓｅ ｂａｓｅｄ ＤＮＡ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｃｏｌｏｒｉｎｇ ｐｒｏｂｌｅｍ．Ｐｒｏｇｒｅｓｓ ｉｎ Ｎａｔｕｒａｌ Ｓｃｉ— ｅｎｃｅ，２００４，１４（５）：１０４—１０７ Ｐａｎ Ｌ Ｑ．Ｃａｒｌｏｓ Ｍ Ｖ．Ｓｏｌｖｉｎｇ ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ ０－１ ｋｎａｐ— ｓａｃｋ ｐｒｏｂｌｅｍ ｂｙ Ｐ ｓｙｓｔｅｍｓ ｗｉｔｈ ｉｎｐｕｔ ａｎｄ ａｃｔｉｖｅ ｍｅｍｂｒａｎｅｓ． Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，２００５，６５ （１２）：１５７８ １５８４ Ｂｏｎｅｈ Ｄ，Ｄｕｎｗｏｒｔｈ Ｃ，Ｌｉｐｔｏｎ Ｒ Ｊ．Ｂｒｅａｋｉｎｇ ＤＥＳ ｕｓｉｎｇ ａ ｍｏｌｅｃｕｌａｒ ｃｏｍｐｕｔｅｒ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｌ ｓｔ ＤＩＭＡＣＳ Ｗｏｒｋ— ｓｈｏｐ ｏｎ ＤＮＡ Ｂａｓｅｄ Ｃｏｍｐｕｔｅｒｓ．１９９５ １ ３７—６５ Ｅ６］ Ａｄｌｅｍａｎ Ｌ Ｍ，Ｒｏｔｈｅｍｕｎｄ Ｐ Ｗ Ｋ，Ｒｏｗｅｉｓ Ｓ，Ｗｉｎｆｒｅｅ Ｅ． Ｏｎ ａｐｐｌｙｉｎｇ ｍｏｌｅｃｕｌａｒ ｃｏｍｐｕｔａｔｉｏｎ ｔＯ ｔｈｅ ｄａｔａ ｅｎｃｒｙｐｔｉｏｎ ｓｔａｎｄａｒｄ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２ｎｄ Ａｎｎｕａｌ Ｍｅｅｔｉｎｇ ｏｎ ＤＮＡ Ｃｏｍｐｕｔｅｒｓ．１９９６：１Ｏ一１２ ［７］ Ｃｈａｎｇ Ｗ Ｌ．Ｇｕｏ Ｍ Ｙ，Ｍｉｃｈａｅｌ Ｓ Ｈ．Ｆａｓｔ ｐａｒａｌｌｅｌ ｍｏｌｅｃｕｌａｒ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ＤＮＡ—ｂａｓｅｄ ｃｏｍｐｕｔａｔｉｏｎ：Ｆａｃｔｏｒｉｎｇ ｉｎｔｅｇｅｒｓ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎａｎｏｂｉｏｓｃｉｅｎｃｅ，２００５，４（２）：１４９－１６３ Ｇｅｈａｎｉ Ａ，ＬａＢｅａｎ Ｔ Ｈ，Ｒｅｉｆ Ｊ Ｈ．ＤＮＡ—ｂａｓｅｄ ｃｒｙｐｔｏｇｒａ— ｐｈｙ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ ＤＩＭＡＣＳ Ｗｏｒｋｓｈｏｐ ｏｎ ＤＮＡ— Ｂａｓｅｄ Ｃｏｍｐｕｔｅｒｓ，ＭＩＴ．１９９９：２３３ ［９］ Ｌｅｉｅｒ Ａ，Ｒｉｃｈｔｅｒ Ｃ，Ｂａｎｚｈａｆ Ｗ，Ｒａｕｈｅ Ｈ．Ｃｒｙｐｔｏｇｒａｐｈｙ ｗｉｔｈ ＤＮＡ ｂｉｎａｒｙ ｓｔｒａｎｄｓ．Ｂｉｏｓｙｓｔｅｍｓ，２０００，５７：１３—２２ ２１２２ 计 算 机 学 报 ２００８钲 ［１Ｏ］ Ｃｈｅｎ Ｊ．Ａ ＤＮＡ—ｂａｓｅｄ ｂｉｏｍｏｌｅｃｕｌａｒ ｃｒｙｐｔｏｇｒａｐｈｙ ｄｅｓｉｇｎ／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００３ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ：ＩＳＣＡＳ ２００３，２００３：８２２ ［１１］ Ｃｌｅｌｌａｎｄ Ｃ Ｔ，Ｒｉｓｃａ Ｖ，Ｂａｎｃｒｏｆｔ Ｃ．Ｈｉｄｉｎｇ ｍｅｓｓａｇｅｓ ｉｎ ＤＮＡ ｍｉｃｒｏｄｏｔｓ．Ｎａｔｕｒｅ，１９９９，３９９：５３３—５３４ ［１２３ Ｗａｎｇ Ｈ．Ｐｒｏｖｉｎｇ ｔｈｅｏｒｅｍｓ ｂｙ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ Ｉ．Ｂｅｌｌ Ｓｙｓｔｅｍ Ｔｅｃｈｎｉｃａ１ Ｊｏｕｒｎａｌ。１９６１，４Ｏ：卜４２ ［１３］ Ｍａｏ Ｃ，ＬａＢｅａｎ Ｔ Ｈ，Ｒｅｉｆ ｊ Ｈ，Ｓｅｅｍａｎ Ｎ Ｃ．Ｌｏｇｉｃａｌ ｃｏｍ— ｐｕｔａｔｉｏｎ ｕｓｉｎｇ ａｌｇｏｒｉｔｈｍｉｃ ｓｅｌｆ－ａｓｓｅｍｂｌｙ ｏｆ ＤＮＡ ｔｒｉｐｌｅ——ｃｒｏｓｓ—＿ ｏｖｅｒ ｍｏｌｅｃｕｌｅｓ．Ｎａｔｕｒｅ，２０００，４０７：４９３－４９６ ［１４］ Ｂａｒｉｓｈ Ｒ，Ｒｏｔｈｅｍｕｎｄ Ｐ，Ｗｉｎｆｒｅｅ Ｅ．ＴＷＯ ｃｏｍｐｕｔａｔｉｏｎａ１ ｐｒｉｍｉｔｉｖｅｓ ｆｏｒ ａｌｇｏｒｉｔｈｍｉｃ ｓｅｌｆ—ａｓｓｅｍｂｌｙ：Ｃｏｐｙｉｎｇ ａｎｄ ｃｏｕｎｔ— ｉｎｇ．Ｎａｎｏ Ｌｅｔｔｅｒｓ，２００５，５（１２）：２５８６—２５９２ ［１５］ Ｃｏｏｋ Ｍ，Ｒｏｔｈｅｍｕｎｄ Ｐ，Ｗｉｎｆｒｅｅ Ｅ．Ｓｅｌｆ－ａｓｓｅｍｂｌｅｄ ｃｉｒｃｕｉｔ ｐａｔｔｅｒｎｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｅｅｔｉｎｇ ｏｎ ＤＮＡ Ｃｏｍｐｕｔｅｒ．Ｍｉｌａｎ，Ｉｔａｌｙ，２００４：９１－１０７ ［ｉ６３ Ｒｏｔｈｅｍｕｎｄ Ｐ，Ｐａｐａｄａｋｉｓ Ｎ，Ｗｉｎｆｒｅｅ Ｅ．Ａｌｇｏｒｉｔｈｍｉｃ ｓｅｌｆ—ａｓ— ｓｅｍｂｌｙ ｏｆ ＤＮＡ ｓｉｅｒｐｉｎｓｋｉ ｔｒｉａｎｇｌｅｓ．ＰＬｏＳ Ｂｉｏｌｏｇｙ，２００４，２ （１２）：２０４１—２０５３ ＣＨＥＮ Ｚｈｉ—Ｈｕａ， ｂｏｒｎ ｉｎ １９７６， Ｐｈ．Ｄ．ｃａｎｄｉｄａｔｅ。ｌｅｃｔｕｒｅｒ．Ｈｅｒ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ＤＮＡ—ｂａｓｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｅｃｕｒｉｔｙ ａｎｄ ｉｎｔｅｌｌｉｇｅｎｔ ｃｏｎｔｒｏｌ ａｌｇｏ— ｒｉｔｈｍ． ［１７］ Ｂｒｕｎ Ｙ．Ａｒｉｔｈｍｅｔｉｃ ｃｏｍｐｕｔａｔｉｏｎ ｉｎ ｔｈｅ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅｌ： Ａｄｄｉｔｉｏｎ ａｎｄ ｍｕｌｔｉｐｌｉｃａｔｉｏｎ．Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００６，３７８（１）：１７～３１ ［１８］ Ｂｒｕｎ Ｙ．Ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ｆａｃｔｏｒｉｎｇ ｉｎ ｔｈｅ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅ１．Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００８， ３９５（１）：３—２３ ［１９］ Ｂｒｕｎ Ｙ．Ｓｏｌｖｉｎｇ ＮＰ—ｃｏｍｐｌｅｔｅ ｐｒｏｂｌｅｍｓ ｉｎ ｔｈｅ ｔｉｌｅ ａｓｓｅｍｂｌｙ ｍｏｄｅ１．Ｔｈｅｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００８，３９５（１）：３卜４６ ［２ｏ３ Ｒｏｔｈｅｍｕｎｄ Ｐ，Ｗｉｎｆｒｅｅ Ｅ．Ｔｈｅ ｐｒｏｇｒａｍ—ｓｉｚｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｓｅｌｆ－ａｓｓｅｍｂｌｅｄ ｓｑｕａｒｅｓ／／Ｐｒｏｃｅｅ ｄｉｎｇｓ ｏｆ ｔｈｅ ３２ｎｄ Ａｎｎｕａｌ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ（ＳＴＯＣ）．Ｐｏｒｔ— ｌａｎｄ，２００ｌ：４５９—４６８ ［２１］ Ｒｏｚｅｎｂｅｒｇ Ｇ，Ｓｐａｉｎｋ Ｈ．ＤＮＡ ｃｏｍｐｕｔｉｎｇ ｂｙ ｂｌｏｃｋｉｎｇ．Ｔｈｅ— ｏｒｅｔｉｃａｌ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００３，２９２（３）：６５３－６６５ ［２２３ ＬａＢｅａｎ Ｔ Ｈ．Ｗｉｎｆｒｅｅ Ｅ，Ｒｅｉｆ Ｊ Ｈ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｐｒｏｇｒｅｓｓ ｉｎ ｃｏｍｐｕｔａｔｉｏｎ ｂｙ ｓｅｌｆ—ａｓｓｅｍｂｌｙ ｏｆ ＤＮＡ ｔ｜ｌｊｎｇｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｅｅｔｉｎｇ Ｏｉｌ ＤＮＡ Ｂａｓｅｄ Ｃｏｍｐｕｔｅｒｓ （ＤＮＡ５）．ＭＩＴ，Ｃａｍｂｒｉｄｇｅ ＭＡ，１９９９：１２３—１４０
