中文
Announcement
More
Progress in Chemistry 2002, Vol. 14 Issue (01): 37- Previous Articles   Next Articles

Special Issue: 计算化学

• Review •

Advances in Biomolecular Computing

Shao Xueguang**;Jiang Haiyan;Cai Wensheng   

  1. Department of Applied Chemistry, University of Science and Technology of China, Hefei 230026, China; Department of Chemistry, University of Science and Technology of China, Hefei 230026, China
  • Received: Revised: Online: Published:
  • Contact: Shao Xueguang
PDF ( 1815 ) Cited
Export

EndNote

Ris

BibTeX

Due to the high parallelism and recognition ability of the biomolecules in biochemical reactions, biomolecular computing behaves great advantage in solving combinatorial optimization problems. Biomolecular computing has been successfully applied in computing NP complete problems such as Hamiltonion path problem, maximal clique problem and SAT problems in Boolean calculation, etc. This paper presents a review of fundamental ideas, computing methods, applications and advances in biomolecular computing. Furthermore, the developmental trend of biomolecular computing is described.

CLC Number: 

[ 1 ] Garzon M H, Deaton R J. IEEE Transactions on Evolutionary Computation, 1999, 3 (3) : 236—250
[ 2 ] Shao X G, Chen Z H, Lin X Q. 分析化学(Chin. J. Anal.Chem. ) , 2000, 28: 152—155
[ 3 ] Adleman L M. Science, 1994, 266: 1021—1024
[ 4 ] Ouyang Q , Kaplan P D, Liu S, et al. Science, 1997, 278:446—449
[ 5 ] Hagiya M. New Generation Comput. , 1998, 17: 131
[ 6 ] Winfree E, Liu F, Wenzler L A , et al. Nature, 1998, 394:539—544
[ 7 ] Sakamoto K, et al. BioSystem s, 1999, 52: 81
[ 8 ] Sakamoto K, Gouzu H, Kiga D, et al. Science, 2000, 288:1223—1226
[ 9 ] Hagiya M , Arita M , Kiga D, et al. in Proc. Second Annual Genetic Programming Conf. (ed. Koza J R ). San Mateo, CA:Morgan Kaufmann, 1997. 105—115
[ 10 ] Winfree E. in Proc. Fourth DIMACS Workshop on DNA Computers (ed. Rubin H). Univ. of Pennsylvania, Philadelphia, 1998. 175—188
[ 11 ] Faulhammer D, Cukras A R, Lipton R J , et al. Proc. Natl.Acad. Sci. , 2000, 97: 1385—1389
[ 12 ] Seife C. Science, 2000, 287: 1182- 1183
[ 13 ] Cukras A R, Faulhammer D, Lipton R J , et al. BioSystems,1999, 52: 35—45
[ 14 ] Murphy R C,Deaton R, Franceschetti D R, et al. A New Algorithm for DNA Based Computation, IEEE, 1997, 207—212
[ 15 ] Garzon M , Gao Y, Rose J A , et al. , in Proc. Second Workshop on Implementing Automata WIA 297 (Lecture Notes in Computer Science, vol. 1436 ). Berlin: Springer-Verlag,1998. 56—74
[ 16 ] Shapiro E. in Proc. Fifth International Meeting on DNA Based Computers ( DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ed. W infree E ). Providence , R I: Amer. Math. Soc. , 1999
[ 17 ] Lipton R J. Science, 1995, 268: 542—545
[ 18 ] Amos M , Dunne P E, Gibbons A. in Proc. Third Annual Genetic Programming Conf. ( ed. Koza J R). San M ateo, CA:Mo rgan Kaufmann, 1998. 679—683
[ 19 ] Morimoto N , Arita M , Suyama A. in DNA Based Computers II, Proc. of the Second DIMACS Workshop on DNA Based Computers (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 44, ed. Landweber L F ) ,Providence, R I: Amer. Math. Soc. , 1999
[ 20 ] Freud R, Freud F. Proceeding of 1997 IEEE International Conference on Evolutionary Computation ( ICEC’97 ). Indianapolis, IN , USA , 1997. 237—242
[ 21 ] Csuhaj Varju E, et al. Computers and A I, 1996, 15 (223) :211—232
[ 22 ] Cai W , Condon A E, Corn R M , et al. Journal of Computational Biology, 1997, (1) : 47—77
[ 23 ] Smith L M , Corn R M , Condon A E, et al. Journal of Computational Biology, 1998, 5 (2) : 255—267
[ 24 ] Liu Q , Wang L , Frutos A G, et al. Nature, 2000, 403:175—179
[ 25 ] Liu Q , Frutos A G, Thiel A J , et al. Journal of Computational Biology, 1998, 5 (2) : 269—278
[ 26 ] Frutos A G, Liu Q , Thiel A J , et al. Nucleic Acids Research,1997, 25 (23) : 4748—4757
[ 27 ] Wang L , Liu Q , Corn R M , et al. J. Am. Chem. Soc. ,2000, 122 (31) : 7435—7440
[ 28 ] Frutos A G, Smith L M , Corn R M. J. Am. Chem. Soc. ,1998, 120 (40) : 10277—10282
[ 29 ] Wang L , Liu Q , Frutos A G, et al. BioSystems, 1999, 52:189—191
[ 30 ] Arita M , Suyama A , Hagiya M. in Proc. Second Annual Genetic Programming Conf. (ed. Koza J R ) , San Mateo, CA:Morgan Kaufmann, 1997. 457—462
[ 31 ] Liu Q , Frutos A G, Wang L , et al. BioSystems, 1999, 52:25—33
[ 32 ] Eng T L. BioSystems, 1999, 52: 135—141
[ 33 ] Oliver J S. J. Mol. Evol. , 1997, 45: 161—167
[ 34 ] Pǎun G. Soft Computing , 1999, 3: 30—36
[ 35 ] Manca V , Martin-Vide C, Pǎun G. BioSystems, 1999, 52:47—54
[ 36 ] Aoi Y, Yoshinobu T, Tanizawa K, et al. Jpn. J. Appl.Phys. , 1998, 37: 5839—5841
[ 37 ] Kari L , Gloor G, Yu S. Theoretical Computer Science, 2000,231: 193—203
[ 38 ] Jonoska N , Karl S. Second DIMACS Workshop on DNA Based Computers, Princeton, 1996, D IMACS Series. AMS Press. 1999, 44: 87—96
[ 39 ] Guarnieri F, Fliss M , Bancroft C. Science, 1996, 273: 220—223
[ 40 ] Beaver D. Journal of ComputationalBiology, 1995, 2 (1) : 1—8
[ 41 ] Boneh D, Dunworth C, Lipton R. First DIMACS Work shop on DNA Based Computers, P rinceton, 1995, DIMACS Series. AMS Press, 1996, 27: 37—65
[ 42 ] L eete T, Schwartz M , W illiam s R, et al. Second DIMACS Workshop on DNA Based Computers, Princeton, 1996, DIMACS Series. AMS Press, 1999, 44: 45—58
[ 43 ] Willams R, Wood D. Second DIMACS Workshop on DNA Based Computers, Princeton, 1996. 260—268
[ 44 ] Kobayashi S, Yokomori T, Sampei G, et al. Proc. IEEE Internat. Conf. on Evolutionary Computation, IN , 1997. 213—217
[ 45 ] Boneh D, Dunworth C, Lipton R, et al. in DNA Based Computers II, Proc. of the Second DIMACS Workshop on DNA Based Computers (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 44, ed. Landweber L F). Providence, R I: Amer. Math. Soc. , 1999. 163—171
[ 46 ] Karp R, Kenyon C, Warts O. in Proc. Seventh Ann. Symp.Discrete Algorithms, SODA , 1996. 458—467
[ 47 ] Adleman L M. in DNA Based Computers, Proc. First DIMACS Workshop on DNA Based Computers (DIMACS Series in Discrete Mathematics and Theoretical Computer Science,vol. 27, ed. Landweber L F). Providence, R I: Amer. Math.Soc. , 1996. 1—21
[ 48 ] Deaton R, Murphy R C, Garzon M , et al. in DNA Based Computers II, Proc. of the Second DIMACS Workshop on DNA Based Computers (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 44, ed.Landweber L F) , Providence, R I: Amer. Math. Soc. , 1999.159
[ 49 ] Deaton R, Garzon M , Murphy R C, et al. in Proc. First Ann. Genetic Programming Conf. . Stanfo rd U niv. , Stanfo rd, CA , 1996. 9—15
[ 50 ] Deaton R, Murphy R, Rose J , et al. in Proc. IEEE Conf.Evolutionary Computation, IN , 1997. 267—271
[ 51 ] Hagiya M. in Proc. Third Annual Genetic Programming Conf. (ed. Koza J R). San Mateo, CA: Mo rgan Kaufmann,1998. 691—699
[ 52 ] Garzon M H, Deaton R J , Barnes K. in Proc. Genetic and Evolutionary Computation Conf. GECCO 299 ( ed. Bahnzhaf W ). San Mateo, CA: Morgan Kaufmann, 1999. 1805—1899
[ 53 ] 陈霄燕(Chen X Y) , 江龙(Jiang L ). 化学进展( Prog.Chem. ) , 1999, 11 (1) : 71—79
[ 54 ] 任立红(Ren L H) , 丁永生(Ding Y S) , 邵世煌(Shao S H). 信息与控制( Information and Contro l) , 1999, 28 (4) : 241—248
[ 55 ] Chen J , Antipc E, Lemieux B, et al. in Proc. Genetic and Evolutionary Computation Conf. GECCO 299 ( ed. Bahnzhaf W ). San Mateo, CA: Morgan Kaufmann, 1999. 1835—1841
[ 56 ] Deaton R, Garzon M , Rose J A. in Proc. IEEE Int. Conf.System s (Man and Cybernetics ). Piscataway, NJ: IEEE Press, 1999. 369—374

[1] Xiaoyao Yin, Fei Li, Xiaochen Bo, Zhigang Luo, Xiaolei Zuo. Computation in Chemistry:A Summary of the Development and Models of DNA Computing [J]. Progress in Chemistry, 2017, 29(11): 1297-1315.
Viewed
Full text


Abstract

Advances in Biomolecular Computing