臺灣博碩士論文加值系統

蛋白質結構是生物學家發現蛋白質功能時一個很重要的依據與利器。蛋白質結構在演化時間上經常保持穩定；有一些蛋白質雖然我們不能由序列比對中發現分子序列相似點，研究者卻能在結構中發現這些蛋白質的相似處。同時，蛋白質三度空間結構也常能帶給研究者在分子機械作用上的啟發與瞭解。目前一群不同的研究者已發展（或正在發展）一些方法及工具來對具相似結構的蛋白質做比較、分析、比對。

在此論文中我們提出一些演算法來衡量二個蛋白質結構的差異。我們也提出一些演算法來對蛋白質結構做適當的空間旋轉、平移動作；並由此來綜合、比較二個結構之差異與相似度。這些方法的優點是可以容許序列分子間在比對時可以容許序列中開任何間距、與序列鏈結方向無關，並容許自由連結點。這些方法可以完全自動化，縱使在少數幾何扭曲錯誤下仍可正確敏感地找出結構相似處。

Protein structure represents a powerful means of discovering function, because structure is well conserved over evolutionary time, and it therefore provides the opportunity to recognize homology that is undetectable by sequence comparison. Several techniques are currently available that attempt to find the optimal alignment of shared structural motifs between two proteins.

In this thesis, we propose novel algorithms for pairwise alignment of protein structures. Methods of locating suitable isometric transformations of one structure and aligning it to the other structure are addressed. Our methods allow sequence gaps of any length, reversal of chain direction, and free topological connectivity of atom sequences. Sequential connectivity can be imposed as an option. The method is fully automatic to identify structural resemblances and common structural cores accurately and sensitively, even in the presence of geometrical distortions.

Chinese Abstracti
Abstracti
Acknowledgementsii
Contentsiii
List of Tablesv
List of Figuresvi
1 Introduction1
1.1 Foreword 1
1.2 Motive and Purpose2
1.3 Background and Literature Review4
1.3.1 FSSP 4
1.3.2 DALI 5
1.3.3 STRUCTAL7
1.3.4 VAST 8
1.3.5 MINAREA 9
1.3.6 LOCK10
1.3.7 3dSEARCH 12
1.3.8 CE14
1.3.9 SCOP 16
1.3.10 CATH 16
1.3.11 LGscore2 16
1.4 Chapter Outline 17
2 Method 18
2.1 Protein (molecular) structure distances, similarities and scoring functions 20
2.2 Finding a suitable rigid transformation for matching structures 22
3 Experiments 27
3.1 Experiment Method 27
3.2 Experimental Result 28
4 Conclusion 31
4.1 Contributions 31
4.2 Future Works 32
Bibliography 33
Vita 39

[1] N. N. Alexandrov and D. Fischer. Analysis of topological and nontopological structural similarities in the pdb: new examples with oldstructures. Proteins, 25:354-365, 1996.
[2] P. J. Artymiuk, A. R. Poirrette, D. W. Rice, and P. Willett. A polymerase i palm in adenylyl cyclase? Nature, 388:33-34, 1997.
[3] D. W. Barakat and P. M. Dean. Molecular structure matching by simulated annealing, iii. the incorporation of null correspondences into the matching problem. J. Comp. Aided Mol. Design., 5:107-117, 1991.
[4] 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 Res., 28:235{242, 2000.
[5] F. C. Bernstein, T. F. Koetzle, Williams G. J. B., Meyer E. F. Jr., M. D. Brice, J. R. Rodgers, O. Kennard, T. Shimanouchi, and M. Tasumi. The protein data bank: A computer based archival file for macromolecular
structure. J. Mol. Biol., 112:535-542, 1997.
[6] S. H. Bryant, T. Madej, J. Janin, Y. Liu, A. Ruoho, G. Zhang, and Hurley J. H. A polymerase i palm in adenylyl cyclase? a reply. Nature,388:34, 1997.
[7] J. M. Bujnicki. Phylogeny of the restriction endonuclease-like superfamily inferred from comparison of protein structures. J Mol Evol., 50:38-44,2000.
[8] C. Chothia and A. M. Lesk. The relation between the divergence of sequence and structure in proteins. EMBO J., 5:823-826, 1986.
[9] G. H. Cohen. Align: A program to superimpose protein coordinates,accounting for insertions and deletions. J. Appl. Crystallogr., In press.1997.
[10] S. Cristobal, A. Zemla, D. Fischer, L. Rychlewski, and A. Elofsson. A study of quality measures for protein threading models. BMC Bioinformatics, 2:5, 2001.
[11] V. De Filippis, C. Sander, and G. Vriend. Predicting local structural changes that result from point mutations. Protein Eng., 7:1203-1208,1994.
[12] S. Dietmann and L. Holm. Identification of homology in protein structure classification. Nature Struct. Biol., 8:953-957, 2001.
[13] A. Falicov and F. E. Cohen. A surface of minimum area metric for the structural comparison of proteins. J.Mol. Biol., 258:871-892, 1996.
[14] D. Fischer, O. Bachar, R. Nussinov, and H. Wolfson. An efficient automated computer vision based technique for detection of three dimensional structural motifs in proteins. J Biomol Struct Dyn., 9:769-789.,1992.
[15] Z. Galil. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys, 18:1:23-38, 1986.
[16] M. Gerstein and M. Levitt. Using iterative dynamic programming to obtain accurate pair-wise and multiple alignments of protein structures. In Proc. Fourth Int. Conf. on Intell. Sys. for Mol. Biol. Menlo Park,CA: AAAI Press, pp 59-67, 1996.
[17] M. Gerstein and M. Levitt. Comprehensive assessment of automatic structural alignment against a manual standard, the scop classification of proteins. Protein Sci., 7:445-456, 1998.
[18] J. F. Gibrat, T. Madej, and S. H. Bryant. Surprising similarities in structure comparison. Curr Opin Struct Biol., 6:377-385, 1996.
[19] A. Godzik and J. Skolnick. Flexible algorithms for direct multiple alignment of protein structures and sequences. CABIOS, 10:587-596, 1994.
[20] H. M. Grindley, P. J. Artymuik, D. W. Rice, and P. Willett. Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol. Biol., 229:707-721,1993.
[21] L. Holm and C. Sander. 3-d lookup: Fast protein structure database searches at 90% reliability. In Proc. Third Int. Conf. on Intell. Sys. for Mol. Biol. Menlo Park, CA: AAAI Press. pp 179-187, 1995.
[22] L. Holm and C. Sander. Protein structure comparison by alignment of distance matrices. J. Mol. Biol., 233:123-138, 1993a.
[23] L. Holm and C. Sander. Structural alignment of globins, phycocyanins,and colicin. FEBS Lett., 315:301-306, 1993b.
[24] L. Holm and C. Sander. The fssp database of structurally aligned protein fold families. Nucleic Acids Res.,22:3600-3609, 1994.
[25] L. Holm and C. Sander. Mapping the protein universe. Science, 273:595-602, 1996a.
[26] L. Holm and C. Sander. Alignment of three-dimensional protein structures: network server for database searching. Methods Enzymol.,266:653-662, 1996b.
[27] L. Holm and C. Sander. Touring protein fold space with dali/fssp. Nucleic Acids Res., 26:316-319, 1998.
[28] B. K. P. Horn. Closed-form solution of absolute orientation using unit quaternions. J. Opt. Soc. Am., 4:629-642, 1987.
[29] M. S. Johnson, M. J. Sutcli®e, and T. L. Blundell. Molecular anatomy:Phyletic relationships derived from three-dimensional structures of proteins. J Mol Evol., 30:43-59, 1990.
[30] W. Kabsch. A solution for the best rotation to relate two sets of vectors.Acta. Cryst., A32:922-923, 1976.
[31] Y. Lamdan and H. J. Wolfson. Geometric hashing: A general and efficient model based recognition scheme. In Proc. IEEE Int. Conf. on Computer Vision., pages 238-249, 1988.
[32] R. H. Lathrop. The protein threading problem with sequence amino acid interaction preferences in np-complete. Protein Eng., 7:1059-1068,1994.
[33] R. H. Lathrop and T. F. Smith. Global optimal protein threading with gapped alignment and empirical pair potentials. J. Mol. Biol., 255:641-665, 1996.
[34] M. Levitt and M. Gerstein. A unified statistical framework for sequence comparison and structure comparison. Proc Natl Acad Sci U S A., 95:5913-5920., 1998.
[35] T. Madej, J. F. Gibrat, and S. H. Bryant. Threading a database of protein cores. Proteins, 23:356-369, 1995.
[36] A. C. R Martin.ttp://www.bioinf.org.uk/software/profit/.
[37] A.D. McLachlan. Rapid comparison of protein structres. Acta Cryst,A38:871-873, 1982.
[38] K. Mehlhorn and St. Naher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.
[39] E. M. Mitchell, P. J. Artymiuk, D. W. Rice, and P. Willett. Use of techniques derived from graph theory to compare secondary structure motifs in proteins. J. Mol. Biol., 212:151-166, 1989.
[40] 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.
[41] S. B. Needleman and C. D. Wunsch. A general method applicable to the seach for similarities in the amino acid sequence of two proteins. J.Mol. Biol., 48:443-453, 1970.
[42] C. A. Orengo, D. T. Jones, and J. M. Thornton. Protein superfamilies and domain superfolds. Nature, 372:631-634, 1994.
[43] C. A. Orengo, A. D. Michie, S. Jones, D. T. Jones, M. B. Swindells, and J. M. Thornton. Cath - a hierarchical classi¯cation of protein domain structures. Structure, 5:1093-1108, 1997.
[44] C. A. Orengo and W. R. Taylor. Ssap: Sequential structure alignment program for protein structure comparison. Methods Enzymol., 266:617-635, 1996.
[45] S. T. Rao and Rossmann M. G. comparison of super-secondary structures in proteins. J. Molecular Biology, 76:241-256, 1973.
[46] R. B. Russell and G. B. Barton. Multiple protein sequence alignment from tertiary structure comparisons: Assignment of global and residue confidence levels. Proteins, 14:309-323, 1992.
[47] A. Sali and T. Blundel. Definition of general topological equivalence in protein structures: A procedure involving comparison of properties and relationships through simulated annealing and dynamic programming.
J. Mol. Biol., 212:403-428, 1990.
[48] Y. Satow, G. H. Cohen, E. A. Padlan, and D. R. Davies. Phosphocholine binding immunoglobulin fab mcpc603: An x-ray diffraction study at 2.7 a. J. Mol. Biol., 190:593-604, 1987.
[49] G. D. Schuler, J. A. Epstein, H. Ohkawa, and J. A. Kans. Entrez: Molecular biology database and retrieval system. Methods Enzymol., 266:141-162, 1996.
[50] J. T. Schwartz and M. Sharir. Identi¯cation of partially obscured objects in two and three dimensions by matching noisy characteristic curves. Int. J. Robotics Research, 6:29-44, 1987.
[51] 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.
[52] A. P. Singh and D. L. Brutlag. Hierarchical protein structure superposition using both secondary structure and atomic representations. In Proc. Fifth Int. Conf. on Intell. Sys. for Mol. Biol. Menlo Park, CA: AAAI Press. pp 284-293, 1997.
[53] T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. J. Mol. Biol., 147:195-197, 1970.
[54] S. Subbiah, D. V. Laurents, and M. Levitt. Structural similarity of dnabinding domains of bacteriophage repressors and the globin core. Curr. Biol., 3:141-148, 1993.
[55] W. Taylor and C. Orengo. Protein structure alignment. J. Mol. Biol., 208:1-22, 1989.
[56] S. Umeyama. Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI,, 13:376-380, 1991.
[57] G. Vriend and C. Sander. Detection of common 3-d substructures in proteins. Proteins, 11:52-58, 1991.
[58] M. Zuker and R. L. Somorjai. The alignment of protein structures in three dimensions. Bull. Math. Biol., 51:55-78, 1989.