臺灣博碩士論文加值系統

在生命體中，因為有各種不同的蛋白質具有特定的性質和功能，生物體內的各種活動與反應才得以發生。蛋白質的生化功能與其結構、折疊動力過程有密不可分的關係。由蛋白質的一級結構預測其三維空間結構，並進一步決定其生化功能，向來是在生命科學研究中極為重要的課題。精確地預測蛋白質結構可加速相關研究的進行，然而，要取得蛋白質的真實結構並不容易。本論文的研究目標是針對兩條十分相似的胺基酸序列，利用一個結構為已知的蛋白質分子(如已存在蛋白質資料庫PDB的蛋白質結構)，來預測另一個序列之蛋白質結構。
在之前的研究中，有許多的摺疊演算法被提出來解決蛋白質結構預測問題，像是U-fold 以及 S-fold。但是，這些摺疊演算法是設計在晶格模型上，其所預測的構型與實際情況差異頗大。因此，我們使用像是B-splines曲線吻合的技巧將晶格模型上的結構與真實狀況下的結構互相轉換。而使用曲線較準的方法，同樣可以使用在評估兩個結構的相似度。從我們實驗結果得知，當兩個蛋白質序列相似度不高時，我們的預測方法有較佳的結果。

Various proteins with specific properties and functions exist in organisms, they
perform all important biochemical activities. The biochemical functions of proteins
are determined by their structures. One of the most important issues in the life
science is to predict the three-dimensional structures with protein sequences, and
then to deduce their biochemical functions. To predict protein structure precisely
will accelerate biochemical research. However, it is a challenge task to obtain the real
structure of a protein. The objective of this study is to develop a protein structure
prediction methodology based on a structure-known protein (such as the proteins
in the PDB database), where the two protein sequences are extremely similar.
Some folding algorithms, such as U-fold and S-fold, have been developed to
predict protein structures. However, the folding algorithms work on a grid lattice,
which is very different from the real structure of a protein. Here we use the curve
fitting technique, such as B-splines, to convert the lattice model and a real structure
to the same domain, that is, the curve. We therefore perform curve (structure)
alignment on them. The curve alignment can also be used to evaluate the similarity
between two structures. By the experimental results, our protein structure prediction
method performs well when we get two protein sequences with similarity that
is not too high.

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 The Hydrophobic-hydrophilic Model . . . . . . . . . . . . . . . . . . 4
2.2 Homology Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Sequence Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 3. Structure Prediction in the HP Model . . . . . . . . . . . 11
3.1 Analysis of the HPmodel . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 The U-fold Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 The S-fold Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 The C-fold Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.5 The Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Chapter 4. Structure Alignment by Curve Fitting . . . . . . . . . . . 24
4.1 Previous Structure Alignment Algorithms . . . . . . . . . . . . . . . 24
4.1.1 RootMean Square Deviation . . . . . . . . . . . . . . . . . . 24
4.1.2 MaxSub . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Spline Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1 The B-Spline Curve . . . . . . . . . . . . . . . . . . . . . . . . 27
Page
4.3 CurveMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Chapter 5. A Prediction Method Based on curve Alignment . . . . 30
Chapter 6. Experimental Results . . . . . . . . . . . . . . . . . . . . . . 39
Chapter 7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

[1] R. Agarwala, S. Batzoglou, and V. Dancik, “Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model,” Journal of Computational Biology, Vol. 4, No. 3, pp. 275—296, 1997.[2] T. Akutsu and H. Arimura, “On approximation algorithms for local multiplealignment,” Proceedings of the Fourth Annual International Conference onComputational Molecular Biology, Tokyo, Japan, pp. 1—7, 2000.[3] D. Beasley, D. Bull, and R. Martin, “An overview of genetic algorithms: Part2, research topics,” University Computing, Vol. 15, No. 4, pp. 170—181, 1993.[4] B. Berger and T. Leight, “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.,” Journal of Computational Biology, Vol. 5, No. 1,pp. 27—40, 1998.[5] T. L. Blundell, B. L. Sibanda, M. J. E. Sternberg, and J. M. Thornton,“Knowledge-based prediction of protein structures and the design of novelmolecules.,” Nature, Vol. 326, pp. 347—352, 1987.[6] T. Creighton, “The protein folding problem,” Science, Vol. 240, pp. 267— 344,1988.[7] P. Crescenzi, D. Goldman, C. Capadimitriou, A. Piccolboni, and M. Yannakakis,“On the complexity of protein folding,” Journal of ComputationalBiology, Vol. 5, No. 1, pp. 409—422, 1998.[8] M. O. Dayho, W. C. Barker, and L. T. Hunt, “Establishing homologies inprotein sequences.,” Journal Meth Enzymol., Vol. 91, pp. 524—545, 1983.[9] K. Dill, “Theory for the folding and stability of globular proteins,” Biochemistry, Vol. 24, p. 1501, 1985.[10] G. Farin, Curves and Surfaces for Computer Aided Geometric Design : A Practical Guide. Boston: Academic Press, second ed., 1990.[11] A. Fraenkel, “Complexity of protein folding,” Bulletin of Mathematical Biology, pp. 1199—1210, 1993.[12] C. F. Gerald and P. O. Wheatley, Applied Numerical Analysis. Addison WesleyPublishing, fourth ed., 1990.[13] D. Goldberg, Genetic Algorithms. Addison Wesley Publishing, rst ed., 1988.[14] H. Hagen, Curves and Surfaces Design. SIAM Activity Group on GeometricDesign, 1992.[15] W. Hart and S. Istrail, “Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal,” Journal of Computational Biology,Vol. 3, No. 1, pp. 53—96, 1996.[16] W. Hart and S. Istrail, “Lattice and o-lattice side chain models of protein folding: Linear time structure prediction better than 86% of optimal,” Journal of Computational Biology, Vol. 4, No. 3, pp. 241—259, 1997.[17] W. Hart and S. Istrail, “Robust proofs of NP-hardness for protein folding: general lattices and energy potentials,” Journal of Computational Biology, Vol. 4, No. 1, pp. 1—22, 1997.[18] M. Hilbert, G. Bohm, and R. Jaenicke, “Structural relationships of homologous proteins as a fundamental principle in homology modeling,” Proteins, Vol. 17, No. 2, pp. 138—151, 1993.[19] J. Holland, “Adaptation in natural and articial system.” Technical Report. The University of Michigan Press, USA, 1975.[20] L. Holm and C. Sander, “3-D lookup: fast protein structure database seaches at 90 reliability.,” Proceedings of 3rd International Conference on Intelligent Systems for Molecular Biology., Cambridge, UK., pp. 179—187, 1995.[21] M. S. Johnson, N. Srinivasan, R. Sowdhamini, and T. L. Blundell, “Knowledgebased protein modeling.,” Critical Reviews in Biochemistry and Molecular Biology, Vol. 29, pp. 1—68, 1994.[22] N. Krasnogor, W. E. Hart, J. Smith, and D. A. Pelta, “Protein structure prediction with evolutionary algorithms.,” Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, USA, 1999.[23] P. Lancaster and K. Salkauskas, Curves and Surfaces Fitting. Landon: Edmundsbury Press., third ed., 1990.[24] R. C. T. Lee, “Computational biology.” http://www.csie.ncnu.edu.tw/, Department of Computer Science and Information Engineering, National Chi-NanUniversity, Taiwan, 2001.[25] R. Lewin, “When does homology mean something else?,” Science, Vol. 237,p. 1570, 1987.[26] G. Mauri, A. Piccolboni, and G. Pavesi, “Approximation algorithms for protein folding prediction.,” Proceedings of the 10th Annual Symposium on Discrete Algorithms (SODA), San Antonio, USA, pp. 945—946, 1999.[27] S. Needleman and C. Wunsch, “A general method applicable to the search forsimilarities in the amino acid sequence of two proteins,” Journal of MolecularBiology, Vol. 48, pp. 442—453, 1970.[28] A. Patton, W. P. III, and E. Goodman, “A standard ga approach to nativeprotein structure prediction,” Proceedings of 6th International Conference OnGenetic Algorithm, Dublin, Ireland, pp. 574—581, 1995.[29] S. T. Rao and M. G. Rossmann, “Comparison of super-secondary structures inproteins,” Journal of Molecular Biology, Vol. 76, pp. 241—256, 1973.[30] F. Richards, “The protein folding problem,” Scientic American, Vol. 264,No. 1, pp. 54—63, 1991.[31] A. Sali, E. Shakhnovich, and M. Karplus, “How does a protein fold?,” Nature, Vol. 369, pp. 248—251, 1994.[32] T. B. Sebastian, P. N. Kelin, and B. Kimia, “Alignment-based recognition of shape outlines.,” Proceedings of 4th International Workshop on Visual Form,Capri, Italy, pp. 606—618, 2001.[33] J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology. PWS Publishing Company, Boston, second ed., 1997.[34] N. Siew, A. Elofsson, L. Rychlewski, and D. Fischer, “Maxsub: an automatedmeasure for the assessment of protein structure prediction quality.,” Bioinformatics, Vol. 16, No. 9, pp. 776—785, 2000.[35] N. Siew and D. Fischer, “Convergent evolution of protein structure prediction and computer chess tournaments:CASP, Kasparov, and CAFASP.,” IBM System Journal, Vol. 40, No. 2, pp. 410—425, 2001.[36] C. N. Storm and R. B. Lyngso, “Prediction of protein structures using simple exact models..” Technical Report. University of Aarhus, Denmark, 1996.[37] C. N. Storm and R. B. Lyngso, “Protein folding in the 2d hp model..” Technical Report RS-99-16 BRICS. University of Aarhus, Denmark, 1999.[38] W. R. Taylor and C. A. Orengo, “Protein structure alignment.,” Journal ofMolecular Biology, Vol. 208, pp. 1—22, 1989.[39] R. Unger and J. Moult, “Finding the lowest free energy conformation of aprotein is NP-hard problem: Proof and implications,” Bulletin of MathematicalBiology, Vol. 55, No. 6, pp. 1183—1198, 1993.[40] R. Unger and J. Moult, “Genetic algorithms for protein folding simulations,”Journal of Molecular Biology, Vol. 231, No. 1, pp. 75—81, 1993.[41] M. Waterman, Introduction to Computational Biology: Maps, Sequences andGenomes. Chapman and Hall, London: CRC Press, 1995.