歐陽明臺灣大學：資訊工程學研究所張培根Chang, Pei-KenPei-KenChang2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/53740由於蛋白質表面結構與所屬弁鄏陰j烈的關連性，使得找尋多個蛋白質間相同局部區域的研究在近年來多所發展。藉由各種分析工具，使用者可以了解蛋白質間的弁鉬P演化上的關係。在此同時，亦有研究發現，某些蛋白質和某些核糖核酸，在結構上也存在著相似特性。現有工具大都設計來比對蛋白質間的相似性，因此需要新工具來解決上述的分子擬態問題。 我們提出一個藉由三維結構資訊來對其兩個分子的比對工具，使用者同時可藉由所開發的工具來觀測必對結果。除了找出蛋白質間重要的局部結構，此工具也能夠對蛋白質和核酸做比對，縱使兩種分子所屬性質是如此的截然不同。 為了比對分子 A 與 B，表面的原子可以使用 alpha-shape 演算法找出來。接著使用 Geometric Hashing 演算法得到大略的比對結果，則 A 分子中的部份原子會與 B 分子中的部份原子在空間中相近。之後便是微調的步驟，主要是依據兩分子間相同部份，利用Iterative Closet Point (ICP) 演算法來做局部的最佳化，直到空間中相近的原子個數不再增加。 實驗結果證實我們的方法確實可將兩個分子做結構上的比對，並不限制只能比對兩個蛋白質。此外，以資料差值的均方根 (RMSD) 與原子相近個數來做評估，我們的方法較優於其他的方法。Recently, developments have been made in finding the common substructures in proteins because the shape of a protein is highly related to its functions. With the help of the analyzing tools, a user can find out functional and evolutional relationships among proteins. However, it has been recently discovered that there are shared structural features between protein structures and RNA structures. The existing tools are designed only for alignment of proteins, thus new tools need to be developed to address the above problem, that is, molecular mimicry. We propose a tool to optimally align two molecules based on their 3D structural data, and the user can observe the result of alignment visually via the tool. In addition to finding important substructures in proteins, the tool can also align a protein and a nucleic acid, although they are two very different types of molecules. In order to align two molecules A and B, we might extract the surface atoms of molecules before aligning by alpha-shape algorithm. Then Geometric Hashing is applied to globally find initial matching of approximately overlapped atoms, thus parts of molecule A can be matched to parts of molecule B. Next, a fine tuning process is introduced, hich is based on local optimization of overlapped parts, and the Iterative Closest Point (ICP) is used until the number of overlapped atoms within a given distance threshold can not be increased any more. The results show that our method is useful to structurally align two molecules, not restricted to align two proteins only. Besides, our tool outperforms in terms of RMSD and number of matched atom pairs in comparison to other tools.ABSTRACT 2 中文摘要 3 TABLE OF CONTENTS 4 CHAPTER 1. INTRODUCTION 5 1.1 Overview 5 1.2 Proteins, Nucleic Acids, and the Protein Data Bank 6 1.3 Applications 8 CHAPTER 2. PREVIOUS WORK 10 CHAPTER 3. ALGORITHMS 12 3.1 Finding the surface atoms 13 3.2 Geometric Hashing 13 3.3 Fine Tuning Process 21 3.4 Discriminators 22 CHAPTER 4. EXPERIMENTAL RESULTS 23 4.1 The Molecular Alignment Problem 23 4.2 Comparison with Other Protein Alignment Tools 28 CHAPTER 5. CONCLUSION 33 REFERENCE 34 PROFILE 3964184760 bytesapplication/pdfen-US蛋白質結構比對活化區域Protein Structure AlignmentActive Sitethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53740/1/ntu-93-R91922080-1.pdf