第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/i.i8sn.1673-4785.2011.02.015 用于DNA编码的部分字 李珍，王淑栋，李二艳 (山东科技大学信息科学与工程学院，山东青岛266510) 摘要：寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要 的结构，尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的 方法来解决DNA编码问题，利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和Watson-Cick Hamming距离的3个命题，通过部分字对DNA编码进行了优化，解决了DNA编码中的部分疑难问题. 关键词：DNA编码；部分字；洞；Hamming距离；Watson-Crick Hamming距离 中图分类号：TP18文献标识码：A文章编号：16734785(2011)02018504 Partial words for DNA encoding LI Zhen,WANG Shudong,LI Eryan College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao 266510,China) Abstract:Finding a good DNA code is a very basic problem in DNA computation.A solution must be provided which ensures that the strands involved do not exhibit any undesired behavior,and especially that they should not form a false positive.The traditional solution requires the Hamming distance between the words to be big enough. The author proposed the idea of considering only partial words for the solution of the DNA encoding problem.To some degree they already include the Hamming distance in the definition of compatibility.Thus,they can be used to simultaneously guarantee a desired distance and other properties.In this paper,the definition of Hole and some properties of partial words were applied to achieve three propositions concerning Hole,Hamming distance,and Watson-Crick Hamming distance.The DNA code set was optimized by using the partial words.Thus some difficult problems were resolved in DNA encoding. Keywords:DNA encoding;partial words;hole;Hamming distance;Watson-Crick Hamming distance 自从Adleman首次利用分子生物技术解决了法来解决DNA编码问题具有重要的意义.本文利用 一个具有7个顶点的有向Hamilton路问题以来，部分字的洞的定义及其性质得到了关于部分字的 DNA计算取得了突飞猛进的发展2s].DNA编码作洞、Hamming距离和Watson-Crick Hamming距离的 为DNA计算的基本问题之一也取得了很大的进3个命题，通过对部分字的分析对DNA编码进行了 展[sa].针对DNA编码中出现的错误杂交，Berstel 优化.随着部分字越来越受到人们的关注，它们可能 和Boasson'1于1998年提出了部分字的概念.2002 为DNA编码提供一种更为有效的工具 年，Blanchet-Sadris)对部分字的性质做出了详细论 证.2003年，Blanchet-Sadri67]又对部分字的性质 1基本定义及性质 作了更深入的研究与探讨.部分字的一些性质「8]包 定义14)字母表Σ={A,T,C,G上的部分字 含了DNA编码的一些限制条件，例如，部分字的相 w是由部分函数f:{0,1,…,n-1}→Σ随机排列构 容性包含了Hamming距离，因此考虑用部分字的方 成的DNA序列.w(p)(=f(),i∈{0,1，…，n-1}) 收稿日期：20100524. (p∈{0,1，…，n-1})有定义的位置构成的集合称 基金项目：国家自然科学基金资助项目(60503002)：中国博士后科学 基金资助项目(20060400344). 为w的定义域，记为D(0),H(0)={0,1,…, 通信作者：李珍.E-mail:topwayD202@163.com n-1}/D(0)称为0的洞集合