跳到主要內容

臺灣博碩士論文加值系統

(44.192.94.177) 您好!臺灣時間:2024/07/21 18:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林約丞
研究生(外文):Yue-ChengLin
論文名稱:求解三維HP模型蛋白質摺疊問題之新分支界定法
論文名稱(外文):A New Branch and Bound Method for the Protein Folding Problem in the 3D HP Model
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:醫學資訊研究所
學門:醫藥衛生學門
學類:醫學技術及檢驗學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:43
中文關鍵詞:生物資訊學分支界定法計算生物學HP模型蛋白質摺疊問題
外文關鍵詞:Bioinformaticsbranch and boundcomputational biologyHP modelthe protein folding problem
相關次數:
  • 被引用被引用:0
  • 點閱點閱:269
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在計算生物學中有一個非常重要之議題,即由胺基酸序列預測其蛋白質摺疊結構,蛋白質摺疊的問題是一個基本問題存在於計算分子生物學和生物化學的物理當中。在這份論文中,我們發展一個新的分支界定方法,並且設定潛能分數做為動態門檻,為蛋白質摺疊的問題在三維HP模型之節省相當多的收尋空間。
先前知道使用在為蛋白質摺疊的問題上的方法可從基準序列找到最優選或次優選的能量結構,但總計算時間是相當長的因為通常它需要跑很多模擬測試否則就會缺乏準確性。而我們的方法是一個動態系統和彈性地被實施的一個方法並且只需跑一次模擬時間。
One of the most important open problems in computational biology is the prediction of the conformation of a protein based on its amino acid sequence. The protein folding problem is a fundamental problem in bioinformatics and biochemical physics. We design a new branch and bound method for protein folding problem, and define a new potential score function as the dynamic threshold which can be efficiently used to prune the search space. The previously known method for the protein folding problem may find 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. Moreover, our method is a dynamical system and flexibly implemented for the protein folding problem, and it only need run once time.
1 Introduction 1
1.1 Heuristics and purpose . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Preparation for work . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Bioinoformatics Background 4
2.1 Amino acids and interactions with proteins . . . . . . . . . . . . . . 4
2.2 Structure of proteins . . . . . . . . . . . . . . . . . . . . . . . . .6
2.3 Relationship between folding and amino acid sequence . . . . . . . . . 10
2.4 Protein folding . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
2.5 HP model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Related Methods 15
3.1 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Ant colony optimization algorithm . . . . . . . . . . . . . . . . . . .16
4 Preliminaries 19
5 Our Algorithm 26
5.1 Dynamic threshold . . . . . . . . . . . . . . . . . . . . . . . . . . .27
5.1.1 r-step checking . . . . . . . . . . . . . . . . . . . . . . . . . . .29
5.1.2 The New Branch and Bound Algorithm . . . . . . . . . . . . . . . . . 29
6 Experimental Results 32
7 Concluding Remarks 39
8 Bibliography 40
[1] U. Bastolla, H. Fravenkron, E. Gestner, P. Grassberger, and W. Nadler, Testing a new Monte Carlo algorithm for the protein folding problem, Proteins, vol. 32, pp. 52-66. 1998.
[2] 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.
[3] 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.
[4] M. Chen and W. Q. Huang, A branch and bound algorithm for the protein fold- ing problem in the hp lattice model, Genomics, Proteomics and Bioinformatics, vol. 3, pp. 4, 2005.
[5] F. Custdio, H. Barbosa, and L. Dardenne, Investigation of the three- dimensional lattice HP protein folding model using a genetic algorithm, Genetics and Molecular Biology, Vol. 27, No. 4, pp. 611- 615, 2004.
[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, No. 6, pp. 1501-1509, 1985.
[8] 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.
[9] Dill KA, Fiebig KM, Chan HS: Cooperativity in Protein-Folding Kinetics . Proc Natl Acad Sci USA, vol90 ,pp.1942-1946, 1993.
[10] 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.
[11] Beutler T., K. Dill, A Fast conformational Method: A New Algorithm for Protein Folding Simulations, Protein Sci.,vol. 5, pp.147-153 , 1996.
[12] C. M. Dobson, The nature and signi?cance of protein folding, Mechanisms of Protein Folding, vol. 2, 2000.
[13] M. Dorigo, Optimization, Learning and Natural Algorithms. PhD thesis, Politec- nico di Milano, Italy, 1992.
[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 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.
[16] M. Dorigo and T. Stutzle, Ant colony optimization, MIT press, 2004.
[17] Kaizhi,Ken A.Dill. Forces of tertiary structural organizaton in globular protein . Proc. Natl. Acad. Sci. USA., vol.92 , pp. 146-150, 2005
[18] R.C. Eberhart, and J. Kennedy, Particle swarm optimization, Proceedings of the IEEE International Conference of Neural Networks, pp. 1942-1948, 1995.
[19] A. Fulton and W. Isaacs, Titin, a huge, elastic sarcomeric protein with a probable role in morphogenesis, Bioessays, vol. 13, pp. 157, 1991.
[20] 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. 10600-10603, 1996.
[21] D. Gidalevitz, Z. Huang, and S. A. Rice, Protein folding at the air-water interface studied with x-ray reXectivity, Proceedings of the National Academy of Sciences of the United States of America, vol. 96, pp. 2608-2611, 1999.
[22] Graham A. Cox, Thomas V. Mortimer-Jones, Robert P. Taylor, Roy L. Johnston, De- velopment and optimization of a noval genetic algorithm for studying model protein folding, Theor Chem Acc vol.112, pp. 163- 178, 2004.
[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] H.P. Hsu, V. Mehra, W. Nadler, and P. Grassberger, Growth algorithm for lattice heteropolymers at low temperatures, Journal of Chemical Physics, vol. 118, pp. 444- 51, 2003.
[25] S.Y Hsieh, D.W Lai ,A New Branch and Bound method for the Protein Folding Problem in the HP Model, BIOINFORMATICS ,2008
[26] Jie Song , Jiaxing Cheng and Tingting Zheng, Protein 3D HP model folding simula- tion based on ACO* , Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, vol.6, pp. 30, 2006.
[27] J. Juneja and J. B. Udgaonkar, Nmr studies of protein folding, Current science, vol. 84-2, pp. 25, 2003.
[28] Kaizhi Yue, Klaus M.Fiebig, Paul D.Thomas, Hue Sun Chan, Eugene I.Shakhnovich and Ken A.Dill. A test of lattice protein folding algorithms, . Proc. Natl. Acad. Sci. USA. , vol.92 , pp. 325-329,1995
[29] M. Kataoka and Y. Goto., X-ray solution scattering studies of protein folding, Folding and design, vol. 1, pp. 107-114, 1996.
[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. 5th ed., 2004.
[31] 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.
[32] 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.
[33] A. Newman and M. Ruhl, Combinatorial problems on strings with applications to protein folding, Proceedings of the Sixth Latin American Symposium on The- oretical Informatics(LATIN'04), pp. 369-378, 2004.
[34] A. Shmygelska, and H.H. Hoos, An ant colony optimization algorithm for the 2D and 3D hydrophobic polar protein folding problem, BMC Bioinformatics, Vol. 6, No. 30, 2005.
[35] A.R. Sikder, and A.Y. Zomaya, An overview of protein-folding techniques: issues and perspectives, International Journal of Bioinformatics Research and Applications, Vol. 1, No. 1, pp. 121-143, 2005.
[36] Toma L., S. Toma, Contact Interaction Method: A New Algorithm for Protein Folding Simulations, Protein Sci, Vol. 5,pp. 147-153 ,1996.
[37] R. Ramakrishnan, B. Ramachandran, and J.F. Pekny, A dynamic Monte Carlo al- gorithm for exploration of dense conformational spaces in heteropolymers, Journal of Chemical Physics, Vol. 106, No. 6, pp. 2418-2424, 1997.
[38] R. Unger, and J. Moult, Finding the lowest free energy conformation of a protein is an NP-Hard problem: proof and implications, Bulletin of Mathematical Biology, pp. 1183-1198, 1993.
[39] R. Unger, and J. Moult, A genetic algorithm for 3D protein folding simulations, Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 581-588, 1993.
[40] 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, pp. 225-101, 2007.
[41] X. Zhang, and T. Li, Improved particle swarm optimization algorithm for 2D protein folding prediction. Proceedings of the 1st International Conference on Bioinformatics and Biomedical Engineering, pp. 53-56, 2007.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top