跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:賴德維
研究生(外文):De-wei Lai
論文名稱:求解HP模型蛋白質摺疊問題之新分支界定法
論文名稱(外文):A New Branch and Bound Method for the Protein Folding Problem in the HP model
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:醫學資訊研究所
學門:醫藥衛生學門
學類:醫學技術及檢驗學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:51
中文關鍵詞:生物資訊學計算生物學分支界定法HP 模型蛋白質摺疊問題
外文關鍵詞:the protein folding problemHP modelcomputational biologybioinformaticsbranch and bound
相關次數:
  • 被引用被引用:0
  • 點閱點閱:172
  • 評分評分:
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:0
蛋白質摺疊的問題是一個基本問題存在於計算分子生物學和生物化學的物理當中。早先最佳知道的分支界定方法使用在為蛋白質摺疊問題上可從基準序列找到最優選或次優選的能量結構,但總計算時間是相當長的因為通常它需要跑很多模擬測試否則就會缺乏準確性。在這份論文中, 我們發展一個新的分支界定方法為蛋白質摺疊的問題在二維HP 模型之下克服被提及的缺點。
由使用基準序列作為評估, 我們可以顯示出, 我們的方法表現比早先已知的方法優越。而且, 我們的方法是一個簡單、彈性和容易地被實施的一個方法。
The protein folding problem is a fundamental problem in computational molecular biology and biochemical physics. The previously best known branch and bound method for the protein folding problem may find optimal or near-optimal energy structure from the benchmark sequences, but the total computation time is rather lengthy because it usually needs to run a great deal of simulating tests or else lack of accuracy.
In this thesis, we develop a new branch and bound method for the the protein folding problem under the two-dimensional HP model to overcome the mentioned drawbacks.
By using benchmark sequences for evaluation, we demonstrate that the performance of our method is superior than previously known methods. Moreover, our method is a
simple, flexible, and easily implemented one for the protein folding problem.
1 Introduction 1
1.1 Motivation 1
1.2 Results 2
1.3 Organization 3

2 Bioinoformatics Background and Literature Survey 4
2.1 Amino acids and Protein 4
2.2 Protein folding 6
2.3 Structure of proteins 7
2.4 HP model 11
2.5 NP-hard and NP-complete 11

3 Related Methods 15
3.1 Branch and Bound 15
3.2 Ant colony optimization algorithm 16
3.3 Genetic algorithm 18
3.4 Monte Carlo method 21

4 Preliminaries 23

5 Our Method 29
5.1 Dynamic threshold 30
5.2 R-step checking 31
5.3 Our algorithm 32

6 Experimental Results 35

7 Concluding Remarks 41

8 Availability and Supplemental Material 42
8.1 The web server 42
8.2 Submission page 43
8.3 Check and reply page 45
8.4 Result page 46
[1] B. Berger and F. T. Leighton, "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete," Journal of Computational Biology, vol. 5, pp. 27-40, 1998.

[2] H. J. Bockenhauer and D. Bongartz, "Protein folding in the HP model on gird lattices with diagonals," Discrete Appl. Match, vol. 155, pp. 230-256, 2007.

[3] C. I. Branden and J. Tooze, "Introduction to protein structure(second edition),"1998.

[4] V. Chandra, A. DattaSharma, and V. S. AnilKumar, "The algorihtmics of folding proteins on lattices," Discrete Appl. Match, vol. 127, pp. 145-161, 2003.

[5] M. Chen and W. Q. Huang, "A Branch and Bound Algorithm for the Protein Folding Problem in the HP lattice Model," Genomics, Proteomics and Bioinformatics,
vol. 3, p. 4, 2005.

[6] P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, and M. Yannakakis,"On the complexity of protein folding," Journal of Computational Biology, vol. 5,
pp. 423-465, 1998.

[7] K. A. Dill, "Theory for the folding and stability of globular proteins," Biochemistry, vol. 24, pp. 1501-1509, 1985.

[8] K. A. Dill, S. Bromberg, K. Yue, K. Fiebig, D. Yee, P. Thomas, and H. chan, "Principles of protein folding-a perspective from simple exact models," Protein
Science, vol. 4, pp. 561-602, 1995.

[9] K. A. Dill, M. Fiebig, and H. S. Chan, "Cooperativity in protein -folding kinetics," Proceedings of the National Academy of Sciences of the United States of America,
pp. 1942-1946, 1993.

[10] K. A. Dill and K. Lau, "A lattice statistical mechanics model of the conformational sequence spaces of proteins," Macromolecules, vol. 22, pp. 3986-3997, 1989.

[11] C. M. Dobson, "The nature and significance of protein folding," Mechanisms of Protein Folding, vol. 2nd ed.,
2000.

[12] M. Dorigo, "Optimization, Learning and Natural Algorithms," Ph.D. dissertation, Politecnico di Milano, Italy, 1992.

[13] M. Dorigo and L. M. Gambardella, "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.

[14] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man and Cybernetics,
vol. 26, pp. 29-41, 1996.

[15] M. Dorigo and T. Stutzle, Ant Colony Optimization. MIT Press, 2004.

[16] J. Drenth, Principles of protein X-ray crystallography. Springer, 1994.

[17] A. Fersht, Structure and mechanism in protein science: a guide to enzyme catalysis
and protein folding. Freeman, 1998.

[18] G. S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications. Springer,1995.

[19] S. M. V. Freund, K. B. Wong, and A. R. Fersht, "Initiation sites of protein folding
by NMR analysis," Proceedings of the National Academy of Sciences of the United States of America, vol. 93, pp. 10 600-10603, 1996.

[20] A. Fulton and W. Isaacs,"Titin, a huge, elastic sarcomeric protein with a probable role in morphogenesis," Bioessays, vol. 13, pp. 157-161, 1991.

[21] D. Gidalevitz, Z. Huang, and S. A. Rice, "Protein Folding at the Air-Water Interface Studied with X-ray Re°ectivity," Proceedings of the National Academy of Sciences of the United States of America, vol. 96, pp. 2608-2611, 1999.

[22] H. Gould and J. Tobochnik, An Introduction to Computer Simulation Methods,Part 2, Applications to Physical Systems. Addison wesley, 1988.

[23] W. E. Hart and S. Istrail, "Robust proofs of NP-hardness for protein folding:general lattices and energy potentials," Journal of Computational Biology,
vol. 4, pp. 1-22, 1997.

[24] W. Huang and Z. Lu, "Personification algorithm for protein folding problem: improvements in PERM," Chinese Science Bulletin, vol. 49, pp. 2092-2096, 2004.

[25] J. Juneja and J. B. Udgaonkar, "NMR studies of protein folding," Current science,vol. 84(2), p. 25, 2003.

[26] M. Kataoka and Y. Goto., "X-ray solution scattering studies of protein folding," Folding and design, vol. 1, pp. 107-114, 1996.

[27] G. KjellstrÄom, "Evolution as a statistical optimization algorithm," Evolutionary Theory, vol. 11, pp. 105-117, 1996.

[28] H. Li, R. Helling, C. Tang, and N. Wingreen, "Emergence of Preferred Structures
in a Simple Model of Protein Folding," Science, vol. 273, pp. 666-669, 1996.

[29] F. Liang and W. H. Wong, "Evolutionary Monte carlo for protein folding simulations," Journal of Chemical Physics, vol. 115, pp. 3374-3380, 2001.

[30] H. Lodish, A. Berk, P. Matsudaira, C. A. Kaiser, M. Krieger, M. P. Scott, S. L. Zipurksy, and J. Darnell, Molecular Cell Biology, vol. 5, 2004.

[31] B. M. Matthews, "Recent transformations in structural biology," Methods in Enzymology, vol. 276, pp. 3-10, 1997.

[32] N. Metropolis and S. Ulam, "The Monte Carlo Method," Journal of the American Statistical Association, vol. 44, pp. 335-341, 1949.

[33] A. Newman, "A new algorithm for protein folding in the HP model," Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02),pp. 876-884, 2002.

[34] A. Newman and M. Ruhl, "Combinatorial problems on strings with applications to protein folding," Proceedings of the Sixth Latin American Symposium on Theoretical Informatics(LATIN'04), pp. 369-378, 2004.

[35] R. Rubinstein and D. Kroese, "Simulation and the Monte Carlo Method(second edition)," 2007.

[36] Schmitt and M. Lothar, "Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to
global optima for arbitrary fitness function under scaling," Theoretical Computer Science, vol. 310, pp. 181-231, 2004.

[37] M. L. Schmitt, "Theory of Genetic Algorithms," Theoretical Computer Science,vol. 259, pp. 1-61, 2001.

[38] A. Shmygelska and H. H. Holger, "An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem," BMC Bioinformatics,vol. 6, p. 30, 2005.

[39] R. Unger and J. Moult, "Genetic algorithms for protein folding simulations," Journal of Molecular Biology, vol. 231, pp. 75-81, 1993.

[40] D. Whitley, "A genetic algorithm tutorial," Statistics and Computing, vol. 4, pp.65-85, 1994.

[41] J. Zhang, S. C. Kou, and J. S. Liu, "Polymer strucutre optimization and simulation via a fragment re-growth Monte Carlo," Journal of Chemical Physics, vol. 126, p.225101, 2007.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top