張汝昌，邱 杰，王明堂，陳慶鋒*

(1. 廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004； 2. 玉林師范學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 玉林 537000)

蛋白質(zhì)是由氨基酸以“脫水縮合”的方式組成的多肽鏈經(jīng)過盤曲折疊形成的具有一定空間結(jié)構(gòu)的物質(zhì)。人類的許多疾病都與某些蛋白質(zhì)功能有關(guān)。對(duì)蛋白質(zhì)結(jié)構(gòu)和功能的深入研究，能夠?yàn)橹委熑祟愐呻y病癥提供更好的助力[1]。蛋白質(zhì)的結(jié)構(gòu)與其功能密切相關(guān)，結(jié)構(gòu)決定功能已經(jīng)成為生物學(xué)家的共識(shí)。假設(shè)結(jié)構(gòu)和功能在進(jìn)化上是連續(xù)的，由蛋白質(zhì)結(jié)構(gòu)之間的相似關(guān)系，可以讓科學(xué)家推斷或預(yù)測(cè)新發(fā)現(xiàn)的與已知蛋白質(zhì)結(jié)構(gòu)相似的蛋白質(zhì)的功能[2]。結(jié)構(gòu)相似的蛋白質(zhì)其生物功能也往往相似，最終決定蛋白質(zhì)功能的是蛋白質(zhì)的空間自然折疊的三維形狀[3]。蛋白質(zhì)的三維結(jié)構(gòu)目前主要的測(cè)定方法有：X射線晶體衍射、電子晶體學(xué)電鏡三維重構(gòu)以及核磁共振[4]等。定量地比較2個(gè)蛋白質(zhì)三維結(jié)構(gòu)來評(píng)估它們的相似性是生物信息學(xué)里一個(gè)重大的挑戰(zhàn)，成功的比較可以為結(jié)構(gòu)生物學(xué)、細(xì)胞生物學(xué)和生物化學(xué)中的一些重要問題提供答案[5-6]。隨著PDB(protein data bank)中蛋白質(zhì)結(jié)構(gòu)的數(shù)量逐年增大，蛋白質(zhì)之間的網(wǎng)絡(luò)關(guān)系變得越來越復(fù)雜[7-8]，如何有效利用現(xiàn)在已知的數(shù)據(jù)去預(yù)測(cè)未知蛋白質(zhì)的功能及對(duì)其進(jìn)行分類已經(jīng)成為一個(gè)新的難題。

利用計(jì)算機(jī)科學(xué)分析該問題已是當(dāng)前的一個(gè)熱點(diǎn)?；跀?shù)字化技術(shù)計(jì)算分類蛋白質(zhì)結(jié)構(gòu)的方法主要有：SCOP[9](structural classification of proteins)、CATH[10](class, architecture, topology and homologous superfamily)、TM-score[11-12]、FSSP[13](families of structurally similar proteins)、DALILITE[14]等。當(dāng)前，通過這些方法已經(jīng)獲得了一些蛋白質(zhì)結(jié)構(gòu)分類的數(shù)據(jù)庫(kù)。除了上述方法，還有通過結(jié)構(gòu)對(duì)齊算法分類蛋白質(zhì)結(jié)構(gòu)的方法，如CE[15]、VAST[16]、SSAP[17]、FAST[18]等，最早提出并被廣泛應(yīng)用的是RMSD方法[19]。大部分對(duì)齊算法時(shí)間復(fù)雜度較高，在大規(guī)模數(shù)據(jù)集上難以應(yīng)用。當(dāng)前，對(duì)預(yù)測(cè)未知蛋白質(zhì)功能和分類的主流評(píng)價(jià)指標(biāo)是模板建模評(píng)分(template modeling score, TM-score)，它是衡量2個(gè)具有不同三級(jí)結(jié)構(gòu)的蛋白質(zhì)且與蛋白質(zhì)的大小無關(guān)的全局折疊相似性度量。TM-score是一個(gè)標(biāo)準(zhǔn)化的度量，其值在[0, 1]內(nèi)，其值大于0.5時(shí)說明在SCOP/CATH中有相似折疊性，等于1時(shí)，這2個(gè)蛋白質(zhì)是一致的[20]。為了減少計(jì)算復(fù)雜度，一些不依賴結(jié)構(gòu)對(duì)比的方法被提出，如基于圖理論的方法[21-22]、基于Cα距離矩陣的方法[23]。為了簡(jiǎn)化對(duì)三維骨架進(jìn)行空間配準(zhǔn)操作的復(fù)雜問題，Taylor等[24]將蛋白質(zhì)的空間坐標(biāo)轉(zhuǎn)化為距離矩陣的量化表示。在此基礎(chǔ)上，Choi等[25]提出了一種基于局部特征頻率的計(jì)算蛋白質(zhì)相似性的方法，該方法把蛋白質(zhì)結(jié)構(gòu)的Cα距離矩陣劃分出許多具有重疊元素的子矩陣，每一個(gè)子矩陣都代表蛋白質(zhì)三維結(jié)構(gòu)在空間中的局部特征，比如α螺旋結(jié)構(gòu)、β折疊結(jié)構(gòu)。從這些大量子矩陣所代表的蛋白質(zhì)局部特征中做聚類分析，劃分成k類局部特征的子矩陣集合，由此將每個(gè)蛋白質(zhì)結(jié)構(gòu)抽象成k維歐氏空間的特征點(diǎn)，求出發(fā)生k類局部特征的頻率(LFF)，每個(gè)蛋白質(zhì)的距離矩陣在做相似性比較之前可以先轉(zhuǎn)成LFF，通過計(jì)算LFF之間的距離間接得到蛋白質(zhì)的相似性，這樣計(jì)算得出的結(jié)果和SCOP的蛋白質(zhì)結(jié)構(gòu)分類具有很好的一致性。但是這種方法主要是靠人工枚舉選擇蛋白質(zhì)局部特征的大小和聚類中心點(diǎn)的數(shù)量，計(jì)算量大的同時(shí)也未必得到最好的局部特征。

本文對(duì)LFF做改進(jìn)，提出自適應(yīng)數(shù)據(jù)集的局部頻率向量ALFF。首先，為了選擇更好的蛋白質(zhì)結(jié)構(gòu)局部特征來計(jì)算蛋白質(zhì)結(jié)構(gòu)相似性，引進(jìn)了OTSU算法[26]，該算法能確保選出來的子矩陣在不同蛋白質(zhì)之間有更大的區(qū)分性，提高計(jì)算的相似度結(jié)果；同時(shí)還使用MeanShift[27]代替k-medoids做聚類分析，其可以根據(jù)數(shù)據(jù)集的特點(diǎn)，自動(dòng)計(jì)算出簇的數(shù)量，而不需要人工參與。其次，在數(shù)據(jù)預(yù)處理中，將冗余的子矩陣去除，減少了接近一半的計(jì)算量。最后，本文隨機(jī)選擇多組SCOP的蛋白質(zhì)結(jié)構(gòu)數(shù)據(jù)進(jìn)行相似性比較，實(shí)驗(yàn)結(jié)果顯示：在蛋白質(zhì)結(jié)構(gòu)class、fold、superfamily以及family分類層面上，ALFF比LFF有更好的一致性；和TM-score評(píng)分比較，ALFF在蛋白質(zhì)結(jié)構(gòu)相似性上有更好的結(jié)果，其準(zhǔn)確性有明顯提升。

1 材料和方法

1.1 局部特征頻率向量(LFF)

Choi等[25]在3 792個(gè)非冗余折疊結(jié)構(gòu)中隨機(jī)選出100個(gè)蛋白質(zhì)，首先，對(duì)每個(gè)蛋白質(zhì)p計(jì)算其中任意2個(gè)Cα原子之間的距離，得到一個(gè)對(duì)稱的距離矩陣Dp={dp(i,j):i,j=1,2,…,sp}，式中dp(i,j)表示該蛋白質(zhì)的第i和第j個(gè)Cα原子之間的歐氏距離，sp表示Cα原子個(gè)數(shù)。這個(gè)矩陣用二維信息表示三維的折疊結(jié)構(gòu)，也和蛋白質(zhì)的骨架一一對(duì)應(yīng)，在一定程度上可以代表這個(gè)蛋白質(zhì)的整體結(jié)構(gòu)。接著，使用滑動(dòng)窗口(窗口大小為m的矩陣)的方式，在距離矩陣上劃分出子矩陣集合

(1)

(2)

1.2 自適應(yīng)的局部特征頻率向量(ALFF)

Choi等[25]通過重疊子矩陣的聚類分析，發(fā)現(xiàn)蛋白質(zhì)三維結(jié)構(gòu)可以使用k(k=100)種m×m(m=10)的特征子矩陣的發(fā)生頻率來表示，這種方法計(jì)算出來的結(jié)果與SCOP數(shù)據(jù)庫(kù)對(duì)蛋白質(zhì)結(jié)構(gòu)的分類具有很好的一致性。然而，這個(gè)方法也有一些缺陷，比如參數(shù)m和k的選擇，m的大小和所選蛋白質(zhì)的局部特征密切相關(guān)，而k也會(huì)根據(jù)數(shù)據(jù)集的不同有不一樣的結(jié)果。Choi等[25]從SCOP數(shù)據(jù)庫(kù)的3 792個(gè)非冗余折疊結(jié)構(gòu)中隨機(jī)選擇了100個(gè)，利用有限枚舉法(m=8，10，12，16；k=50，100，150，200，250，300)得到實(shí)驗(yàn)最優(yōu)取值m=10，k=100。這樣選擇參數(shù)有以下不足之處：1)100個(gè)非冗余結(jié)構(gòu)不能完整表征已經(jīng)解析的所有結(jié)構(gòu)和特點(diǎn)，如果實(shí)驗(yàn)中換了一組數(shù)據(jù)，那么由于蛋白質(zhì)的結(jié)構(gòu)不同，LFF根據(jù)這些參數(shù)(m=10，k=100)得到的局部特征很有可能不適合表示新的數(shù)據(jù)，所以從中提取的特征子矩陣更適用于描述與此100種結(jié)構(gòu)類似的結(jié)構(gòu)，而不適用于這100種結(jié)構(gòu)以外的結(jié)構(gòu)；2)有限枚舉法在取值的優(yōu)化上具有明顯的局限性，因?yàn)橛?jì)算復(fù)雜度較大，還需要人工畫圖觀察參數(shù)變化以選出最優(yōu)；3)由于距離矩陣是對(duì)稱的，所選出來的子矩陣在結(jié)構(gòu)上存在冗余，實(shí)驗(yàn)忽略了子矩陣沿著對(duì)角線對(duì)稱等效分布的情況，可能將等效的子矩陣歸屬到不同的特征子矩陣。基于這3點(diǎn)不足，本文在Choi等[25]的LFF方法上做了一些改進(jìn)，提出可以自動(dòng)適應(yīng)數(shù)據(jù)集的LFF算法，即ALFF。ALFF能夠根據(jù)所選擇的數(shù)據(jù)集選出最好的m和k這2個(gè)參數(shù)，而不需要花大量時(shí)間通過枚舉來手工選擇參數(shù)。ALFF算法先采用OTSU算法得到較優(yōu)的子矩陣，其大小為m，再使用MeanShift聚類算法得到局部特征的數(shù)量k，最后在做相似性比較前對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并去除對(duì)稱矩陣等效的子矩陣。

1.2.1 最大類間方差法(OTSU)

OTSU是日本學(xué)者大津于1979年提出的一種自適應(yīng)的閾值確定方法[26]。在計(jì)算機(jī)視覺和圖像處理中，OTSU算法被用來對(duì)基于聚類的圖像進(jìn)行二值化。該算法按圖像的灰度特性，將圖像分成背景和目標(biāo)2部分。背景和目標(biāo)之間的類間方差越大，說明構(gòu)成圖像的2部分的差別越大，當(dāng)部分目標(biāo)錯(cuò)分為背景或部分背景錯(cuò)分為目標(biāo)時(shí)都會(huì)導(dǎo)致2部分差別變小。因此，使類間方差最大的分割意味著錯(cuò)分概率最小[28]。由此，本文將OTSU算法拓展到ALFF算法參數(shù)m的優(yōu)化上，對(duì)于所選擇的蛋白質(zhì)數(shù)據(jù)集，劃分出來的子矩陣是否能夠很好地表示蛋白質(zhì)的局部特征，關(guān)鍵在于子矩陣大小m的確定。假定所選擇出來的所有局部特征能使這些蛋白質(zhì)區(qū)分度達(dá)到最大，使得蛋白質(zhì)結(jié)構(gòu)的類間方差最大，則對(duì)應(yīng)的局部特征是最合適代表蛋白質(zhì)的局部結(jié)構(gòu)。在對(duì)蛋白質(zhì)數(shù)據(jù)劃分子矩陣的時(shí)候，m的取值范圍是[2,L]，其中L是所有蛋白質(zhì)的距離矩陣中最小的維度。記ni表示子矩陣維度為i的數(shù)量，N=n2+n3+…+nL，則子矩陣維度服從概率分布

(3)

現(xiàn)在根據(jù)假定的閾值t，把子矩陣分為2類：X1記為子矩陣維度在[2,…,t]，X2記為子矩陣維度在[t+1,t+2,…,L]，然后在以上子矩陣的概率分布下，有：

(4)

(5)

背景和目標(biāo)的灰度值分別是：

(6)

(7)

2～L的累計(jì)值為

ρ=λ1×ρ1+λ2×ρ2。

(8)

根據(jù)以上關(guān)系，類間方差有

σ=λ1×(ρ1-ρ)2+λ2×(ρ2-ρ)2。

(9)

當(dāng)類間方差σ取得最大時(shí)，對(duì)應(yīng)的t即為最優(yōu)，所以

(10)

本文后面會(huì)用多組實(shí)驗(yàn)驗(yàn)證OTSU算法選擇參數(shù)m的有效性。

1.2.2 MeanShift

在LFF方法中，聚類的簇的數(shù)量k，即局部特征數(shù)量，同樣是一個(gè)比較重要的參數(shù)。LFF使用有限枚舉法遍歷一定數(shù)量的k值，然后人工選擇認(rèn)為比較好的參數(shù)k，如果要枚舉的m、k的個(gè)數(shù)分別為nm、nk，那就一共需要做nm×nk次聚類實(shí)驗(yàn)，這是一個(gè)很耗費(fèi)時(shí)間的過程。本文方法是在蛋白質(zhì)結(jié)構(gòu)中劃分了大量有重疊結(jié)構(gòu)的子矩陣，如何選擇k才能使得最后得到的頻率向量能準(zhǔn)確地反映蛋白質(zhì)的結(jié)構(gòu)是一個(gè)核心問題，當(dāng)k的數(shù)量未知時(shí)，枚舉法也很難選出好的結(jié)果。因此本文目標(biāo)是能找到一種能夠自動(dòng)發(fā)現(xiàn)聚類中心點(diǎn)的算法，不需要人為干預(yù)蛋白質(zhì)局部特征的數(shù)量k，而MeanShift方法就是能滿足上述需求的一個(gè)算法。MeanShift主要思想是將數(shù)據(jù)特征空間視為先驗(yàn)概率密度函數(shù)，對(duì)于輸入的數(shù)據(jù)被認(rèn)為是一組滿足某種概率分布的樣本點(diǎn)，所以特征空間中數(shù)據(jù)最密集的地方對(duì)應(yīng)概率密度最大的地方，概率密度的質(zhì)心就可以被視為概率密度函數(shù)的局部最優(yōu)值，即所求的聚類中心點(diǎn)。

圖1 MeanShift收斂過程Fig. 1 Convergence process of MeanShift

對(duì)于每一個(gè)樣本點(diǎn)，以它為中心的某個(gè)范圍所有樣本的均值作為每次迭代新的中心，窗口的重心都向數(shù)據(jù)更密集的地方移動(dòng)[29]。圖1直觀地描述了MeanShift一次移動(dòng)過程，圖中的大圓圈代表當(dāng)前的限制條件，箭頭是本次迭代所取得的平均偏移向量?？梢钥闯?，每次的中心點(diǎn)都會(huì)向數(shù)據(jù)密集的地方移動(dòng)，直到算法收斂。對(duì)于給定d維空間Rd中的中心點(diǎn)oi，第l次迭代的坐標(biāo)更新由式(11)給出

(11)

給定N(oi)為中心點(diǎn)oi在距離h內(nèi)所有的近鄰點(diǎn)，Mh(x)為每個(gè)質(zhì)心x計(jì)算的平均移位向量，其指向點(diǎn)密度最大增加的區(qū)域，有效地將質(zhì)心更新為其鄰域內(nèi)樣本的平均值，MeanShift向量的基本形式為

(12)

式中K為核函數(shù)。在MeanShift算法中引入核函數(shù)的目的是使得隨著樣本與被偏移點(diǎn)的距離不同，其偏移量對(duì)均值偏移向量的貢獻(xiàn)也不同。核函數(shù)常被用在機(jī)器學(xué)習(xí)中，可以減少計(jì)算量。ALFF使用的是高斯核，定義為

(13)

最終，所有類的數(shù)量就是需要找的k值。使用MeanShift算法主要有2個(gè)優(yōu)勢(shì)：1)對(duì)任意形狀的數(shù)據(jù)都可以較好地聚類；2)根據(jù)數(shù)據(jù)的分布特點(diǎn)自動(dòng)找到比較合適的聚類數(shù)量。

1.2.3 ALFF算法步驟

基于自適應(yīng)的局部特征頻率向量計(jì)算蛋白質(zhì)三維結(jié)構(gòu)的相似性算法步驟如算法1中偽代碼所示。算法的輸入有：1)所有蛋白質(zhì)的Cα距離矩陣Dmats；2)MeanShift中近鄰范圍參數(shù)h；3)MeanShift收斂閾值ε。算法輸出是一個(gè)蛋白質(zhì)相似性矩陣S。算法首先初始化參數(shù)，使用變量m遍歷[2,L]區(qū)間，L是長(zhǎng)度最小的蛋白質(zhì)的Cα數(shù)量；然后根據(jù)m從距離矩陣劃分出所有子矩陣，計(jì)算對(duì)應(yīng)的類間方差并選出方差最大的對(duì)應(yīng)的子矩陣大小m*；最后通過MeanShift對(duì)所有的m*×m*的子矩陣聚成k類，并統(tǒng)計(jì)每個(gè)蛋白質(zhì)的子矩陣在k個(gè)中心點(diǎn)發(fā)生的頻率得到ALFF，通過ALFF使用余弦相似性計(jì)算蛋白質(zhì)相似度。

算法1ALFF計(jì)算蛋白質(zhì)相似性。

輸入：蛋白質(zhì)的Cα距離矩陣Dmats；近鄰范圍h；MeanShift收斂閾值ε。

輸出：蛋白質(zhì)相似性矩陣S。

1. 初始化：L=min_dimensional(Dmats)； // 獲取距離矩陣的最小維度作為上限

2.m*=0 // 最優(yōu)的子矩陣維度

3. sub_mats={} // 子矩陣集合

4. max_σ=-∞ // 當(dāng)前最大方法

5. form=2→Ldo

6. sub_mats=get_submats(Dmats,m) // 根據(jù)子矩陣的大小m劃分子矩陣

7.σ=get_variance (sub_mats) // 計(jì)算子矩陣為m的類間方差

8. ifσ>max_σthen

9. max_σ=σ

10.m*=m

11. end

12. end

13.Xnew=X=get_submats(Dmats,m*) // 使用m*劃分子矩陣

14. repeat

15.C=0 // 每次迭代的cost為0

16. fori=0→n-1 do // 遍歷每個(gè)樣本點(diǎn)

17.x=Xnew[i]

18.N(x)=get_ neighbors(x,h) // 對(duì)子矩陣x求最近鄰

20.C=C+x-Mx// 更新cost

21.Xnew[i]=Mx

22. end

23. untilC<ε

24. ALFF=get_frequency(Xnew,X) //用聚類結(jié)果Xnew和原始樣本點(diǎn)X求ALFF

25.S=cos_sim(ALFF) // 計(jì)算余弦相似性。

2 實(shí)驗(yàn)結(jié)果及討論

2.1 局部特征大小分析

本文通過隨機(jī)選取蛋白質(zhì)數(shù)據(jù)做實(shí)驗(yàn)，分析OTSU算法的計(jì)算結(jié)果。SCOP (https://scop.berkeley.edu)是一個(gè)根據(jù)大多數(shù)結(jié)構(gòu)已知的蛋白質(zhì)的結(jié)構(gòu)和進(jìn)化關(guān)系對(duì)其結(jié)構(gòu)域進(jìn)行分級(jí)的數(shù)據(jù)庫(kù)，在最新的發(fā)行版2.07中，從所有的折疊結(jié)構(gòu)中抽取了14 401個(gè)具有代表性結(jié)構(gòu)的蛋白質(zhì)作為測(cè)試數(shù)據(jù)。在測(cè)試數(shù)據(jù)中隨機(jī)抽取3組蛋白質(zhì)，對(duì)比可以發(fā)現(xiàn)，盡管每組數(shù)據(jù)的最優(yōu)m的大小有一定差異，但是通過圖2可以看到蛋白質(zhì)類間方差都是先遞增后遞減的。圖2有3組蛋白質(zhì)數(shù)據(jù)，每一組都是100個(gè)蛋白質(zhì)，橫坐標(biāo)是劃分子矩陣的大小m，縱坐標(biāo)是利用OTSU算法通過m得到的類間方差σ，當(dāng)使用不同維度的滑動(dòng)窗口劃分出子矩陣時(shí)，類間方差達(dá)到最大時(shí)對(duì)應(yīng)的維度就是最優(yōu)的m，即m*。圖2中3組數(shù)據(jù)g1、g2、g3的m*分別是22、18、26。圖3中，實(shí)驗(yàn)選擇了1 000組蛋白質(zhì)，使用OTSU算法計(jì)算m*，畫出頻率分布直方圖，可以發(fā)現(xiàn)m*分布是有規(guī)律的，這1 000組蛋白質(zhì)的m*大多數(shù)分布在[8, 30]，其中[14, 26]數(shù)量最多，所以理論上任意數(shù)據(jù)集都可以用OTSU算法計(jì)算m*。

圖2 m*和類間方差的關(guān)系Fig. 2 Relationship between m* and the variance between classes

圖3 最優(yōu)m*值的分布情況Fig. 3 Distribution of optimal m*

2.2 算法對(duì)比

為了驗(yàn)證OTSU和MeanShift算法計(jì)算參數(shù)最優(yōu)值的有效性，本文隨機(jī)選擇5組實(shí)驗(yàn)數(shù)據(jù)，并與LFF、ALFF_OTSU方法做對(duì)比實(shí)驗(yàn)，其中：ALFF_OTSU方法只使用OTSU優(yōu)化LFF的參數(shù)m，聚類方法和LFF一致，使用k-medoids聚類，k=100；LFF使用參數(shù)m=10，k=100；ALFF方法的參數(shù)m和k分別使用OTSU和MeanShift算法得出的最優(yōu)值。實(shí)驗(yàn)評(píng)估方法為重構(gòu)距離矩陣和原始距離矩陣的差異對(duì)比DME(distance matrix error)[25]。重構(gòu)距離矩陣的計(jì)算方法為：所有的子矩陣聚類完成后，得到k個(gè)中心點(diǎn)。對(duì)于每個(gè)蛋白質(zhì)最初的Cα距離矩陣，其每個(gè)子矩陣被該子矩陣的最近鄰(所在簇的中心點(diǎn))代替，如果替換過程中有重疊的地方，那么每次重疊的位置取兩者的平均數(shù)代替。

(14)

圖4 LFF、ALFF_OTSU和ALFF的DME比較Fig. 4 Comparison of DME of LFF, ALFF_OTSU and ALFF

經(jīng)過以上步驟，每個(gè)蛋白質(zhì)的三維結(jié)構(gòu)都會(huì)被表示成一個(gè)代表局部特征頻率的k維向量，通過這個(gè)特征頻率向量就可以計(jì)算蛋白質(zhì)的相似性，余弦相似度用向量空間中2個(gè)向量夾角的余弦值作為衡量2個(gè)個(gè)體間差異的大小。余弦值越接近1，表明夾角越接近0°。蛋白質(zhì)p1和p2的局部頻率向量分別是Vp1和Vp2，則它們的余弦相似度定義為

(15)

余弦值的范圍在0到1之間，值越大說明2個(gè)向量越相似。計(jì)算出的蛋白質(zhì)相似性結(jié)果可以和SCOP數(shù)據(jù)庫(kù)作比較，SCOP數(shù)據(jù)庫(kù)是公認(rèn)的蛋白質(zhì)結(jié)構(gòu)分類數(shù)據(jù)庫(kù)，表1展示了LFF、ALFF_OTSU和ALFF在SCOP的結(jié)構(gòu)分類上保持的一致性。

表1 在SCOP中層次分類一致性的比較

在表2中，通過ALFF方法選取了前10組相似度最高的蛋白質(zhì)對(duì)，在SCOP上尋找它們的共同祖先，共同祖先越相近，理論上相似度越高。為驗(yàn)證ALFF的有效性，用ALFF和LFF、TM-score做比較。其中，TM-score方法使用的是在網(wǎng)站https://zhanglab.ccmb.med.umich.edu/TM-score/上的公開服務(wù)。蛋白質(zhì)對(duì)的TM-score在[0, 0.17]之間，表示該蛋白質(zhì)對(duì)屬于隨機(jī)結(jié)構(gòu)，在[0.5, 1]之間則表示在相同的折疊下。

表2 ALFF的TOP10相似性結(jié)果和TM-score比較

表2中每組高得分用黑體標(biāo)注，可以看出，前4組蛋白質(zhì)在4種方法下都取得比較高的相似性分?jǐn)?shù)，它們的共同祖先是家族或者超家族，而后面除了第8組數(shù)據(jù)以外，其他組的TM-score都低于0.5，而這些蛋白質(zhì)都是有共同祖先的，TM-score在該5組數(shù)據(jù)中不適用。相比之下，ALFF和LFF在后6對(duì)蛋白質(zhì)中仍然有不錯(cuò)的相似性分?jǐn)?shù)，從總體得分上，ALFF略優(yōu)于LFF。值得注意的是第8組蛋白質(zhì)沒有共同祖先，ALFF和LFF也計(jì)算出了比較高的相似性，說明ALFF方法算出這對(duì)蛋白質(zhì)可能有比較多相似的局部特征盡管它們沒有共同的祖先。而ALFF_OTSU方法在這10組數(shù)據(jù)的相似性在ALFF和LFF之間，這證明了OTSU算法在選擇蛋白質(zhì)局部特征大小時(shí)的有效性，通過OTSU和MeanShift結(jié)合可見，ALFF方法是這幾個(gè)方法中最優(yōu)的。

在ALFF方法中，為了避免大量等效的子矩陣對(duì)實(shí)驗(yàn)結(jié)果造成影響，從距離矩陣劃分出子矩陣的時(shí)候只保留矩陣對(duì)角線上方的子矩陣，假設(shè)蛋白質(zhì)數(shù)量是N，蛋白質(zhì)p的距離矩陣維度是np，子矩陣的維度是m，那么N個(gè)蛋白質(zhì)劃分得到的子矩陣總數(shù)S為

(16)

根據(jù)等差數(shù)列求和公式，保留下來的子矩陣總數(shù)Sstay為

(17)

則總共減少的子矩陣數(shù)量為

(18)

從式(18)可以看出，去除的子矩陣接近總數(shù)的一半，大大縮小了計(jì)算數(shù)據(jù)量。圖5展示了LFF、ALFF和TM-score 3種方法分別計(jì)算不同數(shù)量蛋白質(zhì)相似性矩陣的時(shí)間開銷，橫軸表示蛋白質(zhì)的數(shù)量，縱軸表示算法計(jì)算相似度矩陣所用的時(shí)間，單位為s。觀察曲線趨勢(shì)可以發(fā)現(xiàn)，當(dāng)?shù)鞍踪|(zhì)數(shù)量比較多的時(shí)候，TM-score在計(jì)算速度上比較占優(yōu)勢(shì)，而LFF和ALFF隨著數(shù)據(jù)量增大，計(jì)算的復(fù)雜度明顯增加，主要原因是這2種方法都基于聚類分析。ALFF經(jīng)過數(shù)據(jù)縮減，計(jì)算速度明顯比LFF提升了許多，計(jì)算100個(gè)蛋白質(zhì)的相似性矩陣用時(shí)48.13 s，比LFF的79.04 s快了30.91 s。

圖5 LFF、ALFF和TM-score方法的計(jì)算時(shí)間比較Fig. 5 Calculation time comparison of LFF, ALFF and TM-score methods

3 結(jié)語

本文通過對(duì)LFF方法的改進(jìn)得到ALFF方法，該方法可以發(fā)現(xiàn)蛋白質(zhì)的相似性和其局部特征有非常密切的關(guān)系，利用這種關(guān)系得到的局部特征頻率可以很好地表示蛋白質(zhì)的結(jié)構(gòu)。ALFF利用OTSU算法對(duì)數(shù)據(jù)選擇合適的局部特征，MeanShift代替k-medoids做聚類分析，改進(jìn)了2個(gè)重要參數(shù)的選擇，避免了人工調(diào)參，相比LFF，在重構(gòu)矩陣對(duì)比差異中有更低的錯(cuò)誤率。在數(shù)據(jù)集的預(yù)處理上，ALFF去掉了冗余的等效子矩陣，縮小了接近一半的數(shù)據(jù)量，使得算法能夠處理更大的數(shù)據(jù)集。相對(duì)于LFF，ALFF在蛋白質(zhì)結(jié)構(gòu)相似性分析的class、fold、superfamily、family的分類中有更高的一致性，分別提升了0.7、2.3、2.8、3.5個(gè)百分點(diǎn)。在蛋白質(zhì)相似性的對(duì)比實(shí)驗(yàn)中，ALFF總體上和TM-score保持比較好的一致性，能夠較好地計(jì)算出同源蛋白質(zhì)的相似性。相比于LFF，ALFF計(jì)算所花費(fèi)的時(shí)間大大降低，并且準(zhǔn)確性有了進(jìn)一步提升。但是從部分實(shí)驗(yàn)中發(fā)現(xiàn)，基于局部特征的計(jì)算方法也有一些不足之處，即當(dāng)沒有共同祖先的蛋白質(zhì)有相同局部特征的時(shí)候也會(huì)得到較高的相似性分?jǐn)?shù)，這將是今后需要研究的一個(gè)方向。