[1]李珍,王淑栋,李二艳.用于DNA编码的部分字[J].智能系统学报,2011,6(2):185-188.
LI Zhen,WANG Shudong,LI Eryan.Partial words for DNA encoding[J].CAAI Transactions on Intelligent Systems,2011,6(2):185-188.
点击复制
LI Zhen,WANG Shudong,LI Eryan.Partial words for DNA encoding[J].CAAI Transactions on Intelligent Systems,2011,6(2):185-188.
用于DNA编码的部分字
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
6
期数:
2011年第2期
页码:
185-188
栏目:
学术论文—人工智能基础
出版日期:
2011-04-25
- Title:
- Partial words for DNA encoding
- 文章编号:
- 1673-4785(2011)02-0185-04
- 关键词:
- DNA编码; 部分字; 洞; Hamming距离; WatsonCrick Hamming距离
- 分类号:
- TP18
- 文献标志码:
- A
- 摘要:
- 寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要的结构，尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题，利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和WatsonCrick Hamming距离的3个命题, 通过部分字对DNA编码进行了优化,解决了DNA编码中的部分疑难问题.
- 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 WatsonCrick Hamming distance. The DNA code set was optimized by using the partial words. Thus some difficult problems were resolved in DNA encoding.
- 参考文献/References:
-
［1］ ADLEMAN A L. Molecular computation of solution to combinatorial problems［J］. Science, 1994, 266 (11): 10211024.
［2］ LIPTON R J. NA solution of hard computational problems［J］. Science, 1995, 268： 542545.
［3］ BONEH D, DUNWORTH C, LIPTON R. Breaking DES using a molecular computer［C］//Proceedings of the 1st DIMACS Workshop on DNA Based Computers. Providence： American Mathematics Society, 1995： 3765.
［4］ GARZON M, DEATON R， NEATHERY P. On the encoding problem for DNA computing［C］//Proceedings of the 3rd DIMACS Workshop on DNA Based Computers. ［S.l.］， 1997: 230237.
?［5］ OUYANG Qi, KAPLAN P D， LIU Shumao. DNA solution of the maximal clique problem［J］. Science, 1997, 278: 446449.
?［6］ BAUM E B. DNA sequences useful for computation［C］//Proc Second Annual Meeting DNABased Computers.［S.l.］, 1996： 223227.
?［7］ GARZON M,DEATON R,NINO L F. A new metric for DNA computing［C］//Proceedings of the 2nd Annual Genetic Programming Conference GP97. Morgan Kaufmann, USA, 1997: 472487.
［8］ GARZOR M, DEATON R，NINO L F, STEVENS S E, WITTER M. Genome encoding for DNA computing［C］//The Third DIMACS Workshop on DNA Based Computing. Pennsylvania, America， 1997： 230273.
?［9］ FELDKAMP, STEVENTS S E, NINO L F. A DNA sequence complier［C］//Proceedings of 6th DIMACS Workshop on DNA Based Computing. Leidon, The Netherlands， 2000: 253.
［10］ FRUTOS A G, BONEH D, DUNWORTH C. Demonstration of a word design strategy for DNA computing on surface［J］. Nucleic Acids Research, 1997, 25(23): 47484757.
［11］ ARITA M, JOHNSON C， ROTHEMUND P W I. The power of sequence design in DNA computing［C］//The 4th International Conference on Computational Intelligence and Multimedia Applications. ［S.l.］， 2001: 163167.
［12］ BRAICH R S, JOHNSON C, ROTHEMUND P W K, ADLEMAN L M. Solution of a satisfy problem on a gelbased DNA computer［C］//The 6th International Workshop on DNA Based Computing. London, UK: Springerverlag, 2001： 2742.
?［13］ DAN C, TULPAN H H, CONDON H. Anne. Condon. Stochastic local search algorithms for DNA word design［C］//The 8th International Conference on Computational Intelligence and Multimedia Applications.［S.l.］, 2003: 229241.
［14］ BERSTEL J， BOASSON L. Partial words and a theorem of fine and Wilf［J］. Theoretical Computer Science, 1999, 218: 135141.
［15］ BLANCHETSADRI F, HEGSTROM A. Partial words and a theorem of fine and Wilf［J］. Theoretical Computer Science, 2002, 270: 401419.
［16］ BLANCHETSADRI F. Primitive partial words［C］//The 8th International Conference on Computational Intelligence and Multimedia Applications, ［S.l.］， 2003, 218: 135141.
［17］ LEUPOLD P. Partial words for DNA coding［C］// The 8th International Conference on Computational Intelligence and Multimedia Applications.［S.l.］， 2005, 221: 224234.
［19］ 王淑栋，宋弢. DNA Golay码的设计与分析［J］. 电子学报, 2009,37(7): 135141. WANG Shudong, SONG Tao. The design and analysis of DNA Golay codes［J］.Acta Electronica Sinica, 2009, 37(7): 135141.
［20］ 陈鲁生, 沈世镒. 编码理论基础［M］. 北京：高等教育出版社, 2005: 168221.
备注/Memo
收稿日期：2010-05-24.
基金项目： 国家自然科学基金资助项目（60503002）；中国博士后科学基金资助项目（20060400344）.
通信作者： 李珍.
E-mail:topwayD202@163.com.
作者简介：
李珍，女，硕士.主要研究方向为DNA计算.
王淑栋，女，教授，博士.研究领域为DNA计算，复杂网络等.
李二艳，女，硕士生.研究领域为DNA计算.
更新日期/Last Update:
2011-05-19