歐陽彥正臺灣大學：資訊工程學研究所陳尹Chen, YinYinChen2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/54129本論文介紹一個以橢圓群集為基礎的二階段式蛋白質結構比對演算法，二階段式的設計是為了增加比對的速度。第一階段利用啟發式演算法找出粗略比對，以減少結構比對的次數；第二階段利用修正演算法，使得粗略比對修正為最佳比對。橢圓群集則為嶄新的概念，除了利用二級結構的ㄠ袹憿Bβ折板資訊之外，更加上了蛋白質結構當中其餘彎曲部分的資訊，藉以增加比對的準確率，並獲得具有生物意義的結果。 本論文研究的演算法，針對各種類型的蛋白質結構，皆能有效地找出結構的對應結果。本論文採取三組不同的資料集，針對一對多、多對多進行比對實驗，藉此檢驗演算法在結構比對上表現。當中並以十個困難個案這組基準資料集，與Dali、CE、VAST、ProSup、FLASH等演算法進行比較，發現本文演算法的確在整體比對、局部比對之中，皆能得到更好的比對效果。同時我們不僅計算出各個比對結果的相似度，並呈現出蛋白結構實際的對應結果，確認演算法能夠找出蛋白質之間具有生物意義的共同結構。 本論文所提出的演算法之時間複雜度，決定於比對演算法的選擇，利用動態規劃以及幾何雜湊時，分別為O(n4)和O(n3)。與其他結構比對演算法相比，除FLASH之外，本論文之結構比對演算法時間複雜度均相等或低於，其餘著名的以胺基酸片段為基礎的比對演算法。This thesis reports a study on a two-stage protein structural alignment algorithm based on hyper-ellipsoidal clusters. The design of the two-stage algorithm is aimed at improving the efficiency of protein structural alignment without trading off analysis accuracy. In the first stage of the proposed approach, hyper-ellipsoidal clusters are employed to model the substructures of random coils as well as the第一章 緒論 - 1 - 1.1蛋白質結構比對的興起 - 1 - 1.2 研究動機及目的 - 1 - 1.3 論文架構 - 2 - 第二章 蛋白質結構比對之相關研究 - 3 - 2.1 定義 - 3 - 2.1.1 剛體重疊 - 3 - 2.1.2 相似度 - 3 - 2.1.3 二級結構 - 4 - 2.1.4 整體比對、局部比對 - 4 - 2.2 相似度 - 4 - 2.2.1對應殘基數 - 4 - 2.2.2 Root Mean Square Error - 5 - 2.2.3 P value - 6 - 2.3 蛋白質結構比對的類型 - 6 - 2.3.1 內容型 - 6 - 2.3.2 非順序型 - 7 - 2.3.3 順序型 - 7 - 2.4 剛體重疊 - 8 - 2.4.1 直接比對 - 9 - 2.4.2 兩階段式比對 - 9 - 2.5 以胺基酸序列片段為基礎的蛋白質結構比對演算法 - 10 - 2.5.1 ProSup - 11 - 2.5.2 FLASH - 11 - 2.5.3 討論 - 13 - 2.6 幾何雜湊 - 14 - 2.7 複雜度分析 - 16 - 第三章 以橢圓模型為基礎的蛋白質結構比對演算法 - 17 - 3.1 前言 - 17 - 3.2 演算法簡介 - 17 - 3.1演算法第一步驟：分群 - 18 - 3.3.1 以二級結構為基礎的分群 - 18 - 3.3.2 以橢圓群集為基礎的分群 - 20 - 3.3.3 群集之幾何意義 - 23 - 3.2演算法第二步驟：結構比對 - 26 - 3.2.1結構比對演算法 - 27 - 3.2.2評分方式 - 28 - 3.3演算法第三步驟：修正 - 32 - 3.3.1修正演算法 - 32 - 3.3.2最小平方法 - 34 - 3.3.3討論 - 34 - 3.4複雜度分析 - 34 - 第四章 實驗結果 - 36 - 4.1 實驗一 - 36 - 4.1.1資料集 - 36 - 4.1.2實驗數據 - 36 - 4.1.3 實驗結果 - 37 - 4.2 實驗二 - 37 - 4.2.1 資料集 - 37 - 4.2.2 實驗數據 - 37 - 4.2.3 實驗結果 - 39 - 4.3 實驗三 - 40 - 4.3.1 資料集 - 41 - 4.3.2 實驗數據 - 42 - 4.3.3實驗結果 - 42 - 第五章 結論與展望 - 47 - 5.1 結論 - 47 - 5.2 展望 - 49 - 參考文獻 - 51 -1832932 bytesapplication/pdfen-US二級結構動態規劃橢圓群集幾何雜湊蛋白質結構比對secondary structuredynamic programmingalignmentgeometric hshingprotein structure comparisonthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54129/1/ntu-93-R91922076-1.pdf