黃乾綱臺灣大學：工程科學及海洋工程學研究所楊逸偉Yang, Yi-WeiYi-WeiYang2007-11-262018-06-282007-11-262018-06-282007http://ntur.lib.ntu.edu.tw//handle/246246/51023隨著蛋白質資料量的快速增加，如何有效地分析蛋白質之間的關係成為現今非常重要的議題，因此，生物學家可以透過蛋白質結構的分析快速地了解蛋白質之間的反應關係與演化上的關聯性。然而，隨著蛋白質結構資料不斷地以指數般的成長，單純只使用傳統的蛋白質結構比對演算法，來進行蛋白質結構上的資料探勘，如structure motif detection 或是 structure conservation discovery時，將因大量的次結構比對造成長時間耗時的計算而無法應付。因此為加速蛋白質結構比對的速度並運用於蛋白質結構資料探勘上，本研究透過採用索引的技巧，進行蛋白質的局部環境結構編碼，轉換成具有局部結構資訊的一維結構特徵 (structural signature)。並透過索引技巧避免傳統蛋白質結構比對 (protein structure comparison, PSC)所遭遇到的問題，提供同時比對大量蛋白質結構的功效。 本論文透過索引值的設計，將原本複雜三維空間結構，在可容忍的資料流失下轉換成為一維的結構特徵，所設計出來的結構特徵仍保有空間中的資訊。並利用索引及近似比對技巧，在尚未進入蛋白質比對階段前，先快速搜尋相似程度較高的部份結構，有了這個先決條件，可以有效的減少所需比對時間，最後並嘗試帶入原有結構特徵值資訊，找出對應蛋白質之間的共同座標系轉換資訊，進而達到蛋白質結構搜尋比對效用。在實驗部分，本論文使用了蛋白質結構資料庫 (Protein Data Bank)中的資訊來進行驗證，並將比對出的結果參考Enzyme Classification中的資料，並比較VAST和SSM這兩個演算法的效果，驗證所找尋到的蛋白質具有相同功能。就目前所觀察到的實驗數據證明這樣的架構是可行的。藉由本研究所提出的蛋白質結構比對方法，可以讓生物學家在蛋白質結構分析上有更好的工具。With the fast growth of determined protein structures in Protein Data Bank, to effectively analyze the relationship between protein structures has become a critical issue. Currently, protein structure comparison is the major approach to analyze protein structures and discover local functional regions. By evaluating similarity among protein structures, we can identify common substructures shared by the group of proteins. However, if we would like to mine local conserved regions among the group of protein structures, pair-wise protein structure comparison could be applied but it is still a time-consumed computational task because of the exponential growth of protein structures. In this paper, we use sphere-based representation to describe protein local structure and apply indexing technique on protein structure to approach database search on Protein Data Bank for the purpose of protein structure mining. Our approach tries to filter out lots of non-similar protein structures to avoid unnecessary comparisons, and then compares multiple protein structures at the same time. While comparing with VAST and SSM in the capability of find protein structure under hierarchical functional classification of Enzyme Classification, our proposed approach has better performance in sensitivity and precision than VAST and SSM. Our experiment results reveal that our method could be a good approach to find protein structure with similar function. We provide the alternative for molecular biologists to search whole Protein Data Bank from the view of protein local structure.口試委員會審定書 i 誌謝 ii 中文摘要 iii 英文摘要 iv Chapter 1 導論 1 1.1. 蛋白質結構比對 1 1.2. 相似蛋白質結構分類及搜尋 4 1.3. 透過索引技巧搜尋蛋白質相似結構 4 1.4. 透過蛋白質結構資訊統一命名蛋白質 5 1.5. 動機 5 1.6. 章節說明 6 Chapter 2 相關研究 7 2.1. 相關蛋白質資料庫介紹 7 2.1.1. Protein Data Bank 7 2.1.2. Enzyme Structure Database 8 2.1.3. SCOP (Structural Classification of Protein) 8 2.1.4. CATH 9 2.2. 蛋白質結構比對 (Protein Structure Comparison, PSC) 9 2.2.1. 整體結構比對 (Global Structure Alignment) 9 2.2.2. 局部結構比對 (Local Structure Alignment) 12 2.3. 蛋白質結構比對評分參數 12 2.3.1. 對應胺基酸個數 (Number of Equivalent Residue) 12 2.3.2. RMSD (Root Mean Square Deviation) 13 2.3.3. 幾何雜湊 (Geometric Hashing) 13 2.3.4. 修正 (Refinement) 14 2.4. 幾何結構雜湊及索引 14 Chapter 3 以NRS為基礎的結構比對演算法 15 3.1. 問題定義 15 3.2. ESC演算法流程圖 16 3.3. 步驟一 - 使用NRS方式記錄局部環境結構 16 3.4. 步驟二 - 透過幾何資訊編碼蛋白質局部結構 17 3.4.1. 設計概念1 – 依據殘基距離紀錄蛋白質局部結構 18 3.4.2. 設計概念2 – 加入方向性避免鏡像結構誤判 19 3.4.3. 設計概念3 – 加入統一座標系統減少比對之旋轉 19 3.4.4. 設計概念4 – 加入重疊區塊判斷邊界殘基 19 3.5. 快速過濾不相似NRS 20 3.6. 步驟三 - 透過分群特徵值找尋共有座標系 21 3.7. 步驟四 - 比對蛋白質之間相似程度 22 3.7.1. 產生共同座標系統 22 3.7.2. 使用幾何雜湊比對 22 Chapter 4 實驗設計 24 4.1. 實驗一、分群演算法與距離函式分析 24 4.2. 實驗二、NRS的Signature和所對應點數關係 26 4.3. 實驗三、全體比對效果 28 4.4. 實驗四、一對多找尋相似結構 31 4.5. 實驗五、一對全體PDB搜尋相似結構 36 4.6. 實驗六、透過EC找尋共同反應區塊 40 Chapter 5 討論 46 5.1. 所遇問題 46 5.2. 改進方式 46 5.2.1. 結構特徵值容忍度方面 47 5.2.2. 分群演算法方面 47 5.3. 結論 47 Chapter 6 未來應用 50 6.1. 蛋白質資料庫搜尋 50 6.2. 局部蛋白質結構搜尋 50 參考文獻 522977048 bytesapplication/pdfen-US蛋白質結構搜尋蛋白質結構比對索引值設計NRSindexingProtein structurethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51023/1/ntu-96-R94525054-1.pdf