Nearest Neighbor演算法處理符號性質資料的分類及其於蛋白質二級結構預測的應用

Abstract

蛋白質在生物體中一直扮演著很重要的角色且蛋白質被發現的數量及其結構逐年增加。隨著蛋白質的應用越來越廣泛，待解決的課題也就越來越多。例如：蛋白質二級結構預測問題、蛋白質摺疊預測問題(Protein folding prediction problem)、蛋白質投射問題(Protein mapping problem)等。目前在蛋白質相關問題的解決上，科學家都是利用X光繞射以及核磁共振(NMR)來取得實驗結果。這些方法雖然正確率高，但是相對地所要花費的時間及成本是相當高的。因此利用電腦科學中的機器學習(Machine learning)演算法來預測這些問題相信是能夠有效降低實驗成本的。 本篇論文，我們利用了Nearest Neighbor演算法僅針對了蛋白質二級結構預測問題進行了實驗。正如我們大家所知道的，每一種蛋白質序列皆是由20種不同的胺基酸(Amino acid)所組成，而每一種胺基酸都可視為一個符號(Symbol)。在過去，Nearest Neighbor演算法通常是用來處理資料屬性全部是數值的例子。在這樣的屬性當中，這些事例(Instance)都是被視為點，而且彼此之間的距離都適用於歐幾里得距離。然而在符號屬性的領域當中，處理符號是利用特定的距離表以產生事例之間的實質距離。我們所使用的距離是由Stanfill和Waltz所提出的Value Difference Metric表來定義出兩個符號間的實質距離。基於Value Difference Metric表的架構下，我們提出了兩個不同的判定法則來預測蛋白質二級結構。除此之外，我們也研究且實做了目前常用的一種預測法－PSIPRED。最後，我們試著將我們所用的兩種演算法和PSIPRED做結合，並朝向著混合後的準確率能夠不亞於PSIPRED之準確率的方向來努力。