跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃俊瑜
研究生(外文):Chun-Yu Huang
論文名稱:生物資訊邏輯運算:使用疏水-親水格子模組作蛋白質結構最佳化預測
論文名稱(外文):Bioinformatics Logic Computing: Using the HP Lattice Model for Protein Structure Optimal Prediction
指導教授:何善輝
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:175
中文關鍵詞:蛋白質摺疊疏水-親水格子模組邏輯生物閘操作生物計算生物分子計算
外文關鍵詞:The hydrophobic-hydrophilic modelProtein FoldingBio-molecular computingLogic Bio-circuit operationsDNA-based computing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:146
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
任何蛋白質皆可以視為一條胺基酸鏈,當特定條件下可以折疊成二維或是三維結構(Zimmermann 2003)。基於熱力學假說,一個蛋白質的原生結構總是達到整體最小的自由能。疏水-親水格子模組(Hydrophobic-Hydrophilic lattice model) (Dill 1985) 對於預測蛋白質原生結構是較成功且最被研究的模型。但用疏水-親水格子模組解決蛋白質折疊問題是被證明成NP-complete 問題(Crescenzi et al. 1998)。這篇論文提出一個基於生物基本邏輯操作的新型進步且最佳化的生物分子計算模型,並且去解決在疏水-親水格子模組的蛋白質摺疊問題,此問題包括了二維和三維結構預測問題。為了達成目的,我們提出聰明的DNA演算法去產生所有可能的結構並且計算所有可能結構的整體最小自由能,找出擁有最大數量的鬆散接觸的結構。蛋白質擁有較多數量的鬆散接觸,則其擁有較少的自由能。
新型進步且非常聰明的平行DNA演算法主要透過生物資訊邏輯計算上疏水-親水格子模組的使用,來解決蛋白質二維和三維結構預測問題。
Any protein is regarded as a linear chain of amino acid. Under some specific conditions it folds into unique native two-dimensional and three-dimensional structures(Zimmermann 2003). Based upon thermodynamical hypothesis, the native structure of any protein should always achieve its global minimum of free energy. The hydrophobic-hydrophilic model (Dill 1985) for predicting the native structure of a protein is perhaps one of the most successful and best-studied models. The protein folding problem (Crescenzi et al. 1998) in the hydrophobic-hydrophilic model has been proved as a NP-complete problem. This thesis proposed a comprehensive newly developed and optimized bio-logic molecular computing model to solve the protein folding problem in the hydrophobic-hydrophilic model, including two-dimensional and three-dimensional structure respectively. In this research, the intelligent DNA algorithms are proposed to generate all of possible conformation spaces and compute their corresponding global minimum energy of all possible spaces to find the maximum number of loose contacts. Any protein structure has the more number of loose contacts, and then has the lower free energy.
These newly developed and very intelligent parallel DNA algorithms are used for 2D and 3D protein structure optimal predictions using the HP lattice model on bioinformatics logic computing.
中文摘要 i
英文摘要 ii
致謝 iii
Table viii
Figure ix
1. Introduction 1
1.1. Background and Motivation 1
1.2. Protein Structure Prediction 2
2. Literature Review 4
2.1. DNA 4
2.2. Adleman’s Experiment for Solution of the Hamiltonian Path Problem 5
2.3. DNA Model of Computation 8
2.4. Other research about DNA Model of Computation 9
3. The Optimization of the Boolean Bio-circuit Operations and Shifters 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 13
3.2. OR Operation on Bio-molecular Computing 15
3.2.1. Construction for the Parallel OR Operation of a Bit on Bio-molecular Computing 15
3.2.2. Construction for the Parallel OR Operation of N Bits on Bio-molecular Computing 17
3.3. AND Operation on Bio-molecular Computing 18
3.3.1. Construction for the Parallel AND Operation of a Bit on Bio-molecular Computing 19
3.3.2. Construction for the Parallel AND Operation of N Bits on Bio-molecular Computing 21
3.4. NOR Operation on Bio-molecular Computing 22
3.4.1. Construction for the Parallel NOR Operation of a Bit on Bio-molecular Computing 23
3.4.2. Construction for the Parallel NOR Operation of N Bits on Bio-molecular Computing 25
3.5. NAND Operation on Bio-molecular Computing 26
3.5.1. Construction for the Parallel NAND Operation of a Bit on Bio-molecular Computing 26
3.5.2. Construction for the Parallel NAND Operation of N Bits on Bio-molecular Computing 29
3.6. Exclusive-OR Operation on Bio-molecular Computing 30
3.6.1. Construction for the Parallel XOR Operation of a Bit on Bio-molecular Computing 30
3.6.2. Construction for the Parallel XOR Operation of N Bits on Bio-molecular Computing 32
3.7. Exclusive-NOR Operation on Bio-molecular Computing 34
3.7.1. The Construction for the Parallel XNOR Operation of a Bit on Bio-molecular Computing 34
3.7.2. Construction for the Parallel XNOR Operation of N Bits on Bio-molecular Computing 36
3.8. Left Shifters Operation on Bio-molecular Computing 38
3.8.1. The Construction for the Parallel Left Shifter of N Bits on Bio-molecular Computing 39
3.8.2. The Construction for the Parallel Left Shifter on Bio-molecular Computing 41
3.9. Right Shifters Operation on Bio-molecular Computing 42
3.9.1. The Construction for the Parallel Right Shifter of a Bit on Bio-molecular Computing 43
3.9.2. The Construction for the Parallel Right Shifter of N Bits on Bio-molecular Computing 45
4. DNA Algorithms Based on the DNA Model for Constructing Parallel Subtractor and Divider 47
4.1. The Construction of a Parallel One-bit Subtractor 47
4.2. The Construction of a Parallel N-bit Subtractor 49
4.2.1. Generation of DNA Strands for the Input Operands of Parallel N-bit Subtractor 49
4.2.2. DNA Algorithms for Constructing Bio-molecular Parallel Subtractor with Basic Logic Operations 51
4.3. The Construction of a Parallel Divider 53
4.3.1. Generation of DNA Strands for the Input Operands of Parallel N-bit Divider 53
4.3.2. DNA Algorithms for Constructing Bio-molecular Parallel Read-Remainder with Basic Logic Operations 55
4.3.3. DNA Algorithms for Constructing Bio-molecular Parallel Divider with Basic Logic Operations 56
5. Protein Predicting Problem 61
5.1. The Introduction for Protein 61
5.2. Different Levels of Protein Structure 62
5.3. Protein Folding 66
5.4. The Introduction to the Hydrophobic-hydrophilic Model 69
5.5. Mutation on the Absolute or Relative Encoding in the HP Model 73
5.6. Frame of the Predication for Conformations for Proteins on DNA Algorithms Based 75
6. Two Dimensional Protein Structure Prediction using the HP Lattice Model on Optimal Bioinformatics Logic Computing 77
6.1. The Construction for Molecular Solution to a Protein in the Hydrophobic-hydrophilic Model 78
6.2. The Construction for Molecular Solution to the Origin of the Coordinates in a Two-dimensional Lattice 79
6.2.1. The Construction of Parallel Adders of n Bits 83
6.2.2. The Construction of Parallel Subtractor of n Bits 86
6.2.3. The Construction of Parallel Assignment Operators 88
6.3. The Construction for Conformational Space to a Protein in the Hydrophobic-hydrophilic Model in a Two-dimensional Lattice 90
6.4. Compute the Global Minimum Energy from Conformation Space 94
6.4.1. Compute the Number of Loose Contact from Conformation Space 96
6.4.2. Find Loose Contact from Conformation Space 99
6.4.3. Judge Whether Adjacent Positions are Loose Contact 104
6.4.4. A Parallel Comparator for Coordinate Values of Adjacent Positions to Conformation Space 107
6.5. Find Global Minimum Energy 109
6.6. Intelligent DNA Algorithms for Finding Conformation of a Protein with Global Minimum Energy in the Hydrophobic-hydrophilic Model in a Two-dimensional Lattice 111
7. Three Dimensional Protein Structure Prediction using the HP Lattice Model on Optimal Bioinformatics Logic Computing 122
7.1. The Construction for Molecular Solution to a Protein in the Hydrophobic-hydrophilic Model 123
7.2. the Construction for Molecular Solution to the Origin of the Coordinates in a Three-dimensional Lattice 125
7.3. The Construction for Conformational Space to a Protein in the Hydrophobic-hydrophilic Model in a Three-dimensional Lattice 130
7.4. Compute the Global Minimum Energy from Conformation Space in the hydrophobic-hydrophilic model in a three-dimensional lattice 138
7.4.1. Compute the Number of Loose Contact from Conformation Space 140
7.4.2. Find Loose Contact from Conformation Space 145
7.4.3. Judge Whether Adjacent Positions are Loose Contact 151
7.4.4. A Parallel Comparator for Coordinate Values of Adjacent Positions to Conformation Space 155
7.5. Find Global Minimum Energy in the hydrophobic-hydrophilic model in a three-dimensional lattice 157
7.6. Intelligent Parallel DNA algorithm for 3D Protein Structure Prediction using the Hydrophobic-hydrophilic Lattice Model on Optimal Bioinformatics Logic Computing 159
8. Conclusions 162
References 163
A. Nayak, A.S.a.U.Z. "Spatial codes and the hardness of string folding problems," Symposium on Discrete Algorithms archive Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms table of contents) 1998, pp pp. 639 - 648.
Adleman, L. "Molecular computation of solutions to combinatorial problems," Science (266:Nov) 1994, pp 1021-1024.
Berger, B., and Leighton, T. "Protein folding I nthe hydrophobic-hydrophilic(HP) model is NP-complete," Journal of Computational Biology (5:1) 1998, pp 27-40.
Braich, R.S., Johnson, C., Rothemund, P.W.K., Hwang, D., Chelyapov, N., and Adleman, L.M. "Solution of a satisfiability problem on a gel-based DNA computer," 6th International Conference on DNA Computation in the Springer-Verlag Lecture Notes in Computer Science series, 2001.
Braich, R.S., Johnson, C., Rothemund, P.W.K., Hwang, D., Chelyapov, N., and Adleman, L.M. "Solution of a 20-variable 3-SAT problem on a DNA computer," Science (296:5567), April 2002, pp 499-502.
Chang, W.-L., Guo, M., and Ho, M. "Towards solution of the set-splitting problem on gel-based DNA computing," Future Generation Computer Systems (20:5), June 15 2004a, pp 875-885.
Chang, W.-L., Ho, M., and Guo, M. "Molecular solutions for the subset-sum problem on DNA-based supercomputing," BioSystems (73:2) 2004b, pp 117-130.
Chang, W.-L., Ho, M., and Guo, M. "Fast parallel molecular algorithms for DNA-based computation: factoring integers," IEEE Transactions on Nanobioscience (4:2) 2005, pp 149-163.
Chang, W.L., Ho, M., and Guo, M. "Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing," Parallel Computing (Elsevier Science) (30:9 & 10) 2004c, pp 1109-1125.
Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., and Yannakakis., M. "On the Complexity of Protein Folding," Journal of Computational Biology (5:3) 1998, pp 409-422.
Dill, K.A. "Theory for the Folding and Stability of Globular Proteins," Biochemistry (24) 1985, pp 1501-1506.
Dill, K.A. "Dominant Forces in Protein Folding," Biochemistry (29) 1990, pp 7133-7155.
Dill, K.A., Bromberg, S., Yue, K., Fiebig, K.M., D.P. Yee, P.D.T., and Chan, H.S. "Principles of Protein Folding: a Perspective from Simple Exact Models," Protein Science (4) 1995, pp 561-602.
Feynman, R.P. "In minaturizatio," Reinhold Publishing Corporation, pp. 282-296.
Ho, M.S.-H. "Fast parallel molecular solutions for DNA-based supercomputing : the subset-product problem," BioSystems (80:3) 2005, pp 233-250.
Istrail, W.E.H.a.S. "Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal," Journal of Computational Biology (3) 1996, pp pp. 53-96.
Istrail, W.E.H.a.S. "Lattice and off-lattice side chain models of protein folding: linear time structure prediction better than 86% of optimal," Journal of Computational Biology (4) 1997, pp pp. 241-259.
J. Setubal, J.M. "Introduction to Computational Molecular Biology," PWS Publishing Company (second ed:Boston) 1997.
Lipton, R.J. "DNA solution of hard computational problems," Science (268:) 1995, pp 542-545.
Moult, R.U.a.J. "Finding the lowest free energy conformation of a protein is an NP-hard problem proof and implications," Bulletin of Mathematical Biology (55) 1993, pp pp. 1183-1198.
Paun, G., Rozenberg, G., and Salomaa, A. "DNA Computing: New Computing Paradigms," New York, 1998.
Quyang, Q., Kaplan, P.D., Liu, S., and Libchaber, A. "DNA solution of the maximal clique problem," Science (278) 1997, pp 446-449.
Roweis, S., Winferr, E., Burgoyne, R., Chelyapov, N.V., Goodman, M.F., Rothemund, P.W.K., and Adleman, L.M. "A sticker based model for DNA computation," in: DIMACS series in Discrete Mathematics and Theoretical Computer Science, L. Landweber and E. Baum (eds.), 1999, pp. 1-29.
Siew, N., and Fischer, D. "Convergent evolution of protein structure prediction and computer chess tournaments: CASP, Kasparov, and CAFASP," IBM Systems Journal (40) 2001.
Sinden, R.R. "DNA Structure and Function," New York: Academic, 1994.
Wold, M.S. "Principles of Protein Structure," Biochem (34) 2001.
Zimmermann, K.-H. "An Introduction to Protein Informatics," Kluwer Academic Publisher) 2003.
王郁仁 "生物資訊邏輯系統加法器乘法器架構:最大權重Clique及離散對數問題分子計算最佳化," in: IM, MCU, working paper.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top