基于混合特征預測藥物-靶標相互作用的K近鄰模型

王紅梅, 郭真俊, 郭 放, 張麗杰

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

確定藥物-靶標相互作用已成為藥物重新定位、藥物發現、副作用預測等領域的重要前提[1]，而確認藥物-靶標對是許多藥物研究的重要難題。在目前的數據中，只有少數藥物-靶標對得到了實驗驗證，除了已經存儲在各種數據庫中的已知相互作用外，還有無數未配對的小分子化合物需要被發現并開發成新的藥物，在此基礎上，通過生化實驗預測潛在藥物-靶標相互作用是一項非常昂貴、耗時和具有挑戰性的工作。文中提出的方法可以有效地預測潛在藥物-靶標相互作用，在許多相關生物信息學領域取得良好的性能，它們很大程度上可以縮小藥物-靶標相互作用實驗的研究范圍，因此，人們對預測藥物-靶標相互作用計算技術的發展有著持續而迫切的需求。

目前，基于配體、基于靶標和基于化學基因組學方法是藥物-靶標相互作用預測的三類主要計算方法。基于配體的方法通過將新配體與已知蛋白質配體進行比較來預測相互作用。然而，當已知配體數量不足時，基于配體的方法表現不佳。基于靶標的方法考慮了靶標蛋白的三維結構，因此當存在大量具有不可用的三維結構蛋白質時變得不適用，此外，它們不能應用于膜蛋白，如離子通道和G蛋白偶聯受體，其結構過于復雜，難以獲得，且對接模擬通常需要很長時間，因此效率特別低。

為了克服傳統方法的局限性，化學基因組學方法被提出，用于大規模藥物發現和藥物重定位，該方法可以充分利用有利于預測的生物數據，從化合物的化學空間和靶標的基因組特征空間提取不同信息以預測新的藥物-靶標相互作用，化學基因組學方法可以分為基于機器學習方法、基于圖方法、基于網絡方法三種類別。在基于網絡和基于圖方法[2-4]中，通常用二部圖表示藥物-靶標相互作用，圖中節點表示藥物或靶標，邊表示藥物-靶標相互作用，通過二部圖可以推斷網絡或者圖中缺失的鏈接，同樣，可以將二部圖轉化為關聯矩陣，使用矩陣分解的方法[5]推斷隱藏的關聯。在基于機器學習[6-8]的方法中，藥物-靶標相互作用預測通常看作是一個二分類問題，將藥物和靶標的信息表示為特征，將藥物-靶標之間的相互作用表示為類標簽。在所有化學基因組方法中，基于機器學習方法因其可靠的預測結果而獲得了最多的關注，基于機器學習能夠從復雜數據中尋找信息，利用藥物和靶標的化學和生物特性為大規模數據進行預測[9]。

在先前研究[10]的基礎上，使用機器學習算法K近鄰(K-Nearest Neighbors， KNN)預測藥物-靶標相互作用。文中將提取的藥物-靶標的相似性特征作為算法的輸入，使用KNN模型進行分類預測，將預測問題轉換為二分類問題，通過用精確率、召回率、F1值進行性能評估，KNN方法將數據成員存儲在高效的數據結構中，減少了計算成本，經驗證KNN方法性能以及速度都明顯優于其他機器學習方法。

1 相關工作

1.1 邏輯回歸

邏輯回歸[11](Logistic Regression， LR)是一種常用二分類算法，其本質就是一個線性分類模型，它通過一個非線性化映射輸出一個概率值來評判分類標準，即LR將特征輸入集合轉化為0和1這兩類的概率。LR模型的用途很廣泛，常用于醫學、生物學或流行病學的分析，可以預測某一疾病的危險因素，也可根據模型判斷某人所屬于某個疾病的概率大小。

1.2 決策樹

決策樹算法[12]是分類中常用的算法，提供一種易于理解的建模技術，簡化了分類過程，且決策樹是一種透明機制，它方便用戶遵循一個樹結構，了解如何做出決策。決策樹的核心目標是產生一個模型，該模型根據大量輸入變量計算所需變量的值，決策樹方法主要分為兩個部分，即決策樹的生成和剪枝。在對比算法中，我們使用CART(Classification and Regression Tree)決策樹，CART構建的分類樹是基于屬性的二進制拆分，可以輕松處理數值變量和類別變量，可以串行實現，在選擇分割屬性時，使用基尼系數分割度量，使用 CART算法構建決策樹分類器有以下原因：其有著廣泛應用，基于該算法可以對生成的樹進行剪枝，以避免過擬合，這對于使用不平衡數據尤為重要。

1.3 AdaBoost算法

AdaBoost(Adaptive Boosting)算法最初由Schapire R等[13]提出，AdaBoost算法通過對訓練數據保持一個權值集合來創建一組弱分類器，其主要思想是在訓練集上保持一個權重的分布或集合，最初，所有的權值經過相同初始化，根據學習周期自適應做調整。為了可以針對性地建立分類器，提高不正確分類的訓練樣本權值，降低正確分類的樣本權值。對于弱分類器的組合，AdaBoost算法會增加分類錯誤率小的弱分類器權值，降低分類錯誤率較高的弱分類器權值，最終這些弱分類器構成了強分類器。AdaBoost算法精度高，不容易過擬合，但對異常值敏感，因為異常值可能獲得較大權重，最終影響整個模型。

1.4 支持向量機

支持向量機(Support Vector Machine， SVM)是文獻[14]提出的基于統計學習理論機器學習方法，先定義SVM用于數據點的線性分布，之后，又引入核函數處理非線性數據。最大邊緣分類器是SVM的最基本形式，它幫助確定線性可分訓練數據的最簡單分類問題。SVM最接近決策面的數據點，通過巨大維度空間中的超平面來執行數據向量的分類，換句話說，該算法利用輸入數據或訓練數據確定一個最優分離平面或超平面，公正地分離兩類或數據點簇，并且它們之間的距離相等。SVM在處理高維數據時會表現出高性能，但如果數據非常大，那么預測任務的速度會變慢且性能降低。

1.5 DTI-CDF

集成學習是機器學習中主要分類方法之一，它通過構造和組合多個學習者來完成學習任務，Chu Y等[10]將boosting(XGB)和bagging(RF)作為基分類器構建分類模型，DTI-CDF方法從異構藥物-靶標相互作用加權圖中提取特征，輸入構建的CDF模型，預測藥物-靶標之間是否有相互作用，該方法使傳統機器學習模型更加深入，性能優于傳統的集成學習和深度學習方法，預測的1 352個新藥物-靶標相互作用已經被數據庫KEGG[15]和DrugBank[16]支持，是一次預測領域的大膽嘗試。

2 基于混合特征預測藥物-靶標相互作用的KNN模型

使用機器學習中常用的分類算法KNN作為預測模型，文中方法先從構建的異構藥物-靶標相互作用圖中提取藥物-靶標對混合特征，將混合特征作為基于KNN模型的輸入特征向量，通過KNN模型預測藥物-靶標是否有相互作用。算法總體流程如圖1所示。

2.1 特征構建

PathCS[17]是一種基于藥物-靶標相互作用的異構加權圖的混合特征，該特征包含藥物、靶標及它們之間的相似性或者相互作用。

構建異構圖的內核有6種，包括一種蛋白質內核、高斯相互作用內核、基于鄰域交互推斷的內核以及三種藥物內核，分別計算相似性后得到藥物和靶標的組合相似性，然后將組合相似性與已知的藥物-靶標相互作用相結合，構建一個異構藥物-靶標相互作用圖，在異構圖中，兩個靶標節點或兩個藥物節點之間有邊表示它們之間具有相似性，邊的權值為兩個鏈接節點之間的相似性值，如果藥物與靶標有邊，則為已知相互作用，邊的權值為1。構建異構圖后，提取每個藥物靶標對的PathCS。

圖1 算法總體流程

2.2 KNN算法模型

KNN是一種在藥物計算設計中使用的非參數方法，它根據訓練數據中K個近鄰指定每個測試數據的類別，并且該類別等于這些K個近鄰中的大多數類別。將生成的PathCS作為每個藥物-靶標相互作用的輸入特征向量，其次，使用KNN分類器預測潛在的藥物-靶標相互作用。度量節點距離方式有很多，使用歐式距離(Eucledian Distance)計算節點對的距離。

對于K值的選擇，先使用較小的K值進行實驗，通過交叉驗證來選擇最優K值。構建 KNN 模型有蠻力法、KD樹、Ball樹三種構建方式，我們采用默認的方式，算法自動選擇合適的方法構建KNN模型。

2.2.1 蠻力法

KNN快速計算是機器學習的一個活躍研究領域，最簡單的鄰居搜索實現涉及對數據集中所有點對之間的距離進行蠻力計算，對于小數據集樣本，有效的蠻力鄰居搜索可能競爭力會比較大，隨著樣本數的增長，蠻力法就不太適用。

2.2.2 KD樹

KD樹是一種二叉樹結構，它沿數據軸遞歸劃分參數空間，將其劃分為嵌套的正交各向異性區域，數據點被歸檔到其中，是早期聚合信息的方法，其鄰居搜索通過使用關鍵字指定，并使用類進行計算，KD樹構建速度非常快，因為分區只沿數據軸進行，所以沒有其他維距離需要計算，因此可以解決蠻力方法計算效率低的問題，基本思想是通過有效地編碼樣本的聚合距離信息來減少所需的距離計算次數，例如：如果點A 離點B很遠，且點B非常接近點C，那么我們知道點A和C很遠，則無需明確計算它們的距離。

2.2.3 Ball樹

KD 樹沿數據軸對數據進行分區，由于Ball樹節點的球形是幾何形狀，Ball樹在一系列嵌套超球體中對數據進行分區，這使得樹的構建比 KD 樹的構建成本更高，盡管實際性能高度依賴于訓練數據的結構，但產生的數據結構在高度結構化的數據上非常有效，即使在非常高的維度上也是如此。基于Ball樹的鄰居搜索使用關鍵字指定，并使用類計算，解決了更高維度 KD 樹的低效率問題。

2.3 模型詳細內容

文中涉及的相關符號定義見表1。

表1 符號描述

基于混合特征預測藥物-靶標相互作用的KNN模型的算法步驟，輸入藥物-靶標對特征向量和類別標簽，輸出藥物-靶標對所屬的類別。

1)分別計算藥物和靶標的相似性，構建異構圖，從異構圖中提取藥物-靶標對的混合特征作為模型的輸入特征向量。

2)按照KNN算法優化設計策略[18]中的交叉驗證方法選擇K值，通過多次反復將數據集分為訓練集和測試集，然后嘗試在訓練集中取不同的K值，在測試集中觀察誤差，最后選出最小誤差對應的K值。

算法1步驟見表2。

表2 算法1步驟

3)和4)的偽代碼遍歷數據集中每個數據樣本，使用歐式距離計算預測樣本與已知樣本之間的距離，定義一個隊列，采用插入排序對距離進行升序排序，選取K個最近鄰樣本，在K個樣本中根據少數服從多數原則，將待預測樣本歸類為K個樣本中數最多的類別。

算法2步驟見表3。

表3 算法2步驟

KNN算法簡單易實現，如果數據集較大，需要大量空間存儲已知樣本，內存需求大，對測試樣本分類時，需要計算距離進行比較，計算量也大，因此，KNN算法的時間和空間復雜度與數據集中數據樣本數成正比，對于樣本數較少的數據集，KNN算法比較適用。

3 實驗及結果分析

3.1 數據來源

使用核受體(Nuclear Receptors， NR)數據集來評估KNN方法在藥物-靶標相互作用預測的性能，該數據集最初來自文獻[19]，并在后續工作DTI-CDF[10]中進一步作為基準，核受體數據集包含藥物數量54個、靶標數量26個、相互作用數量90個，并且有三種類型的信息：已知藥物-靶標相互作用、多種藥物相似性度量、多種靶蛋白相似性度量。

3.2 性能評估

為了與其他方法進行比較，文中參照文獻[10]提出的方法，使用不同的隨機種子隨機分成訓練集和測試集，進行10折交叉驗證，重復上述操作3次，取實驗的平均值作為最終結果，對每個預測模型，用精確率(P)、召回率(R)、F1值(F1-score)作為模型的衡量指標，計算公式如下：

(1)

(2)

(3)

式中：TP----實際值與預測值均為正的數據數量；

TN----實際值與預測值均為負的數據數量；

FP----實際值為負、預測值為正的數據數量；

FN----實際值為正、預測值為負的數據數量。

3.3 模型參數選擇與分析

由于KNN分類器結果的關鍵參數之一是選擇最佳數量的分子近鄰，如果選擇較小的K值，分類效果不好，容易發生過擬合；如果選擇較大的K值，近似誤差會增大，可能會導致分類不準確。因此，為了獲得最佳數值，先選取較小的K值進行實驗，采用交叉驗證法選取最優的K值，K值結果對比見表4。

表4 K值結果對比 %

從表4分析得出，相比之下，K值為6時，模型性能最好。

3.4 與其他模型分析比較

與機器學習方法SVM、AdaBoost、LR、CART和集成學習方法DTI-CDF進行分析比較，各分類模型結果對比見表5。

表5 各分類模型結果對比 %

分析表中預測結果可以得知，KNN方法在召回率性能上比DTI-CDF和AdaBoost稍微弱點，但F1值比DTI-CDF和AdaBoost方法分別提高了2.09%、1.63%，甚至精確率比DTI-CDF和AdaBoost方法分別提高了7.08%、3.42%，除此之外， KNN在精確率、召回率、F1值性能均高于其他機器學習方法，相比之下,KNN模型實驗速度快于DTI-CDF，表明KNN模型具有更高的分類有效性。

DTI-CDF方法比KNN方法召回率高2.38%，考慮數據集中藥物-靶標相互作用的整個空間，已知的相互作用視為正樣本，未知的相互作用視為負樣本，核受體數據集中正樣本數量低于負樣本數量，存在數據不平衡問題 ，DTI-CDF模型通過構造和組合兩個基分類器構成的分類模型比KNN模型更能處理數據不平衡問題，在未來工作中，我們會不斷對KNN模型進行完善，提高預測概率。

4 結 語

預測藥物-靶標相互作用有助于縮小生化實驗的研究范圍。文中提出一種新的基于混合特征預測藥物-靶標相互作用的KNN模型，針對核受體數據集，提取藥物-靶標的混合特征，將相似性信息輸入KNN模型，進而預測潛在的相互作用，精確率、召回率、F1值的平均值優于對比算法。進一步表明KNN方法是一種易于理解、速度快且實現簡單的分類算法。在未來，我們會進一步將KNN算法用于預測藥物-藥物相互作用、藥物-疾病關聯、疾病-疾病關聯等其他生物學鏈接，并結合深度學習相關模型，改進藥物-靶標相互作用預測性能。