利用改進(jìn)的3DMax算法重構(gòu)染色體3D結(jié)構(gòu)

劉立偉,么會麗

(大連交通大學(xué) 理學(xué)院，遼寧 大連 116028)

染色體構(gòu)象捕獲技術(shù)，特別是Hi-C技術(shù)的發(fā)展，使基因組空間構(gòu)象的分析和研究成為生物信息學(xué)和計算生物學(xué)的重要課題。在高通量下一代測序技術(shù)的幫助下，Hi-C技術(shù)可以生成全基因組范圍的、大規(guī)模的染色體內(nèi)和染色體間相互作用數(shù)據(jù)，能夠詳細(xì)描述基因組內(nèi)的空間相互作用。這些數(shù)據(jù)可以用來重建染色體的三維結(jié)構(gòu)，用于研究DNA復(fù)制、基因調(diào)控、基因組相互作用、基因組折疊和基因組功能[1-9]。目前，根據(jù)構(gòu)建染色體三維模型原理上的不同，可將結(jié)構(gòu)模型分為兩大類:即基于概率約束的預(yù)測模型和基于距離約束的預(yù)測模型。由于細(xì)胞染色體的三維結(jié)構(gòu)是動態(tài)的，我們可以用一些概率分布來描述它，從而將染色體三維結(jié)構(gòu)的構(gòu)建問題轉(zhuǎn)化為概率模型的構(gòu)建問題。實現(xiàn)這一過程的方法稱為基于概率約束的預(yù)測模型。其中有一些方法是通過兩步來進(jìn)行染色體基因組三維結(jié)構(gòu)建模，即將Hi-C數(shù)據(jù)中片段對之間的相互作用頻率(IF)轉(zhuǎn)換為片段對之間的距離，然后通過對距離值進(jìn)行優(yōu)化，推斷出最能滿足距離的3D結(jié)構(gòu)，即求解出染色體片段的三維空間坐標(biāo)，實現(xiàn)這兩步過程的方法稱為基于距離約束的模型。在對距離值進(jìn)行優(yōu)化的過程中，常用梯度迭代優(yōu)化算法優(yōu)化目標(biāo)函數(shù)，目前現(xiàn)有的隨機(jī)梯度優(yōu)化算法有SGD、Momentum、Nesterov、Adagrad、Adadelta、Adam、Adamax、Nadam[10-16]，本文根據(jù)目前存在的隨機(jī)梯度優(yōu)化算法的優(yōu)點和缺點，提出了XNadam算法。

1 3DMax 算法原理簡介

3DMax算法[17]是由Oluwadare等人提出，它使用最大似然方法從Hi-C數(shù)據(jù)中推斷染色體的三維結(jié)構(gòu)。3DMax比現(xiàn)有的大多數(shù)方法都要快，它只依賴于通過最小二乘殘差來優(yōu)化預(yù)測模型的結(jié)構(gòu)坐標(biāo)。3DMax算法也是基于距離約束的預(yù)測模型，該算法首先通過初始化一組染色體空間坐標(biāo)，計算出染色體片段之間的歐氏距離，然后通過轉(zhuǎn)換函數(shù)將輸入的接觸頻率矩陣轉(zhuǎn)換成的距離矩陣，并假設(shè)距離矩陣中的每一個數(shù)據(jù)點獨立并服從正態(tài)分布，從而構(gòu)建一個基于正態(tài)分布的對數(shù)似然目標(biāo)函數(shù)，再采用梯度上升算法迭代優(yōu)化目標(biāo)函數(shù)直到算法收斂，在迭代過程中同步更新染色體三維坐標(biāo)。在3DMax算法中，采用梯度上升算法對目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化的過程中，計算出距離斯皮爾曼相關(guān)系數(shù)(DSCC)，并選出最大DSCC系數(shù)對應(yīng)的轉(zhuǎn)換參數(shù)，最優(yōu)轉(zhuǎn)換參數(shù)下的染色體片段坐標(biāo)，是我們推斷出最能滿足距離的可視化染色體結(jié)構(gòu)。3DMax算法還有一個變體，稱為3DMax1，它在輸入噪聲時對輸入接觸矩陣進(jìn)行額外的預(yù)處理和濾波。

在3DMax1算法中，Oluwadare等人，使用的隨機(jī)梯度上升算法是自適應(yīng)梯度算法(AdaGrad)[18]。自適應(yīng)梯度算法(AdaGrad)是一種基于梯度的優(yōu)化方法，它可以使學(xué)習(xí)速率適應(yīng)每個參數(shù)，可以對低頻的參數(shù)做較大的更新，對高頻的做較小的更新，也因此，對于稀疏的數(shù)據(jù)它的表現(xiàn)很好。它的缺點是分母會不斷積累，內(nèi)存需求較大，這樣學(xué)習(xí)率就會收縮并最終會變得非常小，甚至趨于零。

2 XNadam算法原理簡介

除了3DMax1算法中應(yīng)用到的自適應(yīng)梯度算法(AdaGrad)以外，目前現(xiàn)有的隨機(jī)梯度優(yōu)化算法還有SGD、Momentum、Nesterov、RMSprop、Adadelta、Adam、Adamx、Nadam。本文提出了一種新的隨機(jī)梯度上升算法XNadam，是Nadam的一個變體。Nadam(Nesterov-acceler Adaptive Moment Estimation)是將Adam與Nesterov算法結(jié)合在一起，具備二者的優(yōu)勢。它對學(xué)習(xí)率的約束將更強(qiáng)，使得此算法在某些問題上效果更好。Nadam的優(yōu)點主要在于經(jīng)過偏置矯正后，每一次迭代學(xué)習(xí)率都有個確定范圍，為不同的參數(shù)計算不同的自適應(yīng)學(xué)習(xí)率，使得參數(shù)比較平穩(wěn)，同時內(nèi)存需求較小，也適應(yīng)于大多非凸優(yōu)化，適應(yīng)于大數(shù)據(jù)和高維空間。由于加入了Nesterov項，則在梯度更新時做一個校正，避免前進(jìn)太快，同時提高靈敏；XNadam作為Nadam的一個變體，原理跟Nadam類似。區(qū)別是XNadam采用正弦的相關(guān)方式進(jìn)行學(xué)習(xí)率的衰減，同時利用正弦方式的衰減率對一階矩估計進(jìn)行修正，所以XNadam具有Nadam算法的所有優(yōu)點。

3 XNadam算法

XNadam算法要求:初始學(xué)習(xí)率α0,最小學(xué)習(xí)率αmin要求:矩估計的指數(shù)衰減速率β2,β1,取值區(qū)間均為[0,1)內(nèi)要求:用于數(shù)值穩(wěn)定的小常數(shù)δ(默認(rèn)10-6)要求:初始化一階和二階矩變量n=0,m=0,初始化時間步長t=0計算梯度:gt+1=‰f(St)對梯度更新:g^t+1=gt+11-∏t+1i=1βi1更新有偏二階矩估計:nt+1=β2·nt+(1-β2)·g2t+1修正二階矩的偏差:n^t+1=nt+11-βt+12更新有偏一階矩估計:mt+1=β(t+1)1·mt+(1-β(t+1)1)·gt+1衰減速率:β(t)1=β1·0.5·(1+sin(tπT))T=t(t+3)2對一階矩修正:m^t+1=mt+11-∏t+2i=1βi1繼續(xù)修正一階矩:m-t+1=β(t+2)1·m^t+1+(1-β(t+1)1)·g^t+1學(xué)習(xí)率:αt=α0·[(1-αmin)·0.5·(1+sin(tπT))+αmin]計算更新:ΔSt+1=αt+1m-t+1n^t+1+ε應(yīng)用更新:St+1=St+ΔSt+1

4 模型相似性和準(zhǔn)確性的測量

為了測試該算法，利用3DMaxAdaGrad，3DMaxNadam和3DMaxXNadam算法對酵母染色體三維結(jié)構(gòu)進(jìn)行重構(gòu)，進(jìn)而比較他們的性能。3DMaxAdaGrad、3DMaxNadam、3DMaxXNadam是3DMax算法的一個變體，其中3DMaxAdaGrad是結(jié)合了極大似然算法和AdaGrad算法預(yù)測模型，而3DMaxNadam是結(jié)合了極大似然和Nadam優(yōu)化算法的預(yù)測模型，3DMaxXNadam是結(jié)合了極大似然和XNadam優(yōu)化算法的預(yù)測模型。在比較的過程中，3DMaxXNadam算法中β1=0.6，β2=0.999 9，αmin=0.000 1，只有學(xué)習(xí)率是變化的。

本文采用距離均方根誤差(Distance Root Mean Squared Error ，DRMSE)、距離斯皮爾曼相關(guān)系數(shù)(Distance Spearman Correlation Coefficient ，DSCC)、距離皮爾森相關(guān)系數(shù)(Distance Pearson Correlation Coefficient，DPCC)[19-22]來量化結(jié)構(gòu)的相似性，從而衡量預(yù)測方法的性能。

在本研究中輸入的歸一化接觸頻率值所選擇的數(shù)據(jù)集是酵母的Hi-C數(shù)據(jù)，酵母Hi-C數(shù)據(jù)用Yaffe和Tanay等人[23]提出的技術(shù)進(jìn)行了歸一化。3DMaxAdaGrad，3DMaxNadam和3DMaxXNadam算法對1-12號染色體三維空間結(jié)構(gòu)重構(gòu)的DSCC、DPCC 和DRMSE三個評價指標(biāo)結(jié)果(見圖1)。

圖1 3DMaxAdaGrad，3DMaxnadam和3DMaxnadam算法重構(gòu)染色體三維結(jié)構(gòu)的評估結(jié)果Fig.1 Evaluation results for 3DMaxAdaGrad, 3DMaxNadam, and 3DMaxXNadam

圖1中的柱形圖表示了3DMaxAdaGrad，3DMaxNadam和3DMaxXNnadam三種算法重構(gòu)染色體三維結(jié)構(gòu)的DSCC、DPCC和 DRMSE評估結(jié)果。第一列黃色柱形圖代表三種算法對酵母1-12號染色體三維結(jié)構(gòu)重構(gòu)的DSCC結(jié)果，觀察圖形可知，對于1號、2號染色體，3DMaxAdaGrad算法重建染色體三維結(jié)構(gòu)的DSCC值最大，其次是3DMaxXNnadam算法的DSCC值，其中3DmaxNadam算法的DSCC值最?。粚τ?號染色體，3DmaxNadam算法重構(gòu)染色體三維結(jié)構(gòu)的DSCC值最大，其次是3DmaxXNadam算法的DSCC值較大，最小的是3DMaxAdaGrad的DSCC值；除了上述三條染色體，其余的染色體都是3DmaxXNadam算法重構(gòu)染色體三維結(jié)構(gòu)的DSCC值最大。

第二列綠色柱形圖代表三種算法對酵母1-12號染色體三維結(jié)構(gòu)重構(gòu)的DPCC結(jié)果，從圖可以看出，除了7號染色體，其余11條染色體中，3DmaxXNadam算法重構(gòu)染色體三維結(jié)構(gòu)的DPCC值最大，其次是3DmaxNadam算法的DPCC值，最小的是3DMaxAdaGrad算法的DPCC值。

第三列紅色柱形圖代表三種算法對酵母1-12號染色體重構(gòu)的三維結(jié)構(gòu)DRMSE結(jié)果，從圖可以看出，除了7號染色體，其余11條染色體中，3DmaxXNadam算法重構(gòu)染色體三維結(jié)構(gòu)的DRMSE值最小，其次是3DmaxNadam算法的DRMSE值，最大的是3DMaxAdaGrad算法重構(gòu)染色體三維結(jié)構(gòu)的DRMSE值。

根據(jù)上述實驗結(jié)果可知，3DmaxXNadam算法的性能更好。

5 染色體三維結(jié)構(gòu)可視化

通過算法比較，3DmaxXNadam算法對染色體三維結(jié)構(gòu)進(jìn)行重構(gòu)具有較高的準(zhǔn)確度。在此，使用該算法對酵母 1-12號染色體三維空間結(jié)構(gòu)進(jìn)行重構(gòu)，得了酵母1-12 號染色體的三維效果圖(見圖2)。

圖2 染色體的三維空間結(jié)構(gòu)重構(gòu)效果圖Fig.2 Sketch of 3D structure reconstruction of chromosomes

6 結(jié) 論

本研究在Nadam優(yōu)化算法的基礎(chǔ)上發(fā)展了一種新的梯度上升優(yōu)化算法(XNadam)，并引入最大似然算法分別和AdaGrad、Nadam、XNadam算法相結(jié)合得到3DMaxAdaGrad，3DMaxNadam和3DMaxXNadam算法。利用3DMaxAdaGrad，3DMaxNadam和3DMaxXNadam算法對酵母染色體三維結(jié)構(gòu)進(jìn)行重構(gòu)，并且計算了生成的染色體優(yōu)化結(jié)構(gòu)的DSCC、DPCC 和DRMSE的值，從而衡量預(yù)測方法的性能。在真實數(shù)據(jù)集上的實驗結(jié)果表明，3DmaxXNadam算法可以更有效地從Hi-C接觸矩陣中重建染色體模型，同時與其他方法相比，它速度更快，對內(nèi)存的要求也較低。這個結(jié)論說明新的梯度上升優(yōu)化算法(XNadam)在優(yōu)化對數(shù)似然目標(biāo)函數(shù)上，它的表現(xiàn)比大多數(shù)其他優(yōu)化方法更好。