幾何雜湊在蛋白質結構比對上的應用

Abstract

隨著蛋白質資料的快速增加，有效的分析蛋白質之間的關係成為了一個重要的標的，而蛋白質結構比對則是分析蛋白質的關係之中重要的方法之一。藉由有效的計算兩個蛋白質結構的相似度，可以得知這兩個蛋白質在演化上的關係如何，以藉此推斷兩個蛋白質功能上的相似性。而蛋白質結構比對最重要的因素是快速與準確，因此本研究使用了幾何雜湊這個演算法來比對蛋白質結構。幾何雜湊演算法本來是用在電腦視覺領域，用來比對兩個空間中的結構，是目前最主要的結構比對的演算法。而本論文改良了幾何雜湊演算法，提升了它的準確率，並對不同的蛋白質結構比對，設計了幾個不同的幾何雜湊比對法。最後提出了一個蛋白質位元向量的概念，藉由本研究所提出的蛋白質位元向量，可以快速的推算出兩個蛋白質結構的相似度，來判斷有無進行更精確的比對的需求。在實驗部分，本論文使用了數個蛋白質資料庫(Protein Data Bank)中的資訊來進行比對，而所得到的實驗結果都不錯。藉由本研究所提出的蛋白質結構比對工具，可以有效的讓生化學家在蛋白質分析上有遠大的助力。

With the fast increasing of proteins’ data, effectively analyzing the relation between proteins has become an important issue. One important approach to analyze the relation between proteins is protein structure comparison(PSC). By calculating the similarity between two protein’s structures, we can get the relationship between two structures in evolution. According to these information, we can inference these proteins may possess some similar function. The most important issue of protein structure comparison is fast and preciseness. Therefore, the geometric hashing algorithm was proposed to align two protein structures. Geometric hashing is a technique based on computer vision, used to compare two structures. We improve the geometric hash algorithm, especially increasing the accuracy. We also proposed several variant geometric hashing algorithms for protein structure comparison of different purpose. Finally, we propose bit-vector-based similarity estimation for fast PSC. In our experiments, we use compare several proteins from PDB(Protein Data Bank), and get some good results. The proposed algorithms are well coded and provided on the web. Molecular biologist can leverage our research results by using the provided tool.