[1]李珍,王淑栋,李二艳.用于DNA编码的部分字[J].智能系统学报,2011,6(02):185-188.
 LI Zhen,WANG Shudong,LI Eryan.Partial words for DNA encoding[J].CAAI Transactions on Intelligent Systems,2011,6(02):185-188.
点击复制

用于DNA编码的部分字(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第6卷
期数:
2011年02期
页码:
185-188
栏目:
出版日期:
2011-04-25

文章信息/Info

Title:
Partial words for DNA encoding
文章编号:
1673-4785(2011)02-0185-04
作者:
李珍王淑栋李二艳
山东科技大学 信息科学与工程学院,山东 青岛 266510
Author(s):
LI Zhen WANG Shudong LI Eryan
College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510, China
关键词:
DNA编码部分字Hamming距离WatsonCrick Hamming距离
Keywords:
DNA encoding partial words hole Hamming distance WatsonCrick Hamming distance
分类号:
TP18
文献标志码:
A
摘要:
寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要的结构,尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题,利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和WatsonCrick 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 WatsonCrick 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): 10211024. 
[2] LIPTON R J. NA solution of hard computational problems[J]. Science, 1995, 268: 542545. 
[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: 3765. 
[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: 230237. 
 [5] OUYANG Qi, KAPLAN P D, LIU Shumao. DNA solution of the maximal clique problem[J]. Science, 1997, 278: 446449. 
 [6] BAUM E B. DNA sequences useful for computation[C]//Proc Second Annual Meeting DNABased Computers.[S.l.], 1996: 223227. 
 [7] GARZON M,DEATON R,NINO L F. A new metric for DNA computing[C]//Proceedings of the 2nd Annual Genetic Programming Conference GP97. Morgan Kaufmann, USA, 1997: 472487. 
[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: 230273. 
 [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): 47484757. 
[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: 163167. 
[12] BRAICH R S, JOHNSON C, ROTHEMUND P W K, ADLEMAN L M. Solution of a satisfy problem on a gelbased DNA computer[C]//The 6th International Workshop on DNA Based Computing. London, UK: Springerverlag, 2001: 2742. 
 [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: 229241. 
[14] BERSTEL J, BOASSON L. Partial words and a theorem of fine and Wilf[J]. Theoretical Computer Science, 1999, 218: 135141. 
[15] BLANCHETSADRI F, HEGSTROM A. Partial words and a theorem of fine and Wilf[J]. Theoretical Computer Science, 2002, 270: 401419. 
[16] BLANCHETSADRI F. Primitive partial words[C]//The 8th International Conference on Computational Intelligence and Multimedia Applications, [S.l.], 2003, 218: 135141. 
[17] LEUPOLD P. Partial words for DNA coding[C]// The 8th International Conference on Computational Intelligence and Multimedia Applications.[S.l.], 2005, 221: 224234. 
[19] 王淑栋,宋弢. DNA Golay码的设计与分析[J]. 电子学报, 2009,37(7): 135141. WANG Shudong, SONG Tao. The design and analysis of DNA Golay codes[J].Acta Electronica Sinica, 2009, 37(7): 135141. 
[20] 陈鲁生, 沈世镒. 编码理论基础[M]. 北京:高等教育出版社, 2005: 168221.

备注/Memo

备注/Memo:
收稿日期:2010-05-24.
基金项目: 国家自然科学基金资助项目(60503002);中国博士后科学基金资助项目(20060400344). 
通信作者: 李珍.
E-mail:topwayD202@163.com.
作者简介:
李珍,女,硕士.主要研究方向为DNA计算.
王淑栋,女,教授,博士.研究领域为DNA计算,复杂网络等.
李二艳,女,硕士生.研究领域为DNA计算.
更新日期/Last Update: 2011-05-19