跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:陳宏信
研究生(外文):Hong-Shin Chen
論文名稱:半局部配對演算法之蛋白質結構比對
論文名稱(外文):Comparisons of Semi-local Alignment Algorithms for Protein Structures
指導教授:林耀鈴
指導教授(外文):Yaw-Ling Lin
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊工程學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:60
中文關鍵詞:蛋白質結構演算法結構配對和比對rmsd最小二分配對二級結構半局部配對演算法
外文關鍵詞:structural proteomicsalgorithmsstructure alignments and comparisonsminimum bipartite matchingrmsdsecondary structuresemi-local algorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:172
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
因為蛋白質之間相似的結構允許分子之間上的辨識,所以正確的蛋白質的結構對生物功能是必要。藉由序列比對證明蛋白質之間的相似結構是無法被察覺為相同。因此比對和配對是發現蛋白質結構功能非常有效的方法,能產生直接洞察分子機制。目前,有一些技術在嘗試找出兩個蛋白質結構之間共有的最佳配對。

在此論文裡,我們提出一個藉由局部配對演算法工具在兩個蛋白質結構的炭原子之中找出配對的技術,進而發展出半局部配對演算法。這些初始配對演算法之後會藉由我們先早所提出的方法,藉由在幾何學的距離空間上利用最小二分配對的方法和根據三角級數逼近值估測等量的轉換調整策略,漸進式的找出蛋白質配對中最好配對。最後我們藉由一組實驗數據證明所提出的半局部配對演算法改善了先前方法的結果。
Protein structures are essential for correct biological functions because similar structures between proteins allow molecular recognition. Identifying similar structures between proteins provide the opportunity to recognize homology that is undetectable by sequence comparison. Thus comparison and alignment of protein structures represents a powerful means of discovering functions, yielding direct insight into the molecular mechanisms. Currently, there are several techniques available in attempting to find the optimal alignment of shared structural motifs between two proteins.

In this thesis, we propose algorithms and develop tools for local alignment between two protein structures by the technique of semi-local alignment between the carbon atoms of two proteins.

These initialized alignment algorithms are later refined by our previously proposed methods by stepwise finding better alignments of the protein pairings using minimum bipartite matching method on geometric distance space and several other adjustment strategies in estimating good isometric transformations based on trigonometric series approximation.

We show the effectiveness of the proposed semi-local alignment algorithm by a set of experiments, which improve several previous results.
Abstract ii
Contents iv
List of Tables vi
List of Figures vii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Root mean squared deviation . . . . . . . . . . . . . . . . . . 3
1.2.1 Euler''s Rotation Theorem . . . . . . . . . . . . . . . . 5
1.2.2 Minimum Bipartite Matching . . . . . . . . . . . . . . 5
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Background and Relative Works 7
2.1 VAST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 CE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Other Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Notations and Properties . . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Parametric Adjustment with Trigonometric Series . . . 13
2.5 Re¯ning Structure Alignments . . . . . . . . . . . . . . . . . . 13
2.5.1 Data Collection Method . . . . . . . . . . . . . . . . . 15
2.5.2 Method by Main Vector Alignment . . . . . . . . . . . 15
2.5.3 Initialization by segment alignment . . . . . . . . . . . 16
3 Semi-Local Alignment Algorithm 24
3.1 Method M1: On Two Directions Di®erent Penalties . . . . . . 24
3.2 Method M2: Penalty with Upper Bound . . . . . . . . . . . . 25
3.3 Semi-Local Alignment Algorithm . . . . . . . . . . . . . . . . 26
4 Experiments 28
4.1 Sources of Data . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 31
5 Implementations 38
5.1 A °ow chart of our package . . . . . . . . . . . . . . . . . . . 38
5.2 Download and Installation . . . . . . . . . . . . . . . . . . . . 39
5.3 Handy tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.4 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 Practical examples . . . . . . . . . . . . . . . . . . . . . . . . 45
6 Conclusion and Future Works 48
Bibliography 50
[1] H. M. Berman, J.Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H.Weissig, I. N. Shindyalov, and P. E. Bourne. The protein data bank. Nucleic Acids Research, 28:235-242, 2000.
[2] F. Bourgeois and J. C. Lassalle. Algorithm 415: Algorithm for the assignment problem (rectangular matrices). In Communications of the ACM, volume 14, pages 805-806, New York, NY, 1971. USA.
[3] F. Bourgeois and J. C. Lassalle. An extension of the munkres algorithm for the assignment problem to rectangular matrices. In Communications of the ACM, volume 14, pages 802-804, New York, NY, 1971. USA.
[4] J. M. Bujnicki. Phylogeny of the restriction endonuclease-like superfamily
inferred from comparison of protein structures. J Mol Evol., 50:38-44, 2000.
[5] G. Casella and I. G. Edward. Explaining the gibbs sampler. The American Statistician, 46:167-174, 1992.
[6] S. Dietmann and L. Holm. Identification of homology in protein structure classification. Nature Struct. Biol., 8:953-957, 2001.
[7] N. Echols, D. Milburn, , and M. Gerstein. Molmovdb:analysis and visualization of conformational change and structural flexibility. Nucleic Acids Res., 31:478-482, 2003.
[8] L. Euler. Formulae generales pro trandlatione quacunque corporum rigidorum. Novi Acad. Sci. Petrop., 20:189-207, 1775.
[9] Z. Galil. Effcient algorithms for finding maximum matching in graphs. ACM Computing Surveys, 18:1:23-38, 1986.
[10] M. Gerstein, R. Jansen, T. Johnson, J. Tsai, and W. Krebs. Motions in a database framework: from structure to sequence. Rigidity Theory and Applications, pages 401-442 (ed. M F Thorpe and P M Duxbury, Kluwer Academic/Plenum Publishers), 1999.
[11] J. F. Gibrat, T. Madej, and S. H. Bryant. Surprising similarities in structure comparison. Curr Opin Struct Biol, 6(3):377-385, 1996 Jun.
[12] A. Gray. A treatise on gyrostatics and rotational motion. MacMillan, London, 1918.
[13] L. Holm and C. Sander. Touring protein fold space with DALI/FSSP. Nucleic Acids Res., 26:316-319, 1998.
[14] Shih-Peng Huang, Hsiang-Sheng Shin, and Yaw-Ling Lin. Three dimensional protein structures alignments by minimum bipartite matching. In Proceedings of the 24rd Workshop on Combinatorial Mathematics and Computation Theory, pages 172-181, Nantou, Taiwan, 2007.
[15] M. S. Johnson, M. J. Sutcliffe, and T. L. Blundell. Molecular anatomy: Phyletic relationships derived from three-dimensional structures of proteins. J Mol Evol., 30:43-59, 1990.
[16] Y. L. Lin and S. P. Huang. Tools and algorithms for refined comparison of protein structures. In The 6th WSEAS International Conference on Microelectronics, Nanoelectronics, Optoelectronics (MINO ''07), Istanbul, Turkey, 2007.
[17] Y. L. Lin, Y. H. Lin, P. S. Yu, and H. C. Chang. Randomized algorithms for three dimensional protein structures alignment. The 6th International Symposium on Computational Biology and Genome Informatics., pages 122-125, 2005.
[18] A. C. R. Martin. http://www.bioinf.org.uk/software/profit/.
[19] A. D. McLachlan. Rapid comparison of protein structures. Acta Cryst, A38:871-873, 1982.
[20] J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5:32-38, 1957.
[21] A. G. Murzin, S. E. Brenner, T. Hubbard, and C. Chothia. Scop: a structural classification of proteins database for the investigation of sequences and structures. J Mol. Biol., 247:536-540, 1995.
[22] H. Ohkawa, J. Ostell, and S. Bryant. Mmdb: an asn.1 specification for macromolecular structure. Proc. Int. Conf. Intell. Syst. Mol. Biol, 3:259-267, 1995.
[23] C. A. Orengo, A. D. Michie, S. Jones, D. T. Jones, M. B. Swindells, and J. M. Thornton. Cath - a hierarchical classification of protein domain structures. Structure, 5:1093-1108, 1997.
[24] R. A. Pilgrim. http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html.
[25] J. T. Schwartz and M. Sharir. Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves. Int. J. Robotics Research, 6:29-44, 1987.
[26] H. S. Shin, S. P. Huang, and Y. L. Lin. Parametric searching algorithms with adaptive strategy for three dimensional protein structures alignments. In National Computer Symposium (NCS''2007), pages 144-154, Taichung, Taiwan, 2007.
[27] H. S. Shin, Y. L. Lin, and W. D. Jiang. Protein structures alignment algorithms by parametric searching with trigonometric series. In Proceedings of the 25th Workshop on Combinatorial Mathematics and Computation Theory, pages 44-54, Hsinchu, Taiwan, 2008.
[28] I. N. Shindyalov and P. E. Bourne. Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng., 11:739-747, 1998.
[29] M. S. Waterman and T. F. Smith. Identification of common molecular subsequences. J. Mol. Biol., 147:195-197, 1981.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊