跳到主要內容

臺灣博碩士論文加值系統

(18.204.48.64) 您好!臺灣時間:2021/07/30 10:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王郁仁
研究生(外文):Yu-Jen Wang
論文名稱:生物資訊邏輯系統加法器乘法器架構:最大權重Clique及離散對數問題分子計算最佳化
論文名稱(外文):Bioinformatics Logic Computing: MaximumWeighted Clique and Discrete Logarithm Problems
指導教授:何善輝
指導教授(外文):Shan-Hui Ho
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:146
中文關鍵詞:最大團圖問題DNA超級計算分子生物超級計算生物邏輯平行計算離散對數問題最大權重團圖問題
外文關鍵詞:Biological parallel computingMolecular-based supercomputingDNA-based supercomputingDiscrete logarithm problemMaximum weighted clique problemMaximal clique problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:140
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,生物計算被研究者們利用來解決許多NP問題(Adleman M. L.,
1994; Amos, 1997; Chang, Guo, & Ho, 2005)。本論文根據Adleman的平台,
提出了一個新的最佳化生物資訊邏輯平台,並以此平台為基礎,展示如何
解決最大團圖、最大權重團圖,以及離散對數問題。首先,我們建立生物
計算邏輯單元,分別為平行AND器、平行OR器、平行XOR器等。接著以
此生物計算邏輯單元,建立生物計算算數單元,平行加法器及平行乘法
器。最後,應用此一新最佳化生物資訊邏輯平台,解決兩大NP問題,最大
團圖及離散對數問題。
最大權重團圖問題為一常見的NP問題,它經常被應用於電腦視覺、樣
式辨認以及機器人學等領域。最常的利用方式,是利用權重的圖形來表達
高層次的圖像化資訊。離散對數問題同樣為一NP問題,許多密碼系統皆是
利用離散對數來做為安全的基礎,較常見的有Diffie-Hellman公鑰加密系統
及橢圓曲線加密系統。在本論文中,我們根據分子生物邏輯計算平台提出
了一新的分子生物邏輯計算演算法,解決最大團圖、最大權重團圖,以及
離散對數問題。
Bioinformatics computing has been utilized by many researchers to solve NP
problems in recent years (Adleman M. L., 1994; Amos, 1997; Chang, Guo, & Ho,
2005). This thesis proposed and applied a recent newly developed optimal
bioinformatics bio-logical model, based upon Adleman-Lipton model, to solve
maximal clique, maximum weighted clique and discrete logarithm problems. First, the
logical gates (bio-logical units) parallel AND, parallel OR, and parallel XOR have
been constructed for building up arithmetic units such as parallel adder and multiplier.
Second, three NP problems, maximal clique, maximum weighted clique and discrete
logarithm problems, are solved by this optimal bioinformatics bio-logical model.
The maximum weighted clique problem (MWCP) is one of the well-known NP
problems. The MWCP has important applications in such fields as computer vision,
pattern recognition, and robotics, where weighted graphs are employed as a
convenient means of representing high-level pictorial information. The discrete
logarithm problem is a NP problem. It is the basis for the security of many
cryptosystems including the Diffie-Hellman protocol and Elliptic Curve Cryptosystem.
In this thesis, we proposed newly parallel bio-molecular logic computing algorithms
based on bio-molecular logic computing model to solve the maximal clique,
maximum weighted clique and discrete logarithm problems.
中文摘要........................................................................................................................ ii
英文摘要....................................................................................................................... iii
誌 謝....................................................................................................................... iv
List of Contents .............................................................................................................. v
List of Tables .................................................................................................................. v
List of Figures ............................................................................................................ viii
1. Introduction ............................................................................................................ 1
1.1. Background .................................................................................................... 1
1.2. Motivation ...................................................................................................... 2
2. Literature Review................................................................................................... 4
2.1. The Structure of DNA .................................................................................... 4
2.2. Models of DNA Computation ........................................................................ 7
2.2.1. Taxonomy of Models of DNA Computation ................................................. 7
2.2.2. The Sticker-based Model ............................................................................... 8
2.2.3. DNA Manipulators ......................................................................................... 9
3. Basic Boolean Bio-circuit Operations with Bio-molecular Computing .............. 11
3.1. NOT Operation on Bio-molecular Computing ............................................ 11
3.1.1. Construction for the Parallel NOT Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 12
3.1.2. Construction for the Parallel NOT Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 14
3.2. AND Operation on Bio-molecular Computing ............................................ 15
3.2.1. Construction for the Parallel AND Operation of a Bit on Bio-molecular
ii
Computing.................................................................................................................... 16
3.2.2. Construction for the Parallel AND Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 19
3.3. Construction of a Parallel OR ...................................................................... 20
3.3.1. Construction for the Parallel OR Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 21
3.3.2. Construction for the Parallel OR Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 23
3.4. Construction of a Parallel NOR ................................................................... 25
3.4.1. Construction for the Parallel NOR Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 26
3.4.2. Construction for the Parallel NOR Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 28
3.5. Construction of a Parallel NAND ................................................................ 29
3.5.1. Construction for the Parallel NAND Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 30
3.5.2. Construction for the Parallel NAND Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 32
3.6. Construction of a Parallel XOR ................................................................... 34
3.6.1. Construction for the Parallel XOR Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 35
3.6.2. Construction for the Parallel XOR Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 37
3.7. Construction of a Parallel XNOR ................................................................ 38
3.7.1. Construction for the Parallel XNOR Operation of a Bit on Bio-molecular
Computing.................................................................................................................... 39
iii
3.7.2. Construction for the Parallel XNOR Operation of N Bits on Bio-molecular
Computing.................................................................................................................... 41
4. Parallel Adder and Multiplier ............................................................................... 43
4.1. The Construction of Parallel Adder ............................................................. 43
4.1.1. The Construction of the Parallel One-bit Adder .......................................... 43
4.1.2. The Construction of a N-bits Parallel Adder ................................................ 46
4.2. The Construction of One-bit Parallel Multiplier .......................................... 47
4.3. The Construction of a N-bit Parallel Multiplier ........................................... 49
4.3.1. Generation of DNA Strands for the Input Operands of a Parallel N-bit
Multiplier ..................................................................................................................... 49
4.3.2. The Construction of a Parallel N-Bit Multiplier .......................................... 52
4.3.3. The Example Results of a Parallel N-Bits Multiplier .................................. 54
5. Maximum Weighted Clique Problem .................................................................. 57
5.1. Solving the Clique Problem on Bio-molecular Computing ......................... 57
5.1.1. Definition of Maximal Clique Problem ....................................................... 57
5.1.2. Algorithm of Solving the Maximal Clique Problem .................................... 58
5.1.3. The Complexity of Algorithm 5.1 ................................................................ 61
5.1.4. The Example of Simulated DNA Computing .............................................. 63
5.2. Solving the Maximum Weighted Clique Problem on Bio-molecular
Computing.................................................................................................................... 65
5.2.1. Definition of Maximum Weighted Clique Problem ..................................... 65
5.2.2. Solving the maximum weighted clique problem ......................................... 66
5.2.3. The Example of Simulated DNA Computing .............................................. 72
5.2.4. The Complexity of Algorithm 5.2 ................................................................ 77
6. The Discrete Logarithm Problem ......................................................................... 78
6.1. Introduction of Discrete Logarithm Problem ............................................... 78
iv
6.2. Introduction of Diffie-Hellman key Exchange Protocol .............................. 80
6.3. Bio-molecular Optimization Solution for Discrete Logarithm Problem ..... 81
6.4. DNA Algorithm to Solve Discrete Logarithm Problem ............................... 82
6.5. Construction of Discrete Logarithm Algorithm Modules ............................ 86
6.5.1. Solution Space for 2k Possible Discrete Logarithms ................................... 86
6.5.2. Solution Space for Ordern(M) ..................................................................... 87
6.5.3. Solution Space for a MODULE n and a Primitive Root M ......................... 90
6.5.4. Solution Space for the Result of an Exponential Modular Operation C ...... 92
6.5.5. Algorithm of a Modular Multiplication ....................................................... 93
6.5.6. Reserving the Product to Intermediate Computation of a Modular
Multiplication ............................................................................................................... 94
6.5.7. Construction of Assignment Operator ......................................................... 96
6.5.8. Construction of Insertion of Zero ................................................................ 97
6.6. The Attacking Plan of Breaking the Diffie-Hellman Public-key
Cryptosystem ............................................................................................................... 98
6.7. The Example of Simulated DNA Computing .............................................. 99
6.8. Complexity Assessment ............................................................................. 128
7. Conclusions ............................................................................................................ 130
References .................................................................................................................. 132
Adleman, L. M., Braich, S. R., Johnson, C., Rothemund, Hwang, D., & Chelyapov, N.
(2002). Solution of a 20-variable 3-SAT problem on a DNA computer. Science , 296
(5567), pp. 499-502.
Adleman, M. L. (1994). Molecular computation of solutions to combinatorial
problems. Science , 266 (11), pp. 1021-1024.
Adleman, M. L. (1996). On Constucting a Molecular Computer, DNA Based
Computers. DIMACS: Series in Discrete Mathematics and Theoretical Computer
Science. , pp. 1-21.
Amos, M. (1997). DNA Computation. Ph.D. Thesis, The University of Warwick,
Department of Computer Science.
Boneh, D., Dunworth, C., & Lipton, R. J. (1995). Breaking DES using a molecular
computer. DIMACS workshop on DNA computing.
Boneh, D., Dunworth, C., Lipton, J. R., & Sgall. (1996). On the Computational Power
of DNA., 71, pp. 79-94.
Braich, S. R., Johnson, C., Rothemund, Hwang, D., Chelyapov, N., & Adleman, L. M.
(2000). Solution of a satisfiability problem on a gel-based DNA computer.
Proceedings of the 6th International Conference on DNA Computation in the
Springer-Verlag Lecture Notes in Computer Science series, (pp. 27-41).
Chang, W.-L., Guo, M., & Ho, M. (2005). Fast Parallel Molecular Algorithms for
DNA-Based Computation: Factoring Integers. IEEE Transactions on Nanobioscience ,
4 (1).
Chang, W.-L., Ho, M., & Guo, M. (2004, 2). Molecular Solutions for the Subset-sum
Problem on DNA-based Supercomputing. Journal of BioSystems , 73 (2), pp.
133
117-130.
Clark, D. P., & Russell, L. D. (2000). Molecular Biology (2nd ed.). Cache River Press.
Csuhaj-Varjú, E., Freund, R., Kari, L., & Păun, G. (1996). DNA computing based on
splicing: universality results. Biocomputing: Proceedings of the 1996 Pacific
Symposium. Singapore.
Diffie, W., & Hellman. (1976). Multiuser cryptographic techniques. IEEE
Transactions on Information Theory .
F, H. (1994). Graph Theory. Addison-Wesley.
Feyman, R. (1961). There''s Plenty of Room at the Bottom. Minaturization , pp.
282-296.
Ho, M. (2005, 6). Fast parallel molecular solutions for DNA-based supercomputing:
the subset-product problem. Journal of BioSystems , 80/3, pp. 233-250.
Huang, R. (2008). 生物資訊邏輯運算:使用疏水-親水格子模組作蛋白質結構最佳
化預測. working paper.
Jean-Michel, C., & Cedric, N. (2007). Bioinformatics for Dummies (2 ed.). Wiley
Publishing.
Koblitz. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.
Lipton. (1995). DNA solution of hard computational problems. Science , 268 (5210),
pp. 542 - 545.
Lipton, R. J. (1995). DNA Solution of Hard Computational Problems. Science , 268,
pp. 542-545.
Maurer, U. (1994). Towards the equivalence of breaking the Diffie-Hellman protocol
and computing discrete logarithms. Advances in Cryptology - Crypto (pp. 271-281).
Springer-Verlag.
Paun, G., Rozenberg, G., & Salomaa, A. (1998). DNA Computing: New Computing
Paradigms. Berlin/New York: Springer.
134
Rivest, L. R., Shamir, A., & Adleman, L. (1978). A method for obtaining digital
signatures and public-key cryptosystem. Communication of the ACM , 21, pp.
120-126.
Roweis, S., Winfree, E., Burgoyne, R., Chelyapov, N. V., Goodman, M. F.,
Rothemund, P. W., et al. (1999). A Sticker Based Model for DNA Computation.
DIMACS: Series in Discrete Mathematics and Theoretical Computer Science (pp.
1-29). Second Annual Workshop on DNA Computing, Princeton University.
Sinden, R. R. (1994). DNA Structure and Function. Academic Press.
Skiena. (1997). Clique and Independent Set. In The Algorithm Design Manual (p.
144). New York: Springer-Verlag.
Watson, J. D., Caudy, A. A., Myers, R. M., & Witkowski, J. A. (1992). Recombinant
DNA (2 ed.). New York: Scientific American Books.
Watson, J. D., Hopkins, N., Roberts, J. W., Steitz, J. A., & Weiner, A. M. (1985).
Molecular Biology of the Gene (4 ed.). Menlo Park, CA: Benjamin/Cummings.
William, S. (2004). Network Security Essentials: Applications and Standards (2 ed.).
Prentice Hall.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top