簡易檢索 / 詳目顯示

回結果列表
研究生： 黃昭文
Huang, Chao-Wen
論文名稱： 以DNA運算解圖形同構問題
DNA Computing on Graph Isomorphism Problems
指導教授： 謝孫源
Hsieh, Sun-Yuan
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2010
畢業學年度： 98
語文別： 英文
論文頁數： 102
中文關鍵詞： DNA計算 、DNA演算法 、分子計算 、子圖同構問題 、最大共同子圖問題
外文關鍵詞： DNA-based computing, DNA-based algorithms, molecular computing, the subgraph isomorphism problem, the maximum common subgraph problem, NP-complete
相關次數： 點閱：142  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 1961年的時候，Feynman首先提出DNA分子計算的觀念，但當時候，他所提出來的概念並沒有被實做出來。幾十年過去了，Adleman成功地以DNA strand為資訊記錄的方式，用DNA試管解決了漢彌爾頓路徑問題。自從該次實驗證明DNA計算的可行性之後，DNA計算已經被用來解決相當多的決定及組合最佳化問題。在本篇論文中，我們使用Andleman-Lipton模型，並提出了一種DNA為基礎的圖形編碼架構，該架構可以用來解決一些棘手的圖形問題，例如：子圖同構問題，以及其一般化的問題--最大共同子圖問題，這兩個問題是相當知名的NP-complete問題，在該模型下，只需要多項式次數的基本DNA操做即可得到解答。

    Feynman first proposed DNA-based computation in 1961, but his idea was not implemented by experiment for a few decades. By properly manipulating DNA strands as the input instance of the Hamiltonian path problem, Adleman succeeded in solving the problem in a test tube. Since the experimental demonstration of its feasibility, DNA-based computing has been applied to a number of decision or combinatorial optimization problems. In this thesis, we propose a DNA-based graph encoding scheme which can be used to solve some intractable graph problems, such as the subgraph isomorphism problem and its generalized problem - the maximum common subgraph problem, which are known to be NP-complete problems, in the Adleman-Lipton model using polynomial number of basic biological operations.

    Abstract in Chinese............... i Abstract........................ ii Thanks........................ iii Contents....................... iv List of Tables...................... vii List of Figures......................viii 1 Introduction...................... 1 1.1 Basics of DNA Computing................. 1 1.2 History of DNA Research.................. 7 1.3 Properties of DNA..................... 9 1.4 DNA sequence...................... 13 1.5 Basics of Graph Theory................... 15 1.6 History of Graph Theory.................. 20 1.7 NP-complete Problems................... 22 1.8 Contribution...................... 26 2 Graph Isomorphism Problems................ 28 2.1 Notations.......................... 28 2.2 Graph Isomorphism..................... 29 2.3 Graph Isomorphism Problems................ 31 2.4 Subgraph Isomorphism Problems.............. 32 2.5 Maximum Common Subgraph Problems.......... 35 3 The Adleman-Lipton Model................. 37 4 Sticker-based Solution Space................ 39 4.1 Using Stickers for Generating the Permutation Set..... 40 4.2 Using Stickers for Generating the Solution Space...... 42 5 Solving the Subgraph Isomorphism Problem........ 45 6 Solving the Maximum Common Subgraph Problem.... 52 7 Experimental Data.................... 57 7.1 Biopython and Python.................. 57 7.1.1 Biopython...................... 57 7.1.2 Introduction of Python................ 57 7.1.3 Programming Philosophy............... 59 7.1.4 Name and Neologisms................. 61 7.1.5 Usage....................... 62 7.2 Implementation in the Web Server............. 63 8 Discussion and Conclusion.................. 67 Bibliography...................................68 A Main Code in the Web Server................ 78 A.1 DNASequence.py..................... 78 A.2 DNATool.py........................ 88 A.3 Interfaces.py...................... 90 A.4 GeneralConstraint.py.................. 91 A.5 DNASequences.py.................. 93

    [1] L. M. Adleman, Molecular computation of solutions to combinatorial problems", Science, 266:1021{1024, 1994.
    [2] L. M. Adleman, On constructing a molecular computer, DNA based computers," in DNA Based Computers (Selected Papers from Proc. DI- MACS Workshop DNA Based Computers95), DIMACS Series in Dis- crete Mathematics and Theoretical Computer Science, 1996, pp. 1{21.
    [3] L. M. Adleman, P. W. K. Rothemund, S. Roweis, and E. Winfree, On applying molecular computation to the data encryption standard," in Proc. 2nd Annu. Workshop DNA Computing, DIMACS Series in Dis- crete Mathematics and Theoretical Computer Science, 1999, pp. 31{44.
    [4] M. Amos, DNA computation," Ph.D. dissertation, Dept. Comput. Sci., Univ. Warwick, Coventry, U.K., 1997.
    [5] M. Amos and P. E. Dunne, DNA simulation of Boolean circuits," Uni- versity of Liverpool, Liverpool, U.K., Tech. Rep. CTAG-97 009, Dec 1997.
    [6] M. Arita, A. Suyama, and M. Hagiya, A heuristic approach for the Hamiltonian path problem with molecules," in Proc. 2nd Genetic Pro- gramming Conf. (GP 97), pp. 457{462.
    [7] A. Atanasiu, Arithmetic with membrames," in Proc. Workshop Mutise Processing, 2000, pp. 1{17.
    [8] E. Bach, A. Condon, E. Glaser, and C. Tanguay, DNA models and algo- rithms for NP-complete problems," in Proc. 11th Annu. Conf. Structure in Complexity Theory, 1996, pp. 290{299.
    [9] R. Barua and J.Misra, Binary arithmetic for DNA computers," in Proc. 8th Int. Workshop DNA Based Computers, 2002, pp. 124{132.
    [10] G. M. Blackburn and M. J. Gait, Nucleic Acids in Chemistry and Biol- ogy. Washington, DC: IRL, 1990.
    [11] D. Boneh, C. Dunworth, and R. J. Lipton, Breaking DES Using a Molecular Computer," Princeton Univ., Princeton, NJ, Tech. Rep. CS- TR-489-95, 1995.
    [12] R. S. Braich, C. Johnson, P. W. K. Rothemund, D. Hwang, N. Chelyapov, M. Leonard, and L. M. Adleman, Solution of a satis¯abil- ity problem on a gel-based DNA computer", in Proceedings of the Sixth International Conference on DNA Computation (DNA 2000), Lecture Notes in Computer Science 2054, pp. 27{42, 2001.
    [13] R. S. Braich, C. Johnson, P. W. K. Rothemund,D. Hwang,N. Chelyapov, and L. M. Adleman, Solution of a 20-variable 3-SAT problem on a DNA computer," Science, vol. 296, no. 5567, pp. 499{502, Apr. 2002.
    [14] D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall, On the computa- tional power of DNA," In Discrete Appl. Math. (Special Issue on Com- putational Molecular Biology), vol. 71, pp. 79{94, 1996.
    [15] W. L. Chang and M. Guo and J. Cao, Using Sticker to Solve the 3-Dimensional Matching Problem in Molecular Supercomputers", In- ternational Journal of High Performance Computing and Networking, 1(1/2/3), pp. 128 - 139, 2004.
    [16] W. L. Chang, Fast Parallel DNA-based Algorithms for Molecular Com- putation: the Set-Partition Problem", IEEE Transactions on Nanobio- science, 6(1): 346{353, 2007.
    [17] W. L. Chang and M. Guo, Solving the set cover problem and the prob- lem of exact 3 cover by 3-sets in the Adleman-Lipton model", Biosystems, 72(3):263{275, 2003.
    [18] W. L. Chang and M. Guo, Solving the dominating-set problem in the AdlemanVLipton model," in Proc. 3rd Int. Conf. Parallel and Dis- tributed Computing, Applications and Technologies, 2002, pp. 167{172.
    [19] W. L. Chang and M. Guo, Solving the clique problem and the vertex cover problem in the AdlemanVLipton's model," in Proc. IASTED Int. Conf. Networks, Paralle and Distributed Processing, and Applications, 2002, pp. 431{436.
    [20] W. L. Chang, M. Guo, and M. Ho, Solving the set-splitting problem in sticker-based model and the AdlemanVLipton model", Future Genera- tion Computer Systems, 20(5):875{885, 2004.
    [21] W. L. Chang, M. Guo, and M. Ho, Molecular solutions for the subset- sum problem on DNA-based supercomputing", Biosystems, 73(2):117{ 130, 2004.
    [22] W. L. Chang, M. Guo, and M. Ho, Fast parallel molecular algorithms for DNA-based computation: factoring integers", IEEE Transactions on Nanobioscience, 4(2): 149{163, 2005.
    [23] W. Contributors. DNA." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 28 Jul. 2010.
    [24] W. Contributors. Graph theory." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 16 Jul. 2010.
    [25] S. A. Cook, The complexity of theorem-proving procedures," in Proc 3rd Annu. ACM Symp. Theory of Computing, 1971, pp. 151{158.
    [26] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (Second Eition), MIT Press, Cambridge, 2001.
    [27] A. R. Cukras, D. Faulhammer, R. J. Lipton, and L. F. Landweber, Chess games: a model for RNA-based computation," in Proc. 4th DI- MACS Meeting DNA Based Computers, Jun. 1998, pp. 27{37.
    [28] F. Eckstein, Oligonucleotides and Anologues. Oxford, U.K.: Oxford Univ. Press, 1991.
    [29] D. Faullhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber, Molecular computation: RNA solutions to chess problems", in Proceed- ings of National Academica Science U.S.A. 97, pp. 1385{1389, 2000.
    [30] R. P. Feynman, In Minaturization, D. H. Gilbert, Ed. New York: Rein- hold, 1961, pp. 282{296.
    [31] P. Frisco, Parallel arithmetic with splicing," Romanian J. Inf. Sci Tech- nol., vol. 3, pp. 113{128, 2000.
    [32] B. Fu, Volume bounded molecular computation," Ph.D. Thesis, Dept Comput. Sci., Yale Univ., New Haven, CT, 1997.
    [33] M. R. Garey and D. S. Johnson, Computers and Intractability - A Guide to the Theory of NP-completeness, W. H. Freeman, 1979.
    [34] S. D. Gillmor, P. P. Rugheimer, and M. G. Lagally, Computing with DNA on surfaces", Surface Science, 500:699{721, 2002.
    [35] F. Guarnieri, M. Fliss, and C. Bancroft, Making DNA add", Science, 273:220-223, 1996.
    [36] V. Gupta, S. Parthasarathy, and M. J. Zaki, Arithmetic and logic oper- ations with DNA," in Proc. 3rd DIMACS Workshop DNA Based Com- puters, 1997, pp. 212{220.
    [37] M. Guo, M. Ho, and W. L. Chang, Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing", Par- allel Computing, 30: 1109{1125, 2004.
    [38] M. Guo and W. L. Chang and M. Ho and J. Lu and J. Cao. Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing", BioSystems, 80(1), pp. 71-82, 2005.
    [39] M. Guo and M. Ho and W. L. Chang, Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing", Par- allel Computing, 30(9-10), pp. 1109-1125, 2004.
    [40] M. Ho, W. L. Chang, and M. Guo, Is cook's theorem correct for DNA- based computingXtoward solving the NP-complete problems on a DNA- based supercomputer model," J. Parallel Distrib. Sci. Eng Comput., to be published.
    [41] M. Ho and W. L. Chang, M. Guo and L. T. Yang, Fast Parallel Solu- tion For Set-Packing and Clique Problems by DNA-based Computing", IEICE Transactions on Information and Systems, E-87D(7), pp. 1782{ 1788, 2004.
    [42] H. Hug and R. Schuler, DNA based parallel computation of simple arithmetic," in Proc. 7th Workshop DNA Based Computers, 2001, pp. 159{166.
    [43] R. M. Karp, Reducibility among combinatorial problems," in Complex- ity of Computer Computation. New York: Plenum, 1972, pp. 85{103.
    [44] R. J. Lipton, DNA solution of hard computational problems", Science, 268:542{545, 1995.
    [45] M. C. LaBean, T. H. Reif, and J. H. Seeman, Logical computation us- ing algorithmic self-assembly of DNA triple-crossover molecules," Nature vol. 407, pp. 493{496, 2000.
    [46] T. H. LaBean, E. Winfree, and J. H. Reif, Experimental progress in computation by self-assembly of DNA tilings," Theor. Comput., vol. 54, pp. 123{140, 2000.
    [47] Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith, DNA computing on surfaces", Nature, 403:175{179, 2000.
    [48] K. Mir, A restricted genetic alphabet for DNA computing," in DNA Based Computers II: Proc. DIMACS Workshop 1996, vol. 44, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, E B. Baum and L. F. Landweber, Eds., 1998, pp. 243-246.
    [49] N. Morimoto, M. Arita, and A. Suyama, Solid phase DNA solution to the Hamiltonian path problem," in Proc. 3rd DIMACS Workshop DNA Based Computers, vol. 48, 1999, pp. 93{101.
    [50] A. Narayanan and S. Zorbala et al., DNA algorithms for computing shortest paths," in Proc. 3rd Annu. Conf. Genetic Programming 1998, pp. 718{724.
    [51] M. Ogihara and A. Ray, Simulating Boolean circuits on a DNA com- puter," Univ. Rochester, Rochester, NY, Tech. Rep. TR631, Aug. 1996.
    [52] Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber, DNA solution of the maximal clique problem", Science, 278:446{449, 1997.
    [53] G. P•aun, G. Rozenberg, and A. Salomaa, DNA Computing: New Com- puting Paradigms, Springer-Verlag, Berlin, pp. 117{149, 1998.
    [54] M. J. Perez-Jimenez and F. Sancho-Caparrini, Solving knapsack prob- lems in a sticker based model," in Proc. 7nd Annu.Workshop DNA Com- puting, DIMACS Series in Discrete Mathematics and Theoretical Com- puter Science, 2001, pp. 161{171.
    [55] Z. F. Qiu and M. Lu, Arithmetic and logic Operations with DNA com- puters," in Proc. 2nd IASTED Int. Conf. Parallel and Distributed Com- puting and Networks, 1998, pp. 481-486.
    [56] J. H. Reif, T. LaBean, and H. Seeman, Challenges and applications for self-assembled DNA-nanostructures," in Proc. 6th DIMACS Workshop DNA Based Computers, 2002, pp. 145{172.
    [57] S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman, A sticker based model for DNA computation", in Proceedings of the Second Annual Worksop on DNA Computing, DIMACS: Series in Discrete Mathematics and The- oretical Computer Science, American Mathematical Society, pp. 1{29, 1999.
    [58] K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yoko- mori, and M. Hagiya, Molecular computation by DNA hairpin forma- tion", Science, 288:1223{1226, 2000.
    [59] R. R. Sinden, DNA Structure and Function, Academic Press., 1994.
    [60] S. Y. Shin, B. T. Zhang, and S. S. Jun, Solving traveling salesman prob- lems using molecular programming," in Proc. 1999 Congr. Evolutionary Computation (CEC 99), vol. 2, pp. 994{1000.
    [61] J.Watson, M. Gilman, J.Witkowski, and M. Zoller, Recombinant DNA, 2nd ed. San Francisco, CA: Freeman, 1992.
    [62] J. Watson, N. Hoplins, and J. Roberts et al., Molecular Biology of the Gene. Menlo Park, CA: Benjamin/Cummings, 1987.
    [63] D. B. West, Introduction to Graph Theory, Prentice Hall, NJ, 2 edtion, 2001.

    無法下載圖示 校內：2015-09-03公開
    校外：不公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE