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

詳目顯示:::

: 
twitterline
研究生:許雁筑
研究生(外文):Yen-Chu Hsu
論文名稱:結合疊代修正之混合式多重結構排比演算法
論文名稱(外文):A Hybrid Multiple Structure Alignment Algorithm with Iterative Refinement
指導教授:白敦文
指導教授(外文):Tun-Wen Pai
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:56
中文關鍵詞:多重結構排比蛋白質結構比對動態規劃疊代修正演算法
外文關鍵詞:multiple structure alignmentprotein structure comparisondynamic programmingiterative refinement algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:121
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
蛋白質結構的構型是決定其功能的重要關鍵因素,若多個蛋白質擁有共同的折疊構型極可能會具有相似的功能,藉由此項重要特性及與日俱增的蛋白質結構數量,一個快速且精確的多重結構排比工具也變得更加重要。目前已經有許多工具使用不同的切入觀點來分析這個研究課題,但是這些工具所產生的多重排比結果尚未達到最佳解,仍然可透過位移與旋轉的微調得到更精確的排比結果。在本論文中,我們建構了一個疊代修正演算法來增進多重蛋白質排比的疊合品質。利用反覆更新參考錨點及自動調整適當的距離門檻值,在保持原先結構疊合的相對關係下,可以進一步改善疊合品質並發現更多共同部分的結構。當使用不同工具對標準測試資料庫的排比結果為初始依據,本論文所提出的方法能夠使原先的排比結果更加精確。基於此疊代修正演算法的強韌性,本論文亦提出三個可以產生初始排比位置的引導方法,並建構一個完整的混和式多重蛋白質結構排比系統。
The structural conformation of a protein is a fundamental and important factor to determine its function, and a set of proteins sharing common structural characteristics reflect the reservation of similar functions. To discover the functional relationship among rapidly increasing number of protein tertiary structures, an efficient and effective tool for multiple protein structure alignment has become increasingly important. A number of existing algorithms solved this problem from different aspects and unfortunately, most of the superposition for multiple structures may not achieve an optimal representation at their final output stage. In this thesis, a new refinement algorithm for improving the superposition quality of multiple protein structure alignment is proposed. Through iteratively updated anchors and automatically adjustable cutoff settings, a desired root mean square deviance (RMSD) can be obtained based on any initial condition. Experiments demonstrated that the proposed algorithms improved most of initial alignments from existing tools on benchmark datasets. Furthermore, in this thesis, three novel algorithms for creating initial alignments were also designed and developed to achieve the integrity of a hybrid multiple structure alignment system.
摘要 I
Abstract II
誌謝 III
Table of Contents IV
List of Figures VI
List of Tables VIII
1. Introduction 1
2. Algorithm Overview 3
3. Algorithm Detail 6
3.1 Initial superposition guide 6
3.1.1 Sequence content in aligned SSE segments 6
3.1.2 Centroid of aligned SSEs 11
3.1.3 Local equivalent SSEs 11
Iterative dynamic programming with automatic adjustable cutoff 15
3.2 Refinement 16
4. Performance Measures 23
5. Experimental Results 25
5.1 Implementation 25
5.2 Materials 26
5.3 Protein structures for pairwise alignment tools 27
5.4 Protein structure datasets for different multiple alignment tools 28
5.5 Refinement pf pairwise cases 28
5.6 Refinement of multiple cases 30
5.6.1 Matt and POSA on Homstrad 30
5.6.1 Matt on SABmark 34
5.6.2 MUSTANG & POSA cases 37
5.6.3 IRIS case 40
6. Discussion and Conclusion 41
Reference 43
[1] Chen, Y., & Crippen, G. M. (2006). An iterative refinement algorithm for consistency based multiple structural alignment methods. Bioinformatics, 22(17), 2087-2093.
[2] Kabsch, W. (1976). A solution for the best rotation to relate two sets of vectors. Acta Crystallographica Section A, 32(5), 922-923.
[3] O'Gara, M., McCloy, K., Malone, T., & Cheng, X. (1995). Structure-based sequence alignment of three AdoMet-dependent DNA methyltransferases. Gene, 157(1-2), 135-138.
[4] Deva, T., & Krishnaswamy, S. (2001). Structure-based sequence alignment of type-II restriction endonucleases. Biochim Biophys Acta, 1544(1-2), 217-228.
[5] Kann, M. G., Thiessen, P. A., Panchenko, A. R., Schaffer, A. A., Altschul, S. F., & Bryant, S. H. (2005). A structure-based method for protein sequence alignment. Bioinformatics, 21(8), 1451-1456.
[6] Shatsky, M., Nussinov, R., & Wolfson, H. J. (2006). Optimization of multiple-sequence alignment based on multiple-structure alignment. Proteins, 62(1), 209-217.
[7] Kim, C., & Lee, B. (2007). Accuracy of structure-based sequence alignment of automatic methods. BMC Bioinformatics, 8, 355.
[8] Jewett, A. I., Huang, C. C., & Ferrin, T. E. (2003). MINRMS: an efficient algorithm for determining protein structure similarity using root-mean-squared-distance. Bioinformatics, 19(5), 625-634.
[9] Lackner, P., Koppensteiner, W. A., Sippl, M. J., & Domingues, F. S. (2000). ProSup: a refined tool for protein structure alignment. Protein Eng, 13(11), 745-752.
[10] Holm, L., & Sander, C. (1995). 3-D lookup: fast protein structure database searches at 90% reliability. Proc Int Conf Intell Syst Mol Biol, 3, 179-187.
[11] Suyama, M., Matsuo, Y., & Nishikawa, K. (1997). Comparison of protein structures using 3D profile alignment. J Mol Evol, 44 Suppl 1, S163-173.
[12] Gerstein, M., & Levitt, M. (1998). Comprehensive assessment of automatic structural alignment against a manual standard, the scop classification of proteins. Protein Sci, 7(2), 445-456.
[13] Taylor, W. R. (1999). Protein structure comparison using iterated double dynamic programming. Protein Sci, 8(3), 654-665.
[14] Kleywegt, G.J. and Jones, T.A. (1994). A super position, CCP4/ESF-EACBM Newsletter on Protein Crystallography 31, 9-14.
[15] Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol, 48(3), 443-453.
[16] Zhu, J., & Weng, Z. (2005). FAST: a novel protein structure alignment algorithm. Proteins, 58(3), 618-627.
[17] Henikoff, S., & Henikoff, J. G. (1992). Amino acid substitution matrices from protein blocks. Proc Natl Acad Sci U S A, 89(22), 10915-10919.
[18] Birzele, F., Gewehr, J. E., Csaba, G., & Zimmer, R. (2007). Vorolign--fast structural alignment using Voronoi contacts. Bioinformatics, 23(2), e205-211.
[19] Menke, M., Berger, B., & Cowen, L. (2008). Matt: local flexibility aids protein multiple structure alignment. PLoS Comput Biol, 4(1), e10.
[20] Ye, Y., & Godzik, A. (2005). Multiple flexible structure alignment using partial order graphs. Bioinformatics, 21(10), 2362-2369.
[21] Konagurthu, A. S., Whisstock, J. C., Stuckey, P. J., & Lesk, A. M. (2006). MUSTANG: a multiple structural alignment algorithm. Proteins, 64(3), 559-574.
[22] Guda, C., Scheeff, E. D., Bourne, P. E., & Shindyalov, I. N. (2001). A new algorithm for the alignment of multiple protein structures using Monte Carlo optimization. Pac Symp Biocomput, 275-286.
[23] Dror, O., Benyamini, H., Nussinov, R., & Wolfson, H. J. (2003). Multiple structural alignment by secondary structures: algorithm and applications. Protein Sci, 12(11), 2492-2507.
[24] Krissinel, E. and K. Henrick. Multiple Alignment of Protein Structures in Three Dimensions. in Computational Life Sciences: First International Symposium, CompLife. 2005. Konstanz, Germany.
[25] Shatsky, M., Nussinov, R., & Wolfson, H. J. (2004). A method for simultaneous alignment of multiple protein structures. Proteins, 56(1), 143-156.
[26] Leibowitz, N., Fligelman, Z. Y., Nussinov, R., & Wolfson, H. J. (2001). Automated multiple structure alignment and detection of a common substructural motif. Proteins, 43(3), 235-245.
[27] Ochagavia, M. E., & Wodak, S. (2004). Progressive combinatorial algorithm for multiple structural alignments: application to distantly related proteins. Proteins, 55(2), 436-454.
[28] Lupyan, D., Leo-Macias, A., & Ortiz, A. R. (2005). A new progressive-iterative algorithm for multiple structure alignment. Bioinformatics, 21(15), 3255-3263.
[29] Holm, L., & Sander, C. (1993). Protein structure comparison by alignment of distance matrices. J Mol Biol, 233(1), 123-138.
[30] Mizuguchi, K., Deane, C. M., Blundell, T. L., & Overington, J. P. (1998). HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci, 7(11), 2469-2471.
[31] Van Walle, I., Lasters, I., & Wyns, L. (2005). SABmark--a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics, 21(7), 1267-1268.
[32] Subbiah, S., Laurents, D. V., & Levitt, M. (1993). Structural similarity of DNA-binding domains of bacteriophage repressors and the globin core. Curr Biol, 3(3), 141-148.
[33] Kolodny, R., Koehl, P., & Levitt, M. (2005). Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures. J Mol Biol, 346(4), 1173-1188.
[34] Cohen, G. (1997). ALIGN: a program to superimpose protein coordinates, accounting for insertions and deletions. Journal of Applied Crystallography, 30(6), 1160-1161.
[35] Gerstein, M., & Levitt, M. (1998). Comprehensive assessment of automatic structural alignment against a manual standard, the scop classification of proteins. Protein Sci, 7(2), 445-456.
[36] Wang, X., & Snoeyink, J. (2008). Defining and computing optimum RMSD for gapped and weighted multiple-structure alignment. IEEE/ACM Trans Comput Biol Bioinform, 5(4), 525-533.
[37] X. Wang and J.S. (2006) Snoeyink, Multiple structure alignment by optimal RMSD implies that the average structure is a consensus, Proceedings of 2006 LSS Computational Systems Bioinformatics Conference, pp.79-87.
[38] Zhang, Y., & Skolnick, J. (2005). TM-align: a protein structure alignment algorithm based on the TM-score. Nucleic Acids Res, 33(7), 2302-2309.
[39] Kabsch, W., & Sander, C. (1983). Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers, 22(12), 2577-2637.
[40] DeLano, W. L. The PyMOL Molecular Graphics System. (2002). DeLano Scientific, San Carlos, CA. http://www.pymol.org.
[41] Fischer, D., Elofsson, A., Rice, D., & Eisenberg, D. (1996). Assessing the performance of fold recognition methods by means of a comprehensive benchmark. Pac Symp Biocomput, 300-318.
[42] Chandonia, J. M., Hon, G., Walker, N. S., Lo Conte, L., Koehl, P., Levitt, M., et al. (2004). The ASTRAL Compendium in 2004. Nucleic Acids Res, 32(Database issue), D189-192.
[43] Murzin, A. G., Brenner, S. E., Hubbard, T., & Chothia, C. (1995). SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol, 247(4), 536-540.
[44] Singh, A. P., & Brutlag, D. L. (1997). Hierarchical protein structure superposition using both secondary structure and atomic representations. Proc Int Conf Intell Syst Mol Biol, 5, 284-293.
[45] Wainreb, G., Haspel, N., Wolfson, H. J., & Nussinov, R. (2006). A permissive secondary structure-guided superposition tool for clustering of protein fragments toward protein structure prediction via fragment assembly. Bioinformatics, 22(11), 1343-1352.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔