結(jié)構(gòu)生物信息學(xué)冷凍電鏡的三維重構(gòu)簡介和科學(xué)問題

1、結(jié)構(gòu)生物信息學(xué)冷凍電鏡的三維重構(gòu)簡介和科學(xué)問題一、冷凍電鏡三維重構(gòu)簡介二、CryoEM面臨的科學(xué)問題三、CryoET面臨的科學(xué)問題Outline 確定蛋白質(zhì)結(jié)構(gòu)的方法確定蛋白質(zhì)結(jié)構(gòu)的方法核磁共振X射線晶體衍射結(jié)構(gòu)預(yù)測冷凍電鏡小分子量蛋白蛋白質(zhì)復(fù)合體小分子量蛋白膜蛋白和超大分子復(fù)合體背景簡介背景簡介 冷凍電鏡的優(yōu)勢研究生物大分子結(jié)構(gòu)的強(qiáng)有力手段。冷凍電鏡重構(gòu)技術(shù)在未來結(jié)構(gòu)生物學(xué)中起到了一個(gè)聯(lián)系的紐帶基于CryoEM的多種技術(shù)的融合，被Science評(píng)選為2002年世界十大科技進(jìn)展之一。Sali et.al. Nature (2003) Trends in Macromolecular CryoE

2、M 背景簡介YearsNumber of Public Structures 冷凍電鏡三維重構(gòu)背景簡介一、冷凍電鏡三維重構(gòu)簡介二、CryoEM面臨的科學(xué)問題三、CryoET面臨的科學(xué)問題Outline 冷凍電鏡三維重構(gòu)處理流程生物制樣 樣品冷凍拍攝 數(shù)據(jù)采集 圖像處理 三維重構(gòu) 結(jié)構(gòu)分析 評(píng)價(jià) Chiu et.al. JEOL News (2006)Cryo-EM 冷凍電鏡三維重構(gòu)問題描述electron beam3D macromolecule2D projections(CryoEM)Can we deduce the 3-D structure of the molecule from

3、a set of 2-D projection images with unknown relative orientations?Cryo-EM單顆粒冷凍電鏡三維重構(gòu)200Cryo-EM 冷凍電鏡三維重構(gòu)問題描述9131212157123124579Cryo-EM 冷凍電鏡三維重構(gòu)問題形式描述Data:Unknown Parameters:Density:Rotations:Translations:Objective:C. Yang et.al. JSB (2005)Cryo-EM冷凍電鏡三維重構(gòu)基本思想基本思想：相同生物大分子某方向的投影，在實(shí)空間中經(jīng)過調(diào)整，疊加平均，提高信噪比，使共同

4、部分的結(jié)構(gòu)信息得到加強(qiáng)，最后對各種不同方向的投影在三維空間中進(jìn)行重構(gòu),從而獲得其三維結(jié)構(gòu)信息。Cryo-EMroofdoorwindows65冷凍電鏡三維重構(gòu)基本思想3421顆粒挑選圖像對齊圖像分類確定方向三維重構(gòu)結(jié)構(gòu)分析Cryo-EM顆粒挑選Refine初始模型模型優(yōu)化冷凍電鏡三維重構(gòu)的基本步驟Cryo-EM冷凍電鏡三維重構(gòu)的基本步驟Cryo-EM冷凍電鏡三維重構(gòu)的基本步驟Cryo-EM冷凍電鏡三維重構(gòu)的基本步驟Cryo-EM冷凍電鏡三維重構(gòu)的基本步驟Cryo-EM冷凍電鏡三維重構(gòu)結(jié)果：初始模型Cryo-EM冷凍電鏡三維重構(gòu)結(jié)果：第1次迭代Cryo-EM冷凍電鏡三維重構(gòu)結(jié)果：第2次迭代Cry

5、o-EM冷凍電鏡三維重構(gòu)結(jié)果：第3次迭代Cryo-EM冷凍電鏡三維重構(gòu)結(jié)果：第4次迭代Cryo-EM冷凍電鏡三維重構(gòu)結(jié)果：第5次迭代Cryo-EM一、顆粒圖像信噪比極低二、三維重構(gòu)計(jì)算時(shí)間極其漫長三、急需新的重構(gòu)算法冷凍電鏡三維重構(gòu)面臨的科學(xué)問題Cryo-EM顆粒圖像信噪比極低顆粒圖像信噪比極低電子成像技術(shù)樣品不均一需采集大量圖像數(shù)據(jù)如何快速、準(zhǔn)確進(jìn)行蛋白顆粒的挑選？手工挑選 半自動(dòng)化200Cryo-EM顆粒圖像信噪比極低要達(dá)到1精度，需要100萬張分子顆粒圖片Cryo-EM三維重構(gòu)時(shí)間極其漫長數(shù)萬數(shù)十萬顆粒圖像ClassificationAverageFourier TransformRef

6、inementAlignmentCross Common LineInverse Fourier TransformCryo-EM三維重構(gòu)時(shí)間極其漫長Near-atomic Resolution Structures by Single Particle Cryo-EM ComplexPublicationSelected ParticlesSoftwareCPU hrsEffective resolution ()Modeling methodCPVNature (453) 15 May 200817,123IMIRS 1033.8Fourier-Bessel&球諧函數(shù)15 phageNat

7、ure (451) 28 Feb. 200836,259EMAN1064.5Direct Fourier inversion GroELStructure (16) March 200820,401EMANN/A4.2Direct Fourier inversion RotavirusPNAS (105) 12 Feb. 200818,125FREALIGN1053.8Direct Fourier inversion 數(shù)據(jù)來自 “Current Opinion in Structural Biology” 2008, 18:218-228Cryo-EM急需新的重構(gòu)算法現(xiàn)有算法絕大部分基于Fou

8、rier-Bessel模型，70年代初提出的?；诂F(xiàn)有的算法，重構(gòu)精度很難再提高如何進(jìn)一步提高三維重構(gòu)的精度？Cryo-EM一、顆粒圖像的挑選 -顆粒圖像識(shí)別軟件Picker二、三維重構(gòu)的高性能計(jì)算 -重構(gòu)并行軟件ParaEMAN三、重構(gòu)結(jié)果精度優(yōu)化 -原有算法的完善 -球面坐標(biāo)系下的三維重構(gòu)算法我們的工作Cryo-EM顆粒圖像挑選 降噪處理原始圖片一次降噪二次降噪三次降噪原始電鏡圖片01nov26b.001.003.001.001 ,來自SCRIPPSCryo-EM 當(dāng)前研究現(xiàn)狀 - 顆粒挑選Algorithms/Criteria for Particle Selection分類典型算法優(yōu)點(diǎn)

9、缺點(diǎn)基于模板匹配Berns algorithmLudtkes algorithmPenczeks algorithmRosemans algorithmSigworths algorithm手工挑選模板借助3D參照結(jié)構(gòu)實(shí)現(xiàn)簡單如何保證模板無遺漏結(jié)果假陽性高基于特征Bajais algorithmHalls algorithmMallicks algorithmVolkmanns algorithmZhus algorithm少量樣本集利用幾何與統(tǒng)計(jì)信息自動(dòng)化程度高特征提取困難低對比度圖像效果差數(shù)據(jù)來自 “Nature Methods” 2008, 5(7): 651- 658 “Journal

10、 of Structural Biology” 2004, 145Cryo-EM顆粒挑選 當(dāng)前研究現(xiàn)狀 “Journal of Structural Biology” 145 （1-2）的統(tǒng)計(jì)結(jié)果4.18.2 Cryo-EM顆粒圖像挑選 PickerAlgorithmFPR (%)FNR (%)DR (%)Adaboost （726&786）3.110.789.3Improved adaboost （826&803）7.54.495.6Bayesian classifier （729&778）5.51288Min-distance （758&760）8.21189Cross correlati

11、on （854&897）1.676.4793.53直方圖信息熵的方法相關(guān)性匹配Adaboost方法基于樣本空間分割的方法最小距離分類器貝葉斯分類器模板匹配特征學(xué)習(xí)開發(fā)了多種顆粒識(shí)別算法，實(shí)現(xiàn)了顆粒識(shí)別軟件PickerCryo-EM顆粒圖像挑選 基于直方圖信息熵的方法算法實(shí)現(xiàn)（分成三級(jí)閾值匹配）：匹配“外圍環(huán)”，計(jì)算公式：匹配“內(nèi)圓”，計(jì)算公式：匹配“四分的網(wǎng)格”，計(jì)算公式：各級(jí)的閾值可由機(jī)器學(xué)習(xí)的方式得到Cryo-EM顆粒圖像挑選 基于adaboost的方法弱分類器強(qiáng)分類器正例反例弱分類器錯(cuò)誤率越小，就越小，就越大H(x)為+，則為正例； H(x)為-，則為反例Cryo-EM顆粒圖像挑選Cry

12、o-EM顆粒圖像挑選Cryo-EM一、顆粒圖像的挑選 -顆粒圖像識(shí)別軟件Picker二、三維重構(gòu)的高性能計(jì)算 -重構(gòu)并行軟件ParaEMAN三、重構(gòu)結(jié)果精度優(yōu)化 -原有算法的完善 -球面坐標(biāo)系下的三維重構(gòu)算法我們的工作Cryo-EM三維重構(gòu)高性能計(jì)算 時(shí)間分析EMANModuleRatioClassalign250.59%Classesbymra224.86%Classesbymra121.52%Make3d1.61%Project3d0.65%Projtree0.03%Proc3d0.03%Refine12396.97%Cryo-EM三維重構(gòu)高性能計(jì)算開發(fā)了單顆粒三維重構(gòu)并行軟件ParaEM

13、AN重構(gòu)精度優(yōu)化提出一種顆粒圖像聚類優(yōu)化的重構(gòu)框架，重構(gòu)結(jié)果精度提高重構(gòu)速度優(yōu)化基本操作時(shí)間比例優(yōu)化方式并行策略投影(Projection)0.34%速度優(yōu)化OpenMP分類(Classification)85.63%速度&精度優(yōu)化MPI+OpenMP平均(Average)11%速度優(yōu)化MPI+OpenMP重構(gòu)(Reconstruction) 2.99% 速度優(yōu)化OpenMPCryo-EM對原有算法進(jìn)行了優(yōu)化Recluster三維重構(gòu)結(jié)果精度優(yōu)化給定投影顆粒圖像旋轉(zhuǎn)平移對齊灰度值轉(zhuǎn)換二維點(diǎn)擬合誤差圖像分類最小二乘直線擬合顆粒圖像重聚類框架PRF：LY Fan, et.al. Bioinform

14、atics 2009Cryo-EM三維重構(gòu)結(jié)果精度優(yōu)化乙肝病毒 refine 1 hard=15 sym=icos mask=80 pad=374 proc=3 classkeep=0.9 ang=1 classiter=5 refine x ctfc=7Beta1.1 refine 1 mask=60 sym=c9 proc=3 hard=40 classkeep=0.9 shrink=2 pad=200 amask=55,0.8,30 classiter=5 ang=8乙肝病毒數(shù)據(jù)數(shù)據(jù)Cryo-EM三維重構(gòu)高性能計(jì)算 核心問題n組圖像數(shù)目差異很大目標(biāo)1： N個(gè)圖像的分類處理時(shí)間最短目標(biāo)2：

15、盡可能使各處理器分配的任務(wù)平均Cryo-EM三維重構(gòu)高性能計(jì)算 核心問題問題描述（Makespan Minimization)s : JP （J = 1,2n, P=1,2m)The finishing time of processor iThe makespan is: 強(qiáng)NP難問題Cryo-EM三維重構(gòu)高性能計(jì)算 核心問題提出一種自適應(yīng)任務(wù)動(dòng)態(tài)調(diào)度算法Cryo-EM三維重構(gòu)高性能計(jì)算 核心問題ParaEMAN任務(wù)調(diào)度實(shí)驗(yàn)結(jié)果Cryo-EM三維重構(gòu)高性能計(jì)算 核心問題單顆粒三維重構(gòu)并行軟件-paraEMAN10Cryo-EMCryoEM EMAN的并行優(yōu)化ParaEMAN在曙光5000上的

16、測試結(jié)果305.6445.4508.5Cryo-EMCryoEM EMAN的并行優(yōu)化ParaEMAN在“超龍一號(hào)”的測試結(jié)果FSC曲線Cryo-EMCryoEM EMAN的并行優(yōu)化“超龍一號(hào)”上ParaEMAN同EMAN的比較計(jì)算核數(shù)加速比Cryo-EM一、顆粒圖像的挑選 -顆粒圖像識(shí)別軟件Picker二、三維重構(gòu)的高性能計(jì)算 -重構(gòu)并行軟件ParaEMAN三、重構(gòu)結(jié)果精度優(yōu)化 -單顆粒三維重構(gòu)軟件ICTISAF我們的工作Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法理論基礎(chǔ)0到4階球諧函數(shù)的圖形任何空間幾何體表面都可以表示成球諧函數(shù)各分量的線性組合Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法開發(fā)完成了

17、20面體三維重構(gòu)軟件ICTISAF精度優(yōu)化基于正弦高斯校正和樣條插值的CTF校正模型基于滑動(dòng)窗口的電鏡照片全局插值算法速度優(yōu)化密度函數(shù)快速計(jì)算方法基于徑向采樣點(diǎn)旋轉(zhuǎn)角度不變性的快速映射方法基于60對稱性的快速映射方法Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法基于正弦高斯校正和樣條插值的CTF校正模型電鏡成像時(shí)電子束經(jīng)過電鏡的調(diào)制，得到的顯微像存在假像，需要校正CTFi(s)Envi(s)是校正的關(guān)鍵因素Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法基于正弦高斯校正和樣條插值的CTF校正模型低頻階段采用正弦調(diào)制高頻階段采用高斯調(diào)制Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法基于正弦高斯校正和樣條插值的CTF

18、校正模型重構(gòu)中存在放縮，傅里葉半徑不一定是整數(shù)，所以要插值采用線性插值算法精度不高，應(yīng)用三次樣條插值算法Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法ISAF密度函數(shù)快速計(jì)算模型密度函數(shù)快速計(jì)算方法，將其時(shí)間復(fù)雜度降低一個(gè)冪次基于60對稱性的快速映射方法，將計(jì)算量降低60倍基于徑向采樣點(diǎn)旋轉(zhuǎn)角度不變性的快速映射方法，計(jì)算量降低（Rm+1）/2倍Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法重構(gòu)結(jié)果投影模板取向中心Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法ICTISAF的性能比較Cryo-EMHBV乙肝病毒(HBV)重構(gòu)Cryo-EM基于球諧函數(shù)的三維重構(gòu)算法鯉魚呼吸腸道病毒(GCVR)重構(gòu)基于球諧函數(shù)的三維

19、重構(gòu)算法Cryo-EMCryoEMICTEM軟件包Cryo-EMCryoEMICTEM軟件包Cryo-EMCryoEMICTEM軟件包10Cryo-EMCryoEMICTEM軟件包Cryo-EMIve got a structure, what next?研究趨勢FittingCryo-EMIve got a structure, what next?研究趨勢Modeling + dockingCryo-EM一、冷凍電鏡三維重構(gòu)簡介二、CryoEM面臨的科學(xué)問題三、CryoET面臨的科學(xué)問題Outline生物圖像三維重構(gòu)的高性能算法研究活體、組織、器官細(xì)胞細(xì)胞器蛋白復(fù)合體1m1mm1um1nm

20、蛋白質(zhì)核酸分子原子光學(xué)顯微鏡掃描共聚焦顯微鏡STED顯微鏡電子顯微鏡X射線晶體學(xué)醫(yī)學(xué)CT成像Cryo-ET生物圖像三維重構(gòu)的高性能算法研究Cryo-ET活體、組織、器官細(xì)胞細(xì)胞器蛋白復(fù)合體1m1mm1um1nm蛋白質(zhì)核酸分子原子光學(xué)顯微鏡掃描共聚焦顯微鏡STED顯微鏡電子顯微鏡NMR、X射線晶體學(xué)醫(yī)學(xué)CT成像醫(yī)學(xué)CT、光學(xué)成像NMRX-Ray冷凍電鏡電子斷層三維重構(gòu)和光電聯(lián)合成像技術(shù)彌補(bǔ)了研究尺度與分辨率兩方面空白 冷凍電子斷層三維重構(gòu)問題描述Source:Projection imagesGoal:3D reconstructionCryo-ET生物制樣 樣品冷凍拍攝 數(shù)據(jù)采集 圖像處理和對

21、位 三維重構(gòu) 結(jié)構(gòu)分割、分析 冷凍電子斷層成像流程Cryo-ETProblems in CryoETNoise (SNR very low)Image alignmentMiss wedgeImage size (huge memory requirement)Computational timeCryo-ETProblems in CryoET投影圖像對位，是影響重構(gòu)質(zhì)量的關(guān)鍵因素投影圖像不對位Cryo-ETProblems in CryoET投影圖像信噪比極低Caveolae of PAE cell-60 -50 Cryo-ETProblems in CryoET投影角度無法覆蓋整個(gè)180

22、 ，投影數(shù)據(jù)不完整missing wedgeCryo-ETProblems in CryoET三維重構(gòu)計(jì)算時(shí)間極其漫長電鏡投影圖片數(shù)量和尺寸不斷增加（4K 4K, 8K 8K）生成三維重構(gòu)文件巨大（約7GB）達(dá)到滿意結(jié)果需要迭代幾十次Cryo-ETResearch Areas Improve resolutionImage alignment (SAMA method)Reconstruction algorithm (ASART iterative) Refine ETReconstruction AlgorithmsSpeedupParallel strategyData structur

23、eAsynchronous communication schemeCryo-ETImage alignment A snapshot of the sample in space (single rotation axis).Cryo-ETImage alignment CryoETMarker Free Auto Alignment (SIFT based)Qi Chu, et.al. BIBM. 2011Image alignment CryoETfeature extraction SIFT (scale invariant feature transform)feature matc

24、hing neighbor scope constraintepipolar constraintImage alignment CryoETfeature trackingexhaust searchingneighbor limited searchingprojection modelwhere is the is the calibration matrix of camera, is the projection matrix, is an orthogonal matrix, which also can be written as , withImage alignment Im

25、age alignment To estimate the parameters of the projection matrix, we have the cost function as:robust bundle adjustmentImage alignment nonoyesyesImage alignment CryoETcross section of reconstructionlongitudinal section of reconstructionIMODSAMAExperiment.1 mitochondrionImage alignment CryoETa simil

26、ar x-y section of reconstructioncoarse alignmentSAMA alignmentfiducial marker alignmenta similar x-z section of reconstructionExperiment.2 caveola3D reconstruction methods CryoETART (line-by-line updating policy)SIRT (pixel-by-pixel updating policy)SART (direction-by-direction updating policy)Previo

27、us Iterative algorithm3D reconstruction methods CryoET自適應(yīng)聯(lián)合代數(shù)迭代算法:ASART 初值：反投影算法 (Backprojection BPT)投影數(shù)據(jù)訪問方式： 多級(jí)獲取策略(multi-level scheme,MLS)松弛因子：自適應(yīng)原則差值補(bǔ)償：自適應(yīng)補(bǔ)償（權(quán)因子+像素值）3D reconstruction methods CryoETWBPSARTASARTExperiment 1. mitochondrion3D reconstruction methods CryoETExperiment 1. caveolaWBPSAR

28、TASARTGPU in 3D reconstruction of ETCryoETThe high computational demand of 3D reconstruction in ET is a challenging problem.Large reconstruction files (the size and number of the images increase) e.g. 119 images with size of 2048*2048 2048*2048*430*4B7GBConsiderable processing timeParallel reconstru

29、ction on Multi-GPUsCommunication between multi-GPUs due to overlapping of blobs Synchronous communication provided by CUDA leads to GPU sits idle.W is too large to be located into the GPUs especially when the size of the projected images is very large.more than 896MB of memory in GTX295GPU in 3D rec

30、onstruction of ETCryoETMultilevel parallel strategy for blob-based iterative reconstructionAsynchronous communication schemeBlob-ELLR format with symmetric optimization techniquesXH Wan, et.al. BMC Bioinfor. 2011ATOM softwareCryoET or （online）Unraveling the Cell Nucleus and Neuroscience via Electron

31、 tomography Technique (P53 Gene) NCMIR (UCSD)Large-scale reconstructionOngoing projectCurvilinear projection modelOngoing projectExperimental results-a synapse of a mouse brainOngoing projectX-Y sectionY-Z sectionX-Y sectionY-Z sectionASART reconstruction combined with a straight projection map. Res

32、ults were obtainedafter 50 iterations.Result of ASART combined with a curvilinear projection map. Results were obtained after 50 iterations.Experimental results-a synapse of a mouse brainOngoing projectX-Y sectionY-Z sectionX-Y sectionY-Z sectionASART reconstruction combined with a straight projecti

33、on map. Results were obtainedafter 50 iterations.Result of ASART combined with a curvilinear projection map. Results were obtained after 50 iterations.Serial Sections/ Montage reconstructionOngoing projectZ directionX-Y directionAcknowledgementTHANKSGPU in 3D reconstruction of ETCryoETMultilevel par

34、allel strategy (Coarse-grained scheme) Volume: set of 2D slicesSlab i-1Slab iClassification of slices in a slabGPU i-1GPU i.uniqueuniqueuniqueredundant .ownedgeredundantRedundant: come from neighbor slabsUnique: reconstructed in own slabsEdge: require information from redundant slicesOwn: do not require information from redundant slicesGPU in 3D reconstruction of ETCryoETMultilevel parallel strategy (Fine-grained scheme) for i slabs in the reconstructed volume for s in all slices of the ith slab for t in N iterations of the sth slice Decidemap for the sth slice;