以橢圓群集為基礎的蛋白質結構比對演算法之研究

A Protein Structure Comparison Method Based on Hyper-Ellipsoidal Clusters

陳尹(Yin Chen)

指導教授 ： 歐陽彥正

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00514

摘要

本論文介紹一個以橢圓群集為基礎的二階段式蛋白質結構比對演算法，二階段式的設計是為了增加比對的速度。第一階段利用啟發式演算法找出粗略比對，以減少結構比對的次數；第二階段利用修正演算法，使得粗略比對修正為最佳比對。橢圓群集則為嶄新的概念，除了利用二級結構的ㄠ袹憿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

並列關鍵字

secondary structure ； dynamic programming ； alignment ； geometric hshing ； protein structure comparison

參考文獻

[1] C. Branden and J. Tooze, Introduction to protein structure. Second edition, Garland Publishing, New York. 1999

[3] H. Frigui, A Scalable Clustering Approach Based on the Synchronization of Pulse-Coupled Oscillators. To appear in Data Mining and Knowledge Discovery.

[4] C. Branden and J. Tooze, Introduction to Protein Structure, Second edition, Garland Publishing, New York, 1999

[5] M. Zuker and R. L. Somorjai, The alignment of protein structures in three dimensions. Bull. Math. Biol., 51, pp. 55-78, 1989

[6] M. Levitt and M. Gerstein, A Unified Statistical framework for Sequence Comparison and Structure Comparison. Proc. Nat. Acad. Sci. USA, vol. 95, pp. 5913-5920, 1998