Ϣ
Information and Control
1999ꡡ284ڡVol.28No.41999



DNA о״չ
졡

ժҪDNAĿǵĹ ȤڼҪDNA֮̽DNA㼰ģͣŴ㷨ģ ơ硢ϵͳ㼼мɣָ DNA ŵ㼰Ŀǰ ⣮Ƕǵǰչ
ؼʣDNA㣬㣬Ŵ㷨ģƣ磬ϵ ͳ
ͼţTP11ױʶ룺A
THE STUDY OF DNA COMPUTING: CURRENT SITUATION
AND FUTURE DIRECTIONS
REN LihongDING YongshengSHAO Shihuang
(The Department of Automation, China Textile University, Shanghai 200051)
Abstract:Recently, the possibility of using DNA as a computi ng tool arouses wide interests of many researchers. In this paper, after a brief introduction to the mechanism of DNA, we first explore DNA computing and its m odels. Then we integrate DNA computing with some soft computing technologies, s uch as genetic algorithms, fuzzy control, neural networks and chaotic systems. F urthermore, we pointe out the advantages and current existing problems of DNA c omputing. Finally, we for ecast the further work of DNA computing.
Key words:DNA computing, soft computing, genetic algorithm, fuzzy control, neural networks, chaotic systems


1
ǺᣨDNAЯŴϢԴWatsonCrick1953 귢DNA ֮ǷֺͷչDNAķ＼Уøгճ ۺӦDNAȣ﹤ҵУѡˡ궨DNA ܵ˵ЩչʹʹDNAΪ޸ĵĴý塪һڴ棬 ʹʹЩڴϽвʵ㷨
DNA1994걻L. Adleman״ʵʾڼĿԣڡScience ־ϷͻԵ[1]DNAͼHamilt onian߽ڵ·ʵ飮漣˲DNAضĿļĿԣ ӱԲ㷨ҲٶȣڲΪֹûΪӲ ҵʵ֣ҿýǱڵĲԣƪ²ѧ ѧҵȤĿǰо漰෽棺DNAģͺ㷨[2~13]Ҳѧ߿ʼDNAŴ㷨硢ģϵͳͻ ϵͳ㷽[1423]. L. Adleman˼ սDNAоȴŸѧƵĺоѧѧ ѧѧ͹̵ȣǳ֮ΪDNA㡱
ȼҪDNAȻ̽ĿǰDNAоչ мɣָDNAŵ㼰ʵʵִڵ⣮Ƕǵǰչ
2DNAԭѧ
2.1DNA
DNAҪĻʣЯŴϢDNAĻԪǺᣮڻѧṹĲͬỮΪ(bases) (A) (G) (C)(T)
DNAĺɣĺü֮һγһ˫ɵṹһеļһеļлATԣCGԣÿȾɫһ˫DNAŴϢATCG ںе˳֣еĶԹ˷ḻŴϢ
2.2ŴϢ̼
ϸŴϢҪ֣ơת¼ͷ룮ͨDNAĸƶŴϢŴϢϸ˴ϸʣǰDNAת¼mRNAmRNAŴϢ һضаɵĵʣtRNAã뵽 ĺλã
򽻲DNAŴϢḶ́DNAͨ滥ཻϵĺᣮDNAеı仯ıǻдеı仯תtrans ition죺ʡण߻transversion죺ʱʻתƣframeshift죺һԶʧ룬ϣ
2.3DNAѧ
DNAԭѧǳƣDNAɿĸͬA GCTɵĴѧϾӼб롰0͡1һɱʾ ĸļϡ={A,G,C,T}ϢDNAΪϢøɿģDNA ϼ򵥵ļ㣮 ͬøڲͬӣ磬ںøendonucleases ΪӣDNAøligaseΪӣDNA ۺøpolymeras esΪӣøexonucleaseΪɾӵ[24] 
3DNAоչ
3.1DNA㼰ģ
DNAо漰෽棬DNAͨԡʱոԡЧԼݴģ ѱ飮
3.1.1DNAͨü
L. AdlemanָǷһͨDNAܵ[1] һЩоѧ߽⣮ͨ಻ͬķǱDNA ͨõ[3, 25, 26]DNAĻõĵӼһб̣Щ֤ҪǱDNAģһͨü ģͣ磬ģһͨõͼԪԶһDNAɿһͼ ݵĽ룬ݻ޿ƹͨøӦĿ͹ۿܿдŴBeave νͲDNAӵͼ[27]SmithScheweitzerDNAӺͱ׼ʵҼڽһȷͼ[28]Winfre eһֻװ䵥ɺĿռͼ[12]⣬Ҳ ģͼ[29]BaumʾʹDNAͷѧܴﵽ1020ֵ[30]RooºWagnerûʱ Liptonģܴκμ[11] Щ֤ʾ˴DNA ܽṹ֤һЩʵʽǶʵļ裬޲ ǲֱڹеDNADNAӦеĲҲûкܺõر 
3.1.2DNAģͼ㷨
ʵʼ⣬Ź滮ͼ·Ͳ߼ȣԷ Hamiltonian·ʽ
L. AdlemanĵһDNAʵ֮R. LiptonŽĽƹ㵽 NP⣬˼ٶȣһЩļµõһȷԵĲмģ ͣģͣԹӦȡϲɾͷŴȷӲ[31] ʾDNAʵνѧе⣨SATSATһ NPȫ㷨Ҫָʱ䣩֤NPʹģö ʽʱɣL. Adleman˹Ӽʵ⣬R. Lipton ĴȡϲɾͷŴԹܲģ͵ĻϣƵ Ľģ[32]RooºWagnerDNAϵͳ̽˸ Liptonģ͵ı[11]һЩѧߵƴ(splicing)ϵͳѧ ģ[25, 3338]ǻƴӲĲΪDNAʽģ [39, 40]ƴϵͳͼͬͨü[25, 35]һ ϷӲڴstickerģҲѱо[41, 42]
ԹϵͳΪDNAӵϵͳ[43, 44]ƴӡг ԹϵͳͨüԹϵͳĸһģУĳض ԹӦùĿܵƣ
оѧ߲о˻DNAĸDNA㷨߼ͽ͸ [12, 17, 22, 30, 36, 43, 45, 46], ҲӼģͶӦķģ ͵DNA㷨DNA[47]Ӿ[48]ӷֽⷨ[27]ȣDNAĲ·Ҳѱо[31, 49]Liu[50]ﻯѧķЧģһЩ·ķӼģͣ
3.2DNAļ
вõϢģʽѱϵͳ硢Ŵ㷨 㷽Ҫģ߼ۡŴ㷨ϵͳ һѧϰۣڽDNAܼмɣҪ硢 Ŵ㷨ģͻϵͳļɣ
3.2.1DNAŴ㷨ļ
Ŵ㷨GAģӦͽƺõĻͱԽ ڳGAʵ⣬ǴӵġĺͶʱ ҼٶһЩѧ˻DNAĸĽGA磬˫ DNA GAڴٽDNAƵķǶԻ[15]DNAġ ϵͳڸֽϵͳϸضģ[18]ϸضĹУÿ ϸͬDNAӲģͼʾϸض֯ԣ ⣬˻ѧDNA뷽GA[21, 22]ַDNA ȾɫеظԺͻصԣʹͱףѧDN Aķչʵ֪ʶ DNAת¼DNAøҲ DNA뷽ʵ֣ѧ߽DNA뷽αϸGA(PBGA[2 3]ͬʱΪ˱DNAУں֮仯ѧӦһЩ DNAкõDNA㷨[14]
3.2.2DNAģϵͳļ
ģϵͳѻóɹӦãڸӵĶģϵͳĿǰȱ ЧƷȻGAڻȡģƹ򣬵ʱʤθϵͳģϵͳŻһЩ˻DNAGAڶģϵͳŻ[21, 22]ģϵͳѡӳ亯ĵӶԶȡģƹ򣮲ңøҲDNA ˶ƵогʾַĿԣ
3.2.3DNAļ
֯ɺ͹DNAŴϢãDNAŴϢ ĽģŻ
һֲDNAĿܱڽ磨NNģ[19] ģóCODE-4ܸܵõԤֿDNA еtopoisomeraseԣҸСǺߵ1/4ģ͵Ĳ Ŀ˽75
⣬FarhatHernandez̽˲DNAĸʱΪ[16] ⲿԪӻ໥õԪɣ໥õԪɷѧŴϢ룬DNAеĸ ģ⣮ֽѧDNAŴϢнϵоڴ Ӽѧϰķչ
3.2.4DNAļ
һֻȡӦDNA㷨ķϵͳʱϵͳɿɰ ϢһԹܣDNAܣû綯̬ԵķḻЧ ʹƱУõĽ[17]
⣬ִDNA ŴI Chingϱڼ㽨ģ[20]ÿģ; ʾģʽ¿ѧԭ
4DNAŵ㼰Ŀǰڵ
4.1DNAŵ
ȣDNAвɹˮƽĲԣĿǰľͻÿִ1012 DNAҪصľ޴дL. Adlemanĳʼʵ ͨʵƣDNAĲвĿɴ1014оΪõǰ 1015  1020ĲвǿԴﵽ[1, 27]ȻDN AÿʵȷǳڵǰҪľͻǿļ սDNAӦľ޴Բ
ΣDNAкܸߵЧʺʹӼЧʷǳͣ ˷ǲͻִ109Ҫ1ʵDN A øڽвģкܸߵЧʣ1ִ210 9DNAǳߵϢܶȣ1 λ/nm3ǰ¼ ϢܶȽΪ1λ/1212nm3[1]
⣬ԿʵʵDNAܴٽѧﻯѧøĲ͸ɿ 
4.2Ŀǰڵ
DNAоȡһЩչDNA㻹ʵս ڵǰDNAУDNAļ״̬ڲлоƬ״̬Ӳмõ㷨ͨڲмԪ֮ͨţĿǰDNA оУûжλDNA֮ͨŵĽ飮ڳ沢меļĿǰDNA㣮
ʵһDNAϰҪ棺
1ϣģϵͳ͸ʱԼ棬DNAڴлʧDNA磬ʾUѭ֮İᲢ⣬DNAѧ＼PCRʵ֣ɿֻ95оѧʶЩ⣬༤ĵĲʩ[2, 10, 49, 51]磬ϸʹDNAõعвŵķӦظԪʵӿɿԡ۷ӣRNADNAϳɵıΪϢ壮
2߼ϣӦ㷺ĶԺЧ[1, 3, 24, 26]ȻD NA֤ͨüDNAʵӦвӼѷǸ߶ȲDNAʵ֣еĴйӦɵӼ[50]
5չ
DNAմ𲽽׶ΣԳǳǱѧҽѧǱ ӦãܲԵķӣøҩзǳҪDNA Ĵ۷ǳͣЧʼߣʹȻϸͬľ޴ԣDNA һǳӱ뷨ڵõʵӦ֮ǰҪDNA ⼰չУ
1DNAʵУѡʵʲĿĲٶȡвĿɿԡϢȶԸ弰һʵĿ
2δļӦDNAϵļּУÿԼʺϵ񣬲DNA㣬еĴйɹоƬɣͬʱӦ һָ߼ӱԣ
3һļɣڳGAϽ¸ĽaĽ01ƱĽDNAATCG룻bĽɵ㽻淢չ 㽻桢׼棬ӷתĽԵȣcģDNA޲ϵͳ ܣdDNAĵݽGAͬʱоDNAѧϰ ģϵͳɺŻƣ
֮DNAоʵʵֵȴǽһоϵͳ㷽ϵ;õ̽һѧսѧĽ
עͣĿȻѧ
߼飺죬Ů32꣬ʿоΪ㡢ܿơϵͳƵ оӦù
У32꣬ʿʦоΪΪģơܿơϵͳƵо빤ҵҽѧӦù
ͣУ61꣬ڣʿʦΪй֯ѧУڴģơܿơϵͳơCADƵĽѧоӦù
ߵλй֯ѧԶϵϺ200051
ο
1 Adleman L M. Molecular Computation of Solutions to Combinatorial Problems, Science, 1994, 266(5187): 10211023
2 Bach E et al. DNA Models and Algorithms for NP-complete Problems, Proce edings Eleventh Annual IEEE Conference on Computational Complexity, Philadelphia , PA, USA, 24-27 May 1996: 290300
3 Freund R et al. DNA Computing: the Existence of Universal Computers, To Appear in Theory of Computer Science
4 Gibbons A et al. Models of DNA Computation, Proceedings of 21st Internat ional Symposium on Mathematical Foundations of Computer Science 1996, MFCS '96, Cracow, Poland, 2-6 Sept. 1996:1836
5 Gibbons A et al. DNA Computing, Current Opinion in Biotechnology, 1997, 8(1):103106
6 Leete T H et al. Massively Parallel DNA Computation: Expansion of Symbol ic Determinants, Proceedings of the Second Annual Meeting on DNA based Computers , June 19964966
7 MacDonaill D A. On the Scalability of Molecular Computational Solutions to N P Problems, The Journal of Universal Computer Science, 1996, 2(2): 8 795
8 Murphy R C et al. A New Algorithm for DNA Based Computation, Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), I ndianapolis, IN, USA, 13-16 April 1997:207212
9 Reif J H. Parallel Molecular Computation: Models and Simulations, In Proceed ings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architecture s, Santa Barbara, June 1995, http://www.cs.duke.edu/reif/HomePage.html
10Roo D. Recent Developments in DNA-Computing, Proceedings of 1997 27th International Symposium on Multiple-Valued Logic, Antigonish, NS, Canada, 28-30 May 1997:39
11Roo  D, Wagner K W. On the Power of DNA-Computing, Information and Comput ation, 1996, 131(2):95109
12Winfree E. On the Computational Power of DNA Annealing and Ligation, In DNA based Computers (E. B. Baum and R. J. Lipton, editors), American Mathematical So ciety, 1996.
13Zauner K P, Conrad M. Parallel Computing with DNA: toward the Anti-Universa l Machine, Proceedings of the 4th International Conference on Parallel Problem S olving from Nature, Berlin, Germany, 22-26 Sept. 1996:696705
14Deaton R et al. A DNA Based Implementation of an Evolutionary Search for Good Encodings for DNA Computation, Proceedings of 1997 IEEE International Conf erence on Evolutionary Computation, Indianapolis, IN, USA, 13-16 April 1997:267 271
15Doi H, Furusawa M. Evolution is Promoted by Asymmetrical Mutations in DNA Re plication-Genetic Algorithm with Double-Stranded DNA, Fujitsu Scientific and T echnical Journal, 1996, 32(2):248255
16Farhat N H, Hernandez E D M. Logistic Networks with DNA-Like Encoding and I nteractions, Proceedings of International Workshop on Artificial Neural Networks , Malaga-Torremolinos, Spain, 7-9 June 1995:215222
17Manganaro G, Gyvez J P D. DNA Computing Based on Chaos, Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), Indianapol is, IN, USA, 13-16 April 1997:255260
18Nakano K et al. A Self-Organizing System with Cell-Specialization, Pro ceedings of 1997 IEEE International Conference on Evolutionary Computation, Indi anapolis, IN, USA, 13-16 April 1997:279284
19Russo M F et al. An Improved DNA Encoding Scheme for Neural Network Mode ling, World Congress on Neural Networks-San Diego. 1994 International Neural Net work Society Annual Meeting, San Diego, CA, USA, 5-9 June 1994, I/354359
20Walter K. Nonlinear Computation in the I Ching, Symbiosis of Human and Artif act, Proceedings of the Sixth International Conference on Human-Computer Intera ction, Tokyo, Japan, 9-14 July 1995, B/10531057
21Yoshikawa T et al. Emergence of Effective Fuzzy Rules for Controlling Mo bile Robots Using DNA Coding Method, Proceedings of 1996 IEEE International Conf erence on Evolutionary Computation (ICEC'96), Nagoya, Japan, 20-22 May 1996:581 586
22Yoshikawa T et al. DNA Coding Method and a Mechanism of Development for Acquisition of Fuzzy Control Rules, Proceedings of the Fifth IEEE International Conference on Fuzzy Systems (FUZZ-IEEE '96), New Orleans, LA, USA, 8-11 Sept. 19 96, 3:21942200
23Yoshikawa T et al. The Effects of Combination of DNA Coding Method with Pseudo-Bacterial GA, Proceedings of 1997 IEEE International Conference on Evolu tionary Computation (ICEC '97), Indianapolis, IN, USA, 13-16 April 1997:285290 
24Kari L. DNA Computing: Arrival of Biological Mathematics, The Mathematical I ntelligencer, 1997, 19(2): 922
25Csuhaj Varju E et al. DNA Computing Based on Splicing: Universality Resu lts, Proceedings of First Annual Pacific Symposium on Biocomputing, Hawaii, (L. Hunter, T. E. Klein, eds), World Sci. Publ., Singapore, 1996:179190
26Rozen D E et al. Molecular Computing: Does DNA Compute? Current Biology, 1996, 6(3): 254257
27Beaver D. Computing with DNA, Journal of Computational Biology, 1995, 2(1): 18
28Smith W, Schweitzer A. DNA Computers in Vitro and Vivo, DIMACS Workshop on D NA Based Computing, Princeton, April 1995
29Rothemund P. A DNA and Restriction Enzyme Implementation of Turing Machine, In DNA based Computers (E. B. Baum and R. J. Lipton, editors), American Mathemat ical Society, 1996:75119
30Baum E B. Building an Associative Memory Vastly Larger than the Brain, Scien ce, 1995, 268: 583585
31Lipton R J. DNA Solution of Hard Computational Problems, Science, 1995, 268( 5210): 542545
32Adleman L. On Constructing a Molecular Computer, In DNA based computers (E. B. Baum and R. J. Lipton, editors), American Mathematical Society, 1996, 27: 12 1
33Head T. Splicing Schemes and DNA, Nanobiology, 1992, 1: 335342
34Paun G. On the Power of the Splicing Operation, International Journal of Com puter Mathematics, 1995, 59: 2735
35Paun G. Splicing Systems with Targets Are Computationally Universal, Informa tion Processing Letters, 1996, 59(3): 129133
36Paun G et al. Computing by Splicing, Theoretical Computer Science, 1996, 168(2):321336
37Paun G, Salomaa A. DNA Computing Based on the Splicing Operation, Mathematic a japonicae, 1996, 43(3): 607
38Paun G et al. Computing by Splicing: Programmed and Evolving Splicing Sy stems, Proceedings of 1997 IEEE International Conference on Evolutionary Computa tion, Indianapolis, IN, USA, 13-16 April 1997:273277
39Head T. Formal Language Theory and DNA: an Analysis of the Generative Capaci ty of Specific Recombination Behaviors, Bulletin of Mathematical Biology, 49, 19 87:737759
40Kari L et al. At the Crossroads of DNA Computing and Formal Languages: C haracterizing Recursively Enumerable Languages by Insertion-Deletion Systems, P roceedings of 3rd DIMACS Workshop on DNA-Based Computers, Philadelphia, June 1 997:318333
41Kari L et al. DNA Computing by Using Sticker Systems, To appear in Acta Informatica
42Roweis S et al. A Sticker Based Architecture for DNA Computation, Procee dings of the Second Annual Meeting on DNA based Computers, June 1996:127
43Csuhaj-Varju E et al. Test Tube Distributed Systems Based on Splicing, Computers and AI, 1996, 15(23): 211232
44Freund R, Freund F. Test Tube Systems with Controlled Applications of Rules, Proceedings of 1997 IEEE International Conference on Evolutionary Computation ( ICEC '97), Indianapolis, IN, USA, 13-16 April 1997:237242
45Jonoska N, Karl S A. Ligation Experiments in Computing with DNA, Proceedings of 1997 IEEE International Conference on Evolutionary Computation, Indianapolis , IN, USA, 13-16 April 1997:261266
46Kari L. DNA Computing Based on Insertions and Deletions, Proceedings of Conc eptual Tools for Understanding Dynamics in Biological Systems (Coenoses, N. Kenk el ed.), London, Canada, 1996, 12
47Guarnieri F et al. Making DNA Add, Science, 1996, 273:220223
48Oliver J S. Computation with DNA-Matrix Multiplication, Proceedings of the Second Annual Meeting on DNA based Computers, June 1996:236248
49Karp R M et al. Error-Resilient DNA Computation, In 7th ACM-SIAM Sympo sium on Discrete Algorithms, 1996:458467
50Liu Q et al. A Surfaced-Based Approach to DNA Computation, Proceedings of the Second Annual Meeting on DNA based Computers, June 1996:206216
51Amos M et al. Error-Resistant Implementation of DNA Computation, Procee dings of the Second Annual Meeting on DNA based Computers, June 1996:87101


ոڣ1998-10-05
