基于SVM的化合物分類綜述

蔣強榮 馬佳佳

摘要：藥物研發是一個難度系數大、耗費時間長的工作。根據結構活性關系規則，具有相似結構的化合物可能具有相似特性。因此，準確地對化合物進行分類具有十分重要的意義。回顧了SVM與比較常用的化合物分類方法及各自的優缺點，闡述了對分類方法進行的改進與優化，展望了化合物分類的發展方向。

關鍵詞：SVM;化合物分類;描述符;圖核

Review of Chemical Compound Classification Based on SVM

JIANG Qiang?rong， MA Jia?jia

（Department of Computer Science， Beijing University of Technology， Beijing 100022， China）

Abstract：Drug development is a difficult and time?consuming task. According to the rule of structure activity， compounds with similar structures may have similar properties. Therefore， it is very important to classify compounds accurately. Firstly， this paper reviews SVM and the commonly used classification methods of compounds and their respective advantages and disadvantages. Secondly， it introduces the improvement and optimization method of classification methods. Finally， it looks forward to the development direction of compound classification.

Key Words：compound classification;descriptor;graph kernel

0?引言

隨著組合化學的快速發展，大大加快了化合物的合成與篩選速度，化合物數量急劇增長。藥物發現的目標是從巨大的化學空間里鑒別出對某一特定疾病具有生物活性的分子，然而在數據規模龐大的化學空間上進行詳盡的比對搜索十分困難[1]。因此，準確地對化合物進行分類是非常必要的。

化合物分類是一個非線性問題。SVM可將樣本從原始空間映射到一個更高維的特征空間，使樣本在該特征空間內線性可分。核函數的優點是可以簡化映射空間計算?；瘜W物分類主要有兩種方式：基于描述符的分類方法與基于圖核的分類方法。

描述符是分子相似性方法中的基本要素[2]?；诿枋龇诸惙椒ǖ乃枷胧鞘紫韧ㄟ^一個高維的特征向量描述化合物，該特征向量是由其包含的描述符（如圖片段）決定的，然后利用各種基于向量的核函數計算化合物的相似性。描述符分為1D描述符、2D描述符和3D描述符。1D描述符在利用SMILES[3]表示化合物方面應用較多，其不僅可以表示原子，還可以表示原子間的鍵;2D描述符是由2D分子圖形或結構片段計算得來的，目前在擴展連接性指紋方面應用最多;3D描述符描述的是分子形狀、分子總表面積與電壓等。

1?SVM

SVM[4]是建立在統計學習理論[5]基礎上的一種數據挖掘方法，可有效處理回歸問題（時間序列分析）與模式識別（分類問題、判別分析）問題，并被廣泛應用于文本識別[6]、手寫字體識別[7]、人臉圖像識別[8]與基因分類[9]等。

SVM的機理是尋找一個滿足分類要求的最優分類超平面，使該超平面在保證分類精度的同時，能夠使其兩側空白區域最大化。理論上SVM能夠實現對線性可分數據的最優分類。

以兩類數據分類為例，給定訓練樣本集?（x?i，y?i），i=1，2，...，l，x∈R?n，y∈{±1}，超平??面記作（w·x）+b=0，為使分類面對所有樣本能夠正確分類并且具備分類間隔，則要求其滿足如下約束：y?i[（w·x?i）+b]≥1，i=1，2，…，l。

可以計算出分類間隔為2/‖w‖，因此?構造最優超平面問題則轉化為在約束式下求解：

為了解決該約束最優化問題，引入Lagrange函數：

式（2）中，?a?i?>0為Lagrange乘數。約束最優化問題的解由Lagrange函數的鞍點決定，并且最優化問題的解在鞍點處滿足對 w 和b 的偏導為0。將該二次型規劃問題轉化為相應的對偶問題，即：

因此，求得最優解。

計算最優權值向量?w?*與最優偏置b?*?，分別為：

式（4）和式（5）中，下標?j∈{j|a?*?j>0}。因此，得到最優分類超平面（w?*·x）+b?*?=0，而最優分類函數為：

對于線性不可分情況，SVM的主要思想是將輸入向量映射到一個高維特征向量空間，并在該特征空間中構造最優分類面。

將?x從輸入空間Rn到特征空間H進行Φ變換?，得到：

以特征向量Φ（x）代替輸入向量x，則可得到最優分類函數為：

在以上對偶問題中，無論是目標函數還是決策函數，都只涉及到訓練樣本之間的內積運算，從而在高維空間中避免了復雜的高維運算。

2?描述符研究現狀

在化學中，圖可以用來直接模擬化合物結構的主要拓撲與幾何特征。圖中頂點表示原子，邊表示原子間的連接關系。將化合物表示的分子圖中除去H，分子中的重原子（C，N，O）對應圖中頂點，原子間的鍵（單鍵、雙鍵、三鍵、芳香鍵）對應圖中的邊，如圖1所示。

本節將介紹當前流行的從分子圖提取片段的描述符與描述符常用核函數。

2.1?描述符

2.1.1?指紋

指紋[10]是指將化合物的結構特征編碼成固定位的向量，指紋中具體位字符串的生成依賴于鍵的數量、設置位數量、哈希函數與位字符串長度。指紋描述符的優點是能將化合物包含的大量子結構緊湊地表示出來。

2.1.2?Maccs Keys

Maccs Keys[11]是指基于給定化合物結構與預先由該領域專家定義結構片段的模式匹配。每一個結構片段就是一個鍵，在描述空間中占據一個固定位置。因此，該方法依賴于預先定義的規則封裝分子描述符，而沒有從數據集中學習。

與指紋描述符相比，Maccs Keys沒有哈希函數作用在子結構上。其優點在于子結構的任意拓撲可形成描述符空間的一部分，缺點是不能適應特殊數據集與分類問題。

2.1.3?環樹表示法（CT）

CT[12]是指將化合物表示成環和特定樹的集合，主要思想是首先識別分子圖中的互連組件（也稱為塊），一旦這些塊被識別，通過從塊中枚舉具有確定數量的簡單環，第一個特征集合隨之產生。所有環被識別之后，分子圖中的塊則被刪除，此時的圖是剩余樹組成森林的集合，每一個樹作為一個描述符。最終的描述符空間是環與剩余樹的集合。CT表示法用到樹模型的具體拓撲與大小取決于分子圖中塊的位置。

2.1.4?頻繁子結構（FS）

FS是指在給定?σ的前提下，在數據集中尋找出現次數大于σ?的子結構。因此，與Maccs Keys不同的是，當?σ?改變時，FS的描述符空間也會改變;與指紋描述符不同的是，其不考慮子圖大?。ㄦI的數量），所有子圖構成描述符空間。FS的缺點是?σ值選取過大或過小都可能導致分類效果不理想。

2.1.5?擴展連接性指紋（ECFPs）

ECFPs由摩根算法[13]的變體派生而來，生成過程分為3步：①初始分配階段，為每個原子分配整數標識符;②迭代更新階段，更新每個原子的標識符，以對每個原子鄰居的標識符作出反應;③重復標識符移除階段[14]，如果兩個特征是經過不同次數迭代生成的，則經過更大迭代次數生成的特征將被移除，如果兩個特征是經過相同次數迭代生成的，則哈希標識符值更大的特征將被拒絕。

2.2?核函數

描述符空間常用的核函數有Tanimoto coefficient核與Min?Max核，滿足Mercer條件[15]，兩者實際上都是統計兩個被比較對象的共有特征占兩個對象所有特征之和的比例，值在[0，1]之間。

2.2.1?Tanimoto coefficient核

Tanimoto coefficient核適用于二進制向量，計算的核定義如下：

其中，M表示X、Y均由M維二進制向量表示，X?i、Y?i分別表示X和Y的第i維向量。

2.2.2?Min?Max核?在二進制向量的情況下，Min?Max核退化為Tanimoto系數。Min?Max核定義如下：

其中，P表示X和Y的所有特征集合，φ?p（·）統計p出現的次數。

2.3?描述符領域創新

隨著研究的深入，為了提高化合物分類的準確率，研究者將重心放在提出或改進新的描述符，以及改進或組合描述符空間的核函數等方面。Gong?Hua Li[16]提出新的分子指紋描述方法，將每個化合物的對應模式在活性與非活性化合物中所占比例作為權重系數，并將單個核函數進行兩兩相乘組合，最終取得85%左右的成功率;翟璨等[17]采用ECFPs描述符表示分子圖，根據不同長度描述符應具有不同權重改進了Min?Max核，并在PTC和HIV數據集中進行測試，使分類準確率都得到了提高;王山等[18]采用計數型布隆過濾器對指紋描述符分子相似性進行改進，并采用 DUD LIBVS 1.0 數據集對改進方法進行了比較驗證，與其它原始分子相似性方法相比，其在相似性判斷的準確性與骨架躍遷潛能上均有所提高。此外，還有很多學者提出多核組合方式，以更好地對化合物進行分類。

3?圖核研究現狀

化合物分子圖采用鄰接矩陣表示，兩個頂點如果有邊相連，則值為1。鄰接矩陣定義如下：

其中，?A為化合物圖G的鄰接矩陣，v?i和v?j為G的頂點，假設圖G有n個頂點，則0≤i<n，0≤j<n。

圖核函數主要分為3類：①基于游走的圖核函數;②基于路徑的圖核函數;③基于子樹的圖核函數。

3.1?基于游走的圖核函數

基于游走的圖核函數主要是隨機通路核[19]。隨機通路核通過計算兩個圖的公共通路數目度量兩個圖的相似性，兩個圖?g（V?1，E?1）和g′ （V?2，E?2）的匹配通路數可以通過計算其直積圖g×g'得到。設A?×為直積圖g×g′的鄰接矩陣，則隨機通路核函數表示如下：

其中λ是使和收斂的衰減因子，λ<1，確保對于足夠大的n可以忽略不計。V?×為直積圖g×g′的任一頂點，時間復雜度為Ο（n?6）。

3.2?基于路徑的圖核函數

基于路徑的圖核函數主要是最短路徑核[20]。最短路徑核通過比較兩個圖G?1和G?2的所有最短路徑度量兩個圖的相似性。G?1′=（V?1′，E?1′）和G?2′=（V?2′，E?2′）分別是G?1和G?2的最短路徑圖，所有最短路徑對核的值構成最短通路核，最短路徑可通過弗洛伊德算法求出。最短路徑核的優點是可以完全避免路徑回溯問題。最短路徑核表示如下：

其中?SP（·）表示圖的所有最短路徑集合，k（s?1，s?2）定義為狄拉克核函數，當s?1與s?2的長度一樣時值為1，否則為0。

3.3?基于子樹的圖核函數

基于子樹的圖核函數主要是Weisfeiler?Lehman子樹核[21]。它的思想是基于一維Weisfeiler?Lehman同構判定算法，尋找一對圖結構中同構的子樹結構?；赪eisfeiler?Lehman圖核的一般表示形式為：

其中?h表示迭代次數，G?×、G′?×分別表示圖G和G′?對應的WL序列。假設∑?i∈∑表示WL算法在第?i次迭代后，在圖G和G′中出現至少一次的頂點標簽集中所構成的字母集合，定義一個映射C?i：{G，G′}?×∑?i→N， C?i（G，σ?ij）表示圖G中字母σ?ij出現的次數，則Weisfeiler?Lehman子樹核的表示形式為：

其中h表示迭代次數或層數，φ?h?st（G）和φ?h?st（G）分別為G和G′對應的映射特征，φ?h?st（G）=（c?0（G，δ?01），…，c?h（G，δ?h1），…，c?h（G，δ?h|Σ?i|）），φ?h?st（G′）=（c?0（G′，δ?01），…，c?h（G′，δ?h1），…，c?h（G′，δ?h|Σ?i|））。

3.4?圖核領域創新

Xu等[22]考慮到已有Weisfeiler?Lehman圖核忽視的結構信息，提出一個Weisfeiler?Lehman圖核混合框架，并將其運用于Weisfeiler?Lehman圖序列上，取得了很好的分類結果;Bai等[23]提出一個新的用Jensen?Shannon方法表示頂點的圖核，可識別兩個圖頂點之間的對應關系;Kondor & Pan提出多尺度拉普拉斯圖核，可捕獲個別頂點及子圖之間的拓撲關系。此外，研究者們也不斷致力于提出新的圖核或改進已有圖核，以提高化合物分類的準確率。

4?結語

本文從兩方面對基于SVM的化合物分類進行了詳細介紹，分別介紹了SVM理論、描述符與圖核的研究現狀及發展，并對目前常用的化合物分類方法進行了簡要敘述。目前的化合物分類方法很難達到95%以上的成功率，因此還需要作進一步深入研究，捕捉化合物結構間的特征，以提出更好的比較化合物相似性的方法，進一步提高化合物分類的準確率。

參考文獻：

[1]?RANU S. Querying and mining chemical databases for drug discovery[M]. University of California at Santa Barbara， 2012.

[2]?MALDONADO A G， DOUCET J P， PETITJEAN M， et al. Molecular similarity and diversity in chemoinformatics： from theory to applications[J]. Molecular diversity， 2006， 10（1）：39?79.

[3]?WEININGER D. SMILES I： introduction and encoding rules[J]. Journal of Chemical Information and Computer Sciences， 1988.

[4]?張學工.關于統計學習理論與支持向量機[J].自動化學報，2000，26（1）：32?42.

[5]?VLADIMIR N VAPNIK， 張學工.統計學習理論的本質[M].北京：清華大學出版社，2000.

[6]?陳佳希.基于支持向量機的文本分類[J].電子世界，2017（7）：64.

[7]?董婉君.基于SVM的手寫字體識別[J].工程技術：全文版，2016（2）：00288.

[8]?郭慧敏，丁軍航.基于支持向量機的人臉特征分類技術[J].青島大學學報：工程技術版，2016，31（4）：56?61.

[9]?王晶，周曠.基于支持向量機的腫瘤基因識別[J].計算機與數字工程，2011，39（9）：3?6.

[10]?DAYLIGHT INC. Mission Viejo CA USA[EB/OL]http：//www.daylight.com.

[11]?DURANT J L， LELAND B A， HENRY D R， et al. Reoptimization of MDL keys for use in drug discovery[J]. Journal of Chemical Information and Modeling， 2002，42（6）：1273–1280.

[12]?WROBEL S. Cyclic pattern kernels for predictive graph mining[C].Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2004：158?167.

[13]?MORGAN H L. The generation of a unique machine description for chemical structures?a technique developed at chemical abstracts service[J]. Journal of Chemical Documentation， 1965， 5（2）：107?113.

[14]?ROGERS D， HAHN M. Extended?connectivity fingerprints[J]. Journal of Chemical Information & Modeling， 2010， 50（5）：742?54.

[15]?SWAMIDASS S J， CHEN J， BRUAND J， et al. Kernels for small molecules and the prediction of mutagenicity， toxicity and anti?cancer activity[J]. Bioinformatics， 2005， 21（1）：359–368.

[16]?LI G H， HUANG J F. CDRUG： a web server for predicting anticancer activity of chemical compounds[J]. Bioinformatics， 2012， 28（24）：3334?3335.

[17]?JIANG Q， ZHAI C， XIONG Z. Chemical compound classification based on improved Max?Min kernel[J]. Journal of Chemical & Pharmaceutical Research， 2014.

[18]?王山，孫莉，吳杰，等.一種基于計數型布隆過濾器的分子相似性算法研究[J].計算機科學，2017，44（b11）：552?556.

[19]?GRTNER T， FLACH P， WROBEL S. On graph kernels： hardness results and efficient alternatives[J]. Lecture Notes in Computer Science， 2003， 2777：129?143.

[20]?BORGWARDT K M， KRIEGEL H P. Shortest?path kernels on graphs[C].IEEE International Conference on Data Mining. IEEE， 2006：74?81.

[21]?SHERVASHIDZE N， SCHWEITZER P， JAN VAN LEEUWEN E， et al. Weisfeiler?Lehman Graph Kernels[J]. The Journal of Machine Learning Research， 2011，12（3）：2539?2561.

[22]?XU L， XIE J， WANG X， et al. A mixed Weisfeiler?Lehman graph kernel[J]. Lecture Notes in Computer Science， 2015， 9069：242?251.

[23]?BAI L， ZHANG Z， WANG C， et al. A graph kernel based on the Jensen?Shannon representation alignment[C].International Conference on Artificial Intelligence. AAAI Press， 2015：3322?3328.