鬼佬大哥大
  • / 11
  • 下載費用:30 金幣  

基于SHREC3D和轉換參數優化的染色體3D結構建模方法.pdf

摘要
申請專利號:

CN201510542519.7

申請日:

2015.08.28

公開號:

CN105205345A

公開日:

2015.12.30

當前法律狀態:

駁回

有效性:

無權

法律詳情: 發明專利申請公布后的駁回 IPC(主分類):G06F 19/12申請公布日:20151230|||實質審查的生效IPC(主分類):G06F 19/12申請日:20150828|||公開
IPC分類號: G06F19/12(2011.01)I; G06F19/18(2011.01)I 主分類號: G06F19/12
申請人: 北京工業大學
發明人: 李建更; 張衛; 李曉丹; 張巖
地址: 100124 北京市朝陽區平樂園100號
優先權:
專利代理機構: 北京思海天達知識產權代理有限公司 11203 代理人: 沈波
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510542519.7

授權公告號:

||||||

法律狀態公告日:

2019.02.12|||2016.01.27|||2015.12.30

法律狀態類型:

發明專利申請公布后的駁回|||實質審查的生效|||公開

摘要

基于ShRec3D和轉換參數優化的染色體3D結構建模方法,將基因片段之間的交互頻率轉換為空間距離,進一步構建基因組的三維空間結構。該方法,首先通過黃金分割算法尋找最優的轉換參數,將兩個染色體片段之間的交互作用頻率,轉化為兩個片段之間的空間距離;進而應用最短距離算法構建基因組的空間距離圖譜,最后用MDS算法得到三維空間中各個基因片段的相對坐標圖,對染色體的三維空間結構可視化。并用均方根誤差RMSD和Spearman相關系數度量構建的染色體結構的相似性。本發明對不同分辨率下的Hi-C數據集,能尋找最優的轉換參數,提高了ShRec3D算法的準確性和魯棒性,可用于染色體3D結構的建模。

權利要求書

權利要求書
1.  基于ShRec3D和轉換參數優化的染色體3D結構建模方法,其特征在于:
本方法采用的技術方案實現步驟如下,
1)染色體3D結構的模型表示;
首先將每條染色體分割成一個連著一個的小珠子(bead),每個小珠子代表一定長度的一段序列;若分辨率是1M,就是以1M的長度將染色體打斷成一個個連續的小珠子;最終染色體被斷成N=ceil(L/H)個連續的小珠子,其中L代表染色體的總長度,H代表所選取的分辨率;然后將交互頻率映射到NxN的矩陣(Fij)N×N上,其為對稱半正定矩陣,Fij、Dij分別代表第i個小珠子和第j個小珠子之間的交互頻率和空間距離;定義重構后的染色體坐標矩陣為X=(x1……xn),其中xi∈R3代表第i個小珠子的三維坐標;
2)從接觸頻率矩陣F到距離矩陣D
根據染色體的接觸頻率Fij和空間距離Dij之間呈現一種power-law遞減分布關系,得到兩者之間的轉換函數:
Dij=Fij(-α)ifFij>0otherwise]]>
其中α是一個針對不同分辨率的數據引入的變轉換參數;Dij和Fij是第i和j個片段間的距離和接觸頻率;
3)計算最短路徑:針對距離矩陣DN×N中的無窮量用Floyd-Warshall算法計算最短距離,獲得全基因組的空間距離圖譜Df;
4)MDS(多維尺度變換算法):從距離矩陣Df到空間坐標矩陣X;
5)用黃金分割搜索算法,優化得到轉換參數αf
6)結構相似性度量:用RMSD(均方根誤差)和dSCC(距離Spearman相關系數)計算重建的染色體的相似性;
31)對于Fij>0的兩個點,以歐式距離d(i,j)作為權重賦予i,j兩點組成的邊,由此獲得距離矩陣df(i,j)=d(i,j);
32)對于Fij=0的兩點,用最短路徑通過下式計算:
df(i,j)=min{df(i,j),df(i,1)+df(1,j)}
41)重建后染色體3D結構中第i,j片段之間的歐式距離為dij(X)=‖xi-xj‖;MDS的目標是保持重構前后樣本點之間的距離誤差最小,即
MinimizeΣ0in0<j<n(dij-df(i,j))2]]>
42)定義一個度量矩陣M,其中M由距離矩陣Df獲得,通過下式計算得到
doi2=1NΣj=1NDij2-1N2Σj=1NΣk>jNDjk2]]>其中doi為第i個點和中心點之間的距離;
②M是一個對稱半定矩陣;
43)將矩陣M進行奇異值分解,取其最大的m(本文m=3)個特征值(λ1,λ2,……λm)對應的m個特征向量(ω1,ω2,……,ωm),m個特征值組成m維對角矩陣Λ,m個特征向量組成n*m維矩陣V;
③X即為重構后的染色體3D結構片段的三維坐標
51)定義一個單峰目標函數error(F,α)=∑|F-F′|;其中F為真實的染色體接觸頻率矩陣,為重構后的三維坐標構建的接觸頻率矩陣;用黃金分割搜索算法優化α∈(0.1,2)使目標函數最小, 得到轉換參數αf;
61)現階段,無法獲得真實的染色體3D結構;通過兩種內切酶(Hind3,NcoI)獲得的同一基因組的數據來構建三維結構,從而比較這兩個結構重疊的相似性來度量方法的正確性;
62)將一個染色體結構的位點片段坐標進行剛性的平移、旋轉和伸縮,采用最小平方擬合的方法,使得整體結構最大程度地疊置到另一個結構上;設兩個結構的骨架分別由連續的三維坐標點決定,P=(p1,p2……pn)和Q=(q1,q2,……qn),RMSD的計算過程為:對P進行變換,P′=sRP-T,其中R∈R3×3的旋轉矩陣,T∈R3是平移向量,t是伸縮因子;計算:
RMSD=minΣi=1n(qi-pi)2]]>
RMSD計算的是兩個結構的標準矢量距離,表示兩者結構的相似性;偏差值越小,兩結構的相似性越大;
63)計算兩種重建結構的由三維坐標得到的距離矩陣之間的Spearman相關系數(dSCC)
dSCCΣ(d1-d1&OverBar;)(d2-d2&OverBar;)Σ((d1-d1&OverBar;)2Σ((d2-d2&OverBar;)2]]>
dSCC∈(-1,1),dSCC接近1,表示兩結構相似性越大;則算法的精確度越高。

說明書

說明書基于ShRec3D和轉換參數優化的染色體3D結構建模方法
技術領域
本發明涉及生物信息學中染色體三維模型構建技術領域,是一種針對不同分辨率下的Hi-C數據的染色體3D結構建模的方法。
背景技術
基因組學的研究使認識到基因的正確表達、調控以及調控原件之間的相互作用都需要在染色體折疊成的復雜的三維結構中完成。因此構建染色體的三維結構對于進一步的理解基因組的表達、調控等功能有重要的意義。近些年來,基于染色質構象捕獲(chromosomeconformationcapture,3C)及其衍生技術基礎上發展起來的Hi-C技術,能夠在全基因組范圍內捕獲不同基因座之間的空間交互,揭示基因組空間結構的規律性及其與基因調控之間的關系。基于這些高通量交互數據,進一步采用數學建模方法,得到的結果極大拓展了對基因組空間結構的認識。
基于高通量測序數據的染色體3D結構的建模大致分為兩類:(i)consensus方法,目的在于重建一個整體數據反應的單個染色體的平均結構。(ii)ensemble方法,用于產生多個代表性的結構,反應一個細胞群體中多個基因組空間結構呈現的整體趨勢。這兩類方法用于染色體3D結構建模都經過兩個重要步驟,一是將兩個DNA片段之間的交互作用頻率,轉換成三維空間距離;二是基于空間距離,采用約束優化方法獲得最優的染色體三維空間結構。對于單個染色體的平均結構的研究,Hi-C數據中染色體片段間的接觸頻率和其空間距 離的轉換函數成為研究的關鍵。常見的轉換方式包括反比例轉換和線性轉換.ChromSDE方法中首次提出了一個變參數的冪指數轉換函數:d=f(-α),用黃金分割算法尋找最優的參數;然后通過半正定規劃算法(SDP)得到三維結構。ShRec3D方法中針對Hi-C接觸頻率矩陣為稀疏矩陣的特點,提出了一個兩步算法:首先針對d=f-1中的無窮的距離d,用圖論中的最短距離算法獲得全基因組的距離矩陣;而后用經典的MDS(multidimensionalscaling),獲得三維空間相對坐標位置。ShRec3D方法避免了ChromSDE算法中對于高分辨率下大數據量無法收斂的問題,且計算效率比ChromSDE算法高出幾個數量級。
發明內容
本發明的目的在于針對ShRec3D和ChromSDE算法中的不足,提出了一種基于ShRec3D和轉換參數優化的染色體3D結構建模方法。針對ShRec3D算法中對不同分辨率的數據只有固定轉換函數d=f-1這一問題,引進了一個轉換參數變量α。應用于不同的Hi-C數據集,證明了ShRec3D算法更好的準確性和魯棒性。本發明有助于從算法上更加精確的構建染色體3D結構,可視化展示基因組的三維空間結構,啟發人們對基因組功能的理解。
為實現上述目的,本發明采用的技術方案實現步驟如下:
1)染色體3D結構的模型表示;
首先將每條染色體分割成一個連著一個的小珠子(bead),每個小珠子代表一定長度的一段序列。例如分辨率是1M,就是以1M的長度將染色體打斷成一個個連續的小珠子。最終染色體被斷成 N=ceil(L/H)個連續的小珠子,其中L代表染色體的總長度,H代表所選取的分辨率。然后將交互頻率映射到NxN的矩陣(Fij)N×N上,其為對稱半正定矩陣,Fij、Dij分別代表第i個小珠子和第j個小珠子之間的交互頻率和空間距離。定義重構后的染色體坐標矩陣為X=(x1……xn),其中xi∈R3代表第i個小珠子的三維坐標。
2)從接觸頻率矩陣F到距離矩陣D
根據染色體的接觸頻率Fij和空間距離Dij之間呈現一種power-law遞減分布關系,得到兩者之間的轉換函數:
Dij=Fij(-α)ifFij>0otherwise]]>
其中α是一個針對不同分辨率的數據引入的變轉換參數。Dij和Fij是第i和j個片段間的距離和接觸頻率。
3)計算最短路徑:針對距離矩陣DN×N中的無窮量用Floyd-Warshall算法計算最短距離,獲得全基因組的空間距離圖譜Df;
4)MDS(多維尺度變換算法):從距離矩陣Df到空間坐標矩陣X;
5)用黃金分割搜索算法,優化得到轉換參數αf
6)結構相似性度量:用RMSD(均方根誤差)和dSCC(距離Spearman相關系數)計算重建的染色體的相似性。
31)對于Fij>0的兩個點,以歐式距離d(i,j)作為權重賦予i,j兩點組成的邊,由此獲得距離矩陣df(i,j)=d(i,j)。
32)對于Fij=0的兩點,用最短路徑通過下式計算:
df(i,j)=min{df(i,j),df(i,1)+df(1,j)}
41)重建后染色體3D結構中第i,j片段之間的歐式距離為dij(X)=‖xi-xj‖。MDS的目標是保持重構前后樣本點之間的距離誤差最小,即
MinimizeΣ0in0<j<n(dij-df(i,j))2]]>
42)定義一個度量矩陣M,其中M由距離矩陣Df獲得,通過下式計算得到
doi2=1NΣj=1NDij2-1N2Σj=1NΣk>jNDjk2]]>其中doi為第i個點和中心點之間的距離;
②M是一個對稱半定矩陣;
43)將矩陣M進行奇異值分解,取其最大的m(本文m=3)個特征值(λ1,λ2,……λm)對應的m個特征向量(ω1,ω2,……,ωm),m個特征值組成m維對角矩陣Λ,m個特征向量組成n*m維矩陣V;
③X即為重構后的染色體3D結構片段的三維坐標
51)定義一個單峰目標函數error(F,α)=∑|F-F′|。其中F為真實的染色體接觸頻率矩陣,為重構后的三維坐標構建的接觸頻率矩陣。用黃金分割搜索算法優化α∈(0.1,2)使目標函數最小,得到轉換參數αf。
61)現階段,無法獲得真實的染色體3D結構。通過兩種內切酶(Hind3,NcoI)獲得的同一基因組的數據來構建三維結構,從而比較這兩個結構重疊的相似性來度量方法的正確性。
62)將一個染色體結構的位點片段坐標進行剛性的平移、旋轉和伸縮,采用最小平方擬合的方法,使得整體結構最大程度地疊置到 另一個結構上。設兩個結構的骨架分別由連續的三維坐標點決定,P=(p1,p2……pn)和Q=(q1,q2,……qn),RMSD的計算過程為:對P進行變換,P′=sRP-T,其中R∈R3×3的旋轉矩陣,T∈R3是平移向量,t是伸縮因子。計算:
RMSD=minΣi=1n(qi-pi)2]]>
RMSD計算的是兩個結構的標準矢量距離,表示兩者結構的相似性。偏差值越小,兩結構的相似性越大。
63)計算兩種重建結構的由三維坐標得到的距離矩陣之間的Spearman相關系數(dSCC)
dSCCΣ(d1-d1&OverBar;)(d2-d2&OverBar;)Σ((d1-d1&OverBar;)2Σ((d2-d2&OverBar;)2]]>
dSCC∈(-1,1),dSCC接近1,表示兩結構相似性越大。則算法的精確度越高。
與現有技術相比,本發明將轉換參數α引入ShRec3D方法中,它更適應于不同分辨率下的Hi-C數據,即分辨率越大,轉換參數的值越大,從而使接觸頻率到空間距離的轉換函數更優。同時使用MDS算法代替SDP算法,避免了ChromSDE方法中對于大數據量的計算不收斂的問題。變參數的ShRec3D方法提高了原有方法的染色體3D結構建模的準確性和魯棒性。本發明構建的染色體三維結構更加準確從可視化角度極大拓展了對基因組空間結構的認識。
附圖說明
圖1為本發明的方法流程圖。
圖2為在不同的噪聲水平下,本發明和其他兩種方法關于RMSD 值變化曲線對比圖。
圖3為在不同的噪聲水平下,本發明和其他兩種方法關于Spearman系數值變化曲線對比圖。
圖4為在不同的噪聲水平下,本發明和其他兩種方法關于參數誤差Δα值變化曲線對比圖。
具體實施方式
以下結合附圖和實施例對本發明作進一步詳細說明。
實施例
模擬數據集
模擬產生三個明確結構的數據集(1)螺旋結構曲線(Helix),(2)布朗運動點形成的曲線(Brownianmotion),(3)在一個正方體內隨機運動產生的三維曲線圖(randompoints)。每個結構由100個點組成,假設HIC技術能夠敏感的最多捕獲50個近鄰點,這樣保證接觸頻率矩陣是稀疏的,并令轉換指數α=1。所以可計算任意兩點的接觸頻率fij=(1/dij)(1α)=1/dij(dij=||Xi-Xj||,]]>為兩點之間的歐式距離)。而且,為了更真實的逼近真實的HIC數據,規定接觸頻率之和為106。
為證明本發明的魯棒性,用含有噪聲的螺旋結構的數據集來重建三維結構,噪音接觸頻率矩陣為其δ=(rand-1)*noiselevel,δ為特定噪音水平(noiselevel為定值)下的隨機噪聲值,其rand∈(0,1);F為真實的接觸頻率矩陣Fij=1/dij。本發明與ChromSDE(包括LinearSDP和QuadraticSDP)方法,在不同的噪聲水平下針對Spearman相關系數、RMSD和參數誤差Δα三個參數進行比較。從圖2可以看出 隨著噪音增大,三種方法的RMSD值都變大,在noiselevel>0.3時,本發明在RMSD值小于其他兩個方法。圖3關于Spearman相關系數有類似的結論。圖4所示,在noiselevel<0.8時,三種方法都能準確優化轉換參數,且接近真實值Δα<0.08。綜上分析,在一定的噪聲水平下,本發明能精確構建模擬數據集的3D結構。
真實的Hi-C數據
Hi-C數據集來自老鼠的胚胎干細胞(mESC),分辨率為1M,下載自NCBI庫檢索號是GSE35156。人類GM06990細胞系的歸一化的數據集下載自http://compgenomics.weizmann.ac.il/tanay/?page_id=283。每個細胞系的兩個數據集的不同在于采用Hind3和NcoI酶來獲得結構片段。
對于真實Hi-C數據,表1列出了每個細胞系下所有重構的染色體關于RMSD和Spearman系數的平均值。對于三種方法的比較列表1、表2。
從表1中不難發現,在RMSD和dSCC兩個指標上,本發明能有效的構建染色體3D結構,對于mESC數據集,本發明比有ChromSDE和ShRec3D方法有更好的優越性。對于GM數據集,本發明和ChromSDE有相似的性能。表2中指出了本發明在構建染色體3D結構中,在效率上比ChromSDE快近一個數量級。由于本發明在ShRec3D方法的基礎上增加了迭代尋找最優的參數的黃金分割算法,所以在效率上低于ShRec3D。本發明綜合考慮來了染色體3D模型構建的準確性和高效性,其性能優于其他方法。
表1結構穩定性參數對比

注:兩個細胞系下的兩種酶切數據構建染色體3D結構的RMSD和dSCC平均值。黑色字體表示的是該細胞系下最優的參數值。
表2.每個數據集的染色體3D結構重構花費時間之和(單位:秒)

注:對于各個數據的三維基因組的三維結構重構花費時間之和。

關 鍵 詞:
基于 SHREC3D 轉換 參數 優化 染色體 結構 建模 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于SHREC3D和轉換參數優化的染色體3D結構建模方法.pdf
鏈接地址:http://www.wwszu.club/p-6405670.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大