基于Cheng-范數(shù)的不同維度樣本相似性度量

郭志偉，陳新莊

（延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西延安 716000）

生物信息學(xué)中，為解決蛋白質(zhì)功能聚類、疾病相關(guān)基因識(shí)別及藥物發(fā)現(xiàn)等問題，學(xué)者們已經(jīng)從各個(gè)計(jì)算方面提出了許多強(qiáng)大的機(jī)器學(xué)習(xí)方法，如決策樹、支持向量機(jī)、樸素貝葉斯及深度學(xué)習(xí)方法等［1-3］，樣本相似性度量在這些方法中均起著至關(guān)重要的作用?？墒牵@些實(shí)際問題涉及的樣本，如蛋白質(zhì)、基因及藥物等，通常具有不同維度。然而，大量現(xiàn)有經(jīng)典相似性度量，如曼哈頓距離、歐幾里得距離、切比雪夫距離及余弦距離等，均僅適用于相同維度樣本。因此，無法通過經(jīng)典相似性度量方法來度量不同維度樣本相似性。

為了克服這些困難，SAW 等［4］提出了一種無對(duì)齊方法，從樣本序列角度來度量不同維度樣本相似性。無對(duì)齊方法通常分兩步來度量樣本序列相似性：第一步，將樣本序列轉(zhuǎn)換為固定長(zhǎng)度的特征向量；第二步，以這些提取的特征向量相似性來衡量原始樣本序列相似性。在這個(gè)過程中，特征提取對(duì)無對(duì)齊方法的準(zhǔn)確性起著關(guān)鍵性的作用，但是從原始數(shù)據(jù)提取有效特征并非容易實(shí)現(xiàn)。目前，使用描述符來獲取固定長(zhǎng)度特征向量是一種有效方法。FAN 等［5］通過組合多種已有描述符提出了一種有效描述符，來度量蛋白質(zhì)序列相似性?？墒?，描述符的設(shè)計(jì)或定義通常不是一件容易的事，而且容易丟失一些不確定是否有用的信息［6-8］。

同時(shí)，也存在一些方法從樣本三維結(jié)構(gòu)角度來度量不同維度樣本相似性。樣本三維結(jié)構(gòu)通常比樣本序列包含更多信息，樣本三維結(jié)構(gòu)由構(gòu)成其分子的原子空間分布決定。因此，可通過原子空間分布相似性來衡量樣本三維結(jié)構(gòu)相似性。ANKERST等［9］將蛋白質(zhì)空間均勻劃分，并生成每個(gè)區(qū)域的統(tǒng)計(jì)信息，從而將蛋白質(zhì)的三維結(jié)構(gòu)轉(zhuǎn)化為形狀直方圖。HU 等［10］根據(jù)蛋白質(zhì)分子結(jié)構(gòu)的分形特征，提出了描述蛋白質(zhì)三維結(jié)構(gòu)的體積分形參數(shù)。AKUTSU［11］根據(jù)所比較蛋白質(zhì)對(duì)的骨架在空間中可以對(duì)齊的程度，衡量了兩者的相似性，在此過程中，蛋白質(zhì)結(jié)構(gòu)的骨架坐標(biāo)被嚴(yán)格平移和旋轉(zhuǎn)，并利用RMSD 方法能使其整體結(jié)構(gòu)在另一蛋白質(zhì)骨架上最大重疊。這些方法的關(guān)鍵是提取樣本結(jié)構(gòu)中空間旋轉(zhuǎn)和平移不變的特征。這個(gè)特征量本身可以是幾何、拓?fù)浠蚱渌c空間位置無關(guān)的生物信息。但是，無論從哪個(gè)方面提取特征，都有可能丟失一些關(guān)鍵信息。為了克服這些不足，CHEN 等［12］最近通過將樣本三維結(jié)構(gòu)轉(zhuǎn)化為圖，并引入新的矩陣克羅內(nèi)克積（p，m）-范數(shù)，從而通過圖核、矩陣克羅內(nèi)克積（p，m）-范數(shù)來度量藥物之間的相似性，進(jìn)行藥物發(fā)現(xiàn)。

本文在CHEN 等［12］近期工作的基礎(chǔ)上，基于由著名非線性系統(tǒng)控制理論專家程代展研究員引入的Cheng-范數(shù)，提出一種不同維度樣本相似性度量方法。該方法的基本思路是：將樣本三維結(jié)構(gòu)轉(zhuǎn)化為圖，并給出圖對(duì)應(yīng)的二維矩陣表示，通過基于Cheng-范數(shù)定義的矩陣相似度來度量樣本相似性。同時(shí)，以蛋白質(zhì)功能聚類為例，通過該樣本相似性度量方法，分別基于蛋白質(zhì)加權(quán)圖對(duì)應(yīng)的加權(quán)鄰接矩陣和加權(quán)拉普拉斯矩陣對(duì)蛋白質(zhì)樣本進(jìn)行相似性度量，從而采用層次聚類算法對(duì)其進(jìn)行功能聚類，以驗(yàn)證該相似性度量方法的有效性。該方法采用了圖表示，能夠保留樣本的結(jié)構(gòu)信息，而且相比于矩陣克羅內(nèi)克積（p，m）-范數(shù)，矩陣Cheng-范數(shù)更容易被計(jì)算。

1 基本符號(hào)與術(shù)語

在介紹基本術(shù)語之前，首先給出本文中經(jīng)常用到的一些符號(hào)：

1）[m，n]表示正整數(shù)m 與n 的最小公倍數(shù)，并用(m，n)表示正整數(shù)m與n的最大公因數(shù)；

2）?表示矩陣的克羅內(nèi)克（Kronecker）積（也稱張量積）；

3）1n表示n維全1列向量(1，1，…，1)T；

4）In表示n階單位方陣；5）(x，y)表示向量x和y的數(shù)量積（也稱內(nèi)積）。接下來，介紹由程代展研究員定義的一些基本術(shù)語［13-15］。

1.1 Cheng-MV積

1.2 Cheng-內(nèi)積與Cheng-范數(shù)

設(shè)x是m維實(shí)向量，則x的Cheng-范數(shù)定義為

2 基于Cheng-范數(shù)的相似性度量方法

本文所呈現(xiàn)的樣本相似性度量方法的基本思路是：將樣本三維結(jié)構(gòu)轉(zhuǎn)化為圖，并給出圖對(duì)應(yīng)的二維矩陣表示，通過基于Cheng-范數(shù)定義的矩陣相似度來度量樣本相似性。

為了定義矩陣相似度，通過將不同階數(shù)方陣映射成相同階數(shù)方陣的思想，基于Cheng-范數(shù)，首先引入不同階數(shù)方陣的距離。

定義1 設(shè)A 和B 分別是階數(shù)為n 和m 的實(shí)方陣，則A和B的距離定義為

該樣本相似性度量方法通過不同階數(shù)方陣的相似度，來度量相應(yīng)不同維度樣本的相似性。

3 蛋白質(zhì)功能聚類

在蛋白質(zhì)功能預(yù)測(cè)中，比如想預(yù)測(cè)給定蛋白質(zhì)是否是一種酶，通常采用的方法是通過尋找具有相似序列、結(jié)構(gòu)或化學(xué)性質(zhì)的蛋白質(zhì)來推斷給定蛋白質(zhì)功能。一種非常有效的方法是將蛋白質(zhì)的三維結(jié)構(gòu)轉(zhuǎn)化為其對(duì)應(yīng)的表示圖（如圖1 所示），并通過圖的相似性來度量蛋白質(zhì)的相似性［16］。

圖1 蛋白質(zhì)103L的三維結(jié)構(gòu)及表示圖

本實(shí)驗(yàn)從蛋白質(zhì)數(shù)據(jù)庫（PDB）［17］選取60 個(gè)蛋白質(zhì)樣本，其中30 個(gè)為O-糖基水解酶，以XXXL 格式命名，即103L、104L；其余30 個(gè)為氧轉(zhuǎn)運(yùn)蛋白，主要分為兩部分（也有個(gè)別例外情形，如1YOG）：一部分以XXXM 格式命名，即105M、107M，另一部分以2ZXX 格式命名，即2ZSN、2ZT0。進(jìn)一步，將蛋白質(zhì)樣本轉(zhuǎn)化為圖，并給出其矩陣表示。通過定義的不同階數(shù)方陣相似度，來度量相應(yīng)不同維度樣本相似性，并對(duì)選取的60 個(gè)蛋白質(zhì)樣本進(jìn)行功能聚類，以聚類結(jié)果來驗(yàn)證該相似性度量方法的有效性。

3.1 蛋白質(zhì)結(jié)構(gòu)的二維矩陣表示

本實(shí)驗(yàn)從蛋白質(zhì)結(jié)構(gòu)圖分析（NAPS）［18］獲取這60個(gè)蛋白質(zhì)的加權(quán)圖［19］。在蛋白質(zhì)加權(quán)圖中，由Cα原子表示的氨基酸殘基被視為圖的節(jié)點(diǎn)；若一對(duì)Cα原子之間的距離在上、下閾值范圍內(nèi)（0~7?），則在這對(duì)節(jié)點(diǎn)之間連一條邊；定義邊權(quán)重為所連接Cα原子對(duì)歐氏距離的倒數(shù)。圖1B 展示了蛋白質(zhì)103L 對(duì)應(yīng)的圖。通過蛋白質(zhì)結(jié)構(gòu)圖分析（NAPS），可獲得這60 個(gè)蛋白質(zhì)加權(quán)圖的全局參數(shù)信息。在下列實(shí)驗(yàn)中，首先以這60個(gè)蛋白質(zhì)加權(quán)圖的加權(quán)鄰接矩陣作為其二維矩陣表示，來度量相應(yīng)不同維度樣本相似性，并進(jìn)行功能聚類。

3.2 蛋白質(zhì)功能層次聚類

不難看到，不同維度蛋白質(zhì)的加權(quán)圖對(duì)應(yīng)著不同階數(shù)加權(quán)鄰接矩陣，例如134L 水解酶對(duì)應(yīng)著130 × 130 的加權(quán)鄰接矩陣，而107M 氧轉(zhuǎn)運(yùn)蛋白對(duì)應(yīng)著154 × 154 的加權(quán)鄰接矩陣。同時(shí)，不同階數(shù)加權(quán)鄰接矩陣無法確定樣本的中心，從而無法計(jì)算聚類簇之間的中心距離，但是可以將2 個(gè)聚類簇中樣本間的平均距離、最大距離或最小距離作為聚類簇之間的距離。因此，本實(shí)驗(yàn)采取層次聚類算法對(duì)選取的60個(gè)蛋白質(zhì)樣本進(jìn)行功能聚類。

根據(jù)定義1 計(jì)算60 個(gè)蛋白質(zhì)樣本對(duì)應(yīng)的距離矩陣，并繪制該距離矩陣的熱圖，如圖2A 所示。從圖2A 可以看出：通過適當(dāng)調(diào)整順序，樣本大致分為3 個(gè)簇，即名為XXXM 的氧轉(zhuǎn)運(yùn)蛋白、名為2ZXX 的氧轉(zhuǎn)運(yùn)蛋白和名為XXXL 的水解酶。然后，通過兩聚類簇中樣本間的平均距離作為聚類簇之間的距離對(duì)樣本集進(jìn)行層次聚類，并繪制聚類樹，如圖2B所示。從圖2B 可以看出：選擇距離為2.006 作為閾值，產(chǎn)生4 個(gè)聚類簇。表1 展示了4 個(gè)聚類簇的聚類結(jié)果，與圖2A 所示結(jié)果保持一致。

表1 聚類樹產(chǎn)生的4個(gè)聚類簇情況表

以兩聚類簇中樣本間的最大距離作為聚類簇之間的距離，可將樣本集聚成如圖3A所示的2個(gè)簇，其中一個(gè)簇由表1中第Ⅰ簇和第Ⅱ簇聚合而成；另一個(gè)簇由表1中第Ⅲ簇和第Ⅳ簇聚合而成。將2個(gè)聚類簇的結(jié)果與真實(shí)標(biāo)簽進(jìn)行比較，并計(jì)算其Jaccard 系數(shù)、FM指標(biāo)和Rand指標(biāo)，如表2所示。聚類理論表明：其Jaccard系數(shù)、FM指標(biāo)和Rand指標(biāo)越接近1，聚類結(jié)果越理想。綜合3個(gè)指標(biāo)，本次聚類結(jié)果并不很理想。

由于鄰接矩陣包含較少信息，無法將表1 中第Ⅰ簇和第Ⅳ簇聚合成一個(gè)新簇以代表水解酶，也無法將表1中第Ⅱ簇和第Ⅲ簇聚合成另一個(gè)新簇以代表氧轉(zhuǎn)運(yùn)蛋白。進(jìn)一步，取樣本加權(quán)圖對(duì)應(yīng)的加權(quán)拉普拉斯矩陣作為其矩陣表示，并通過兩聚類簇中樣本間的平均距離作為聚類簇之間的距離進(jìn)行層次聚類，將樣本集聚類為2 個(gè)簇。圖3B 展示了其聚類結(jié)果，表2 也給出了其對(duì)應(yīng)的聚類指標(biāo)，其Jaccard 系數(shù)、FM 指標(biāo)和Rand 指標(biāo)均達(dá)到1。聚類結(jié)果表明：基于樣本加權(quán)圖對(duì)應(yīng)的加權(quán)拉普拉斯矩陣，以兩聚類簇中樣本間的平均距離作為聚類簇之間的距離進(jìn)行層次聚類能得到理想的聚類結(jié)果。

表2 層次聚類各指標(biāo)信息表

圖2 樣本距離矩陣熱圖及基于鄰接矩陣以樣本間平均距離聚類對(duì)應(yīng)的聚類樹

圖3 基于鄰接矩陣（拉普拉斯矩陣）以樣本間最大距離（平均距離）聚類對(duì)應(yīng)的聚類樹

最后，將本文提出的相似性度量與序列相似性度量、結(jié)構(gòu)相似性度量進(jìn)行對(duì)比。通過于祥田［20］提供的描述符獲得56 維特征向量，并用歐幾里得距離度量這60 個(gè)蛋白質(zhì)樣本的序列相似度。同時(shí)，用RMSD 方法度量這60 個(gè)蛋白質(zhì)樣本的結(jié)構(gòu)相似度。圖4 展示了其聚類結(jié)果，表2 也給出了其對(duì)應(yīng)的聚類指標(biāo)。對(duì)比發(fā)現(xiàn)：本文基于樣本加權(quán)圖對(duì)應(yīng)的加權(quán)拉普拉斯矩陣所定義的不同維度樣本相似性度量是目前最有效的相似性度量方法。

圖4 基于序列相似性和結(jié)構(gòu)相似性聚類對(duì)應(yīng)的聚類樹

4 結(jié)論

本文基于Cheng-范數(shù)，提出一種不同維度樣本相似性度量新方法。同時(shí)，以蛋白質(zhì)功能聚類為例，通過該方法分別基于蛋白質(zhì)加權(quán)圖對(duì)應(yīng)的加權(quán)鄰接矩陣和加權(quán)拉普拉斯矩陣對(duì)蛋白質(zhì)樣本進(jìn)行相似性度量，進(jìn)一步采用層次聚類算法對(duì)其進(jìn)行聚類。通過綜合分析3個(gè)聚類指標(biāo)及聚類樹，可以得出：基于樣本加權(quán)圖對(duì)應(yīng)的加權(quán)拉普拉斯矩陣，以兩聚類簇中樣本間的平均距離作為聚類簇之間的距離進(jìn)行層次聚類能夠按照蛋白質(zhì)功能給出理想的聚類結(jié)果，充分表明了該相似性度量方法切實(shí)有效。

本文對(duì)蛋白質(zhì)樣本進(jìn)行功能聚類時(shí)僅采用了樣本加權(quán)圖對(duì)應(yīng)的加權(quán)鄰接矩陣和加權(quán)拉普拉斯矩陣作為其矩陣表示。實(shí)際上，樣本加權(quán)圖對(duì)應(yīng)的點(diǎn)特征矩陣和邊特征矩陣包含更多樣本結(jié)構(gòu)信息。如果對(duì)多種功能的樣本進(jìn)行功能聚類時(shí)，采用樣本加權(quán)圖對(duì)應(yīng)的點(diǎn)特征矩陣和邊特征矩陣作為其矩陣表示，可能取得更理想的聚類結(jié)果。由于本文采用樣本加權(quán)圖對(duì)應(yīng)的加權(quán)拉普拉斯矩陣作為其矩陣表示，已經(jīng)取得理想的聚類結(jié)果，所以不再考慮將其他矩陣作為其矩陣表示。