利用改進的3DMax算法重構染色體3D結構

劉立偉,么會麗

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

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

1 3DMax 算法原理簡介

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

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

2 XNadam算法原理簡介

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

3 XNadam算法

XNadam算法要求:初始學習率α0,最小學習率αmin要求:矩估計的指數衰減速率β2,β1,取值區間均為[0,1)內要求:用于數值穩定的小常數δ(默認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繼續修正一階矩:m-t+1=β(t+2)1·m^t+1+(1-β(t+1)1)·g^t+1學習率:αt=α0·[(1-αmin)·0.5·(1+sin(tπT))+αmin]計算更新:ΔSt+1=αt+1m-t+1n^t+1+ε應用更新:St+1=St+ΔSt+1

4 模型相似性和準確性的測量

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

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

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

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

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

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

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

根據上述實驗結果可知，3DmaxXNadam算法的性能更好。

5 染色體三維結構可視化

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

圖2 染色體的三維空間結構重構效果圖Fig.2 Sketch of 3D structure reconstruction of chromosomes

6 結 論

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