跳到主要內容

臺灣博碩士論文加值系統

(3.233.217.106) 您好!臺灣時間:2022/08/17 21:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王宏元
研究生(外文):Hung-Yuan Wang
論文名稱:利用DNA設計生物電腦的排序器
論文名稱(外文):The Design of Sorters Based on DNA for Bio-Computers
指導教授:楊昌彪楊昌彪引用關係
指導教授(外文):Chang-Biau Yang
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:47
中文關鍵詞:互補(雜交)分子生物計算排序器酵素去氧核醣核酸
外文關鍵詞:enzymecomplementaryDNA computingmolecular computingDNA computingsorter
相關次數:
  • 被引用被引用:0
  • 點閱點閱:410
  • 評分評分:
  • 下載下載:28
  • 收藏至我的研究室書目清單書目收藏:0
DNA computing是近幾年來利用分子生物來進行數學計算和邏輯運算的一個新研究領域。可以容易地實作出較暴力的演算法,來解決一些NP-complete的問題,如Hamiltonian path problem、traveling salesperson problem和satisfiability problem。也可以用來模擬目前電腦□簡單的電路設計或晶片,如:簡單的1-bit比較器和加法器。這些主要是利用DNA可大量平行處理的特性。在本論文□,我們將利用DNA,首先設計出具有feedback能力的一個完整1-bit串流的比較器,其可完成兩個word的比較;再以此比較器為基本元件,完成一個生化的word-parallel bit-serial的排序器。事實上,我們排序器的設計方式,是可以應用在任何的sorting network來進行排序,例如:bitonic sorter和odd-even merge sorter。
In the past few years, several articles have been devoted to the study of molecular computing based on DNA in order to implement the algorithm to solve some NP-complete problems and simulate logic gates in silicon-based computers. A great deal of effort has been made on using DNA to implement simple logic gates, such as simple
1-bit comparators and simple adders, or to solve NP-complete problems, such as the Hamiltonian path problem, the traveling salesperson problem and the satisfiability problem. All of the methods rely on the capability of DNA computing which could perform computation in huge parallelism to produce all possible solutions where the answer may be derived from. In this thesis, we will first design a full bit-serial
comparator that can perform the feedback operation. Then, we will design a word-parallel bit-serial sorter which uses our comparators as the elementary building components. Our design of sorters can be applied to any sorting network, such as bitonic sorter and odd-even merge sorter.
TABLE OF CONTENTS
Page
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
Chapter 2. Basic Operations of DNA Computing . . . . . . . . . . . . 4
Chapter 3. Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1 The Hamiltonian Path Problem Solved by Adleman . . . . . . . . . . 12
3.2 The Satis.ability Problem Solved by Lipton . . . . . . . . . . . . . . 14
3.3 Solid Phase DNA Solution for the Hamiltonian Path Problem . . . . 16
3.4 SAT’s Solution by HaoyangWu . . . . . . . . . . . . . . . . . . . . . 20
3.5 Amos’s NAND Boolean Circuits . . . . . . . . . . . . . . . . . . . . . 22
3.6 DNA Adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chapter 4. A Word-Parallel Bit-Serial Sorter . . . . . . . . . . . . . . 29
4.1 A Bit-Serial Comparator . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 The Encoding of the Comparator . . . . . . . . . . . . . . . . . . . . 31
4.3 How toMake the Biological SorterWork . . . . . . . . . . . . . . . . 36
4.4 Implementation of the Bitonic Sorters . . . . . . . . . . . . . . . . . 40
Chapter 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
[1] L. M. Adleman, “Molecular computation of solutions to combinatorial problems,”Science, Vol. 266, pp. 1021—1024, Nov. 1994.[2] S. G. Akl, The Design and Analysis of Parallel Algorithms. Prentice-Hall,Englewood Cli.s, New Jersey, USA, .rst ed., 1989.[3] M. Amos, P. E. Dunne, and A. Gibbons, “DNA simulation of boolean circuits,”Genetic Programming 1998: Proceedings of the Third Annual Conference, Universityof Wisconsin, Madison, Wisconsin, pp. 679—683, 1998.[4] K. E. Batcher, “Sorting networks and their applications,” In Proceedings of theAFIPS Spring Joint Computer Conference, Atlantic City, NJ, USA, Vol. 32,pp. 307—314, 1968.[5] E. B. Baum and D. Boneh, “Running dynamic programming algorithms on aDNA computer,” In Proceedings of the Second Annal Meeting on DNA basedComputers, held at Princeton University, pp. 10—12, June 1996.[6] R. H. Garrett and C. M. Grisham, Biochemistry. Emily Barrosse, John J.Vondeling, second ed., 1998.[7] G. Gloor, L. Kari, M. Gaasenbeek, and S. Yu, □owards a DNA solution tothe shortest common superstring problem,?International Journal on Arti.cialIntelligence Tools, Vol. 8, No. 4, pp. 385?99, 1999.[8] F. Guarnieri and M. Fliss, “Making DNA add,” Science, Vol. 273, pp. 220—223,July 1996.[9] M. Hagiya, “From molecular computing to molecular programming,” Proceedings6th DIMACS Workshop on DNA Based Computers, held at the Universityof Leiden, p. 87, June 2000.[10] T. Hinze and M. Sturm, “A universal functional approach to DNA computingand its experimental practicability,” Proceedings 6th DIMACS Workshop onDNA Based Computers, held at the University of Leiden, Leiden, The Netherlands,13 - 17 June 2000, p. 257, 2000.[11] J.-S. Hwu and R.-J. Chen, “DNA solution to the traveling salesman optimizationproblem,” 1998 International Computer Symposium Workshop on Algorithms,Tainan, Taiwan, pp. 17—19, dec. 1998.[12] Jonoska and Karl, “Ligation experiments in computing with DNA,” Proceedingsof 1997 IEEE International Conference on Evolutionary Computation, UniversityPlace Hotel Indianapolis, pp. 261—266, 1997.[13] S. Y. Lila Kari, Greg Gloor, “Using DNA to solve the bounded post correspondenceproblem,” Theoretical Computer Science, Vol. 231, pp. 193—203, 2000.[14] R. J. Lipton, “Using DNA to solve NP-complete problems,” Science, Vol. 268,pp. 542—545, Apr. 1995.[15] N. Morimoto, M. Arita, and A. Suyama, “Solid phase DNA solution to theHamiltonian path problem,” Proceedings of the 3rd DIMACS Workshop onDNA Based Computers, University of Pennsylvania, U.S.A, pp. 83—92, 1997.[16] E. Ogihara and A. Ray, “Executing parallel logical operations with DNA,”Proceedings of the Congress on Evolutionary Computation, Washington, DC,Vol. 2, pp. 972—979, June 1999.[17] M. Ogihara and A. Ray, “DNA-based self-propagating algorithm for solvingbounded-fan-in boolean circuits,” Genetic Programming 1998: Proceedings ofthe Third Annual Conference, University of Wisconsin, Madison, Wisconsin,pp. 725—730, April 1998.[18] F. Qiu and M. Lu, “A new solution for boolean circuit with DNA computer,”Department of Electrical Enginnering Teax University College Station, Texas,U.S.A, April 2000.[19] S.-Y. Shin, B.-T. Zhang, and S.-S. Jun, “Solving traveling salesman problemsusing molecular programming,” Proceedings of the Congress on EvolutionaryComputation, Washington, DC, Vol. 2, pp. 994—1000, 1999.[20] E. Stoschek, M. Sturm, and T. Hinze, “On a DNA experiment for solving acertain NP-complete problem,” Technical Report TUD-FI99-02, Dresden Universityof Technology, Germany, Aug. 1999.[21] S. P. V. Gupta and M. J. Zaki, “Arithmetic and logic operations with DNA,”Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, held atthe University of Pennsylvania, pp. 212—220, June 1997.[22] H. Wu, “An improved surface-based method for DNA computation,” BioSystems,Vol. 59, pp. 1—5, 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top