蔣強榮 馬佳佳

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

關(guān)鍵詞：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?引言

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

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

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

1?SVM

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

SVM的機理是尋找一個滿足分類要求的最優(yōu)分類超平面，使該超平面在保證分類精度的同時，能夠使其兩側(cè)空白區(qū)域最大化。理論上SVM能夠?qū)崿F(xiàn)對線性可分數(shù)據(jù)的最優(yōu)分類。

以兩類數(shù)據(jù)分類為例，給定訓練樣本集?（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‖，因此?構(gòu)造最優(yōu)超平面問題則轉(zhuǎn)化為在約束式下求解：

為了解決該約束最優(yōu)化問題，引入Lagrange函數(shù)：

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

因此，求得最優(yōu)解。

計算最優(yōu)權(quán)值向量?w?*與最優(yōu)偏置b?*?，分別為：

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

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

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

以特征向量Φ（x）代替輸入向量x，則可得到最優(yōu)分類函數(shù)為：

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

2?描述符研究現(xiàn)狀

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

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

2.1?描述符

2.1.1?指紋

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

2.1.2?Maccs Keys

Maccs Keys[11]是指基于給定化合物結(jié)構(gòu)與預(yù)先由該領(lǐng)域?qū)＜叶x結(jié)構(gòu)片段的模式匹配。每一個結(jié)構(gòu)片段就是一個鍵，在描述空間中占據(jù)一個固定位置。因此，該方法依賴于預(yù)先定義的規(guī)則封裝分子描述符，而沒有從數(shù)據(jù)集中學習。

與指紋描述符相比，Maccs Keys沒有哈希函數(shù)作用在子結(jié)構(gòu)上。其優(yōu)點在于子結(jié)構(gòu)的任意拓撲可形成描述符空間的一部分，缺點是不能適應(yīng)特殊數(shù)據(jù)集與分類問題。

2.1.3?環(huán)樹表示法（CT）

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

2.1.4?頻繁子結(jié)構(gòu)（FS）

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

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

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

2.2?核函數(shù)

描述符空間常用的核函數(shù)有Tanimoto coefficient核與Min?Max核，滿足Mercer條件[15]，兩者實際上都是統(tǒng)計兩個被比較對象的共有特征占兩個對象所有特征之和的比例，值在[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系數(shù)。Min?Max核定義如下：

其中，P表示X和Y的所有特征集合，φ?p（·）統(tǒng)計p出現(xiàn)的次數(shù)。

2.3?描述符領(lǐng)域創(chuàng)新

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

3?圖核研究現(xiàn)狀

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

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

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

3.1?基于游走的圖核函數(shù)

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

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

3.2?基于路徑的圖核函數(shù)

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

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

3.3?基于子樹的圖核函數(shù)

基于子樹的圖核函數(shù)主要是Weisfeiler?Lehman子樹核[21]。它的思想是基于一維Weisfeiler?Lehman同構(gòu)判定算法，尋找一對圖結(jié)構(gòu)中同構(gòu)的子樹結(jié)構(gòu)。基于Weisfeiler?Lehman圖核的一般表示形式為：

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

其中h表示迭代次數(shù)或?qū)訑?shù)，φ?h?st（G）和φ?h?st（G）分別為G和G′對應(yīng)的映射特征，φ?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?圖核領(lǐng)域創(chuàng)新

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

4?結(jié)語

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

參考文獻：

[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]?張學工.關(guān)于統(tǒng)計學習理論與支持向量機[J].自動化學報，2000，26（1）：32?42.

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

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

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

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

[9]?王晶，周曠.基于支持向量機的腫瘤基因識別[J].計算機與數(shù)字工程，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]?王山，孫莉，吳杰，等.一種基于計數(shù)型布隆過濾器的分子相似性算法研究[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.