结构生物信息学冷冻电镜的三维重构简介和科学问题

1、结构生物信息学冷冻电镜的三维重构简介和科学问题一、冷冻电镜三维重构简介二、CryoEM面临的科学问题三、CryoET面临的科学问题Outline 确定蛋白质结构的方法确定蛋白质结构的方法核磁共振X射线晶体衍射结构预测冷冻电镜小分子量蛋白蛋白质复合体小分子量蛋白膜蛋白和超大分子复合体背景简介背景简介 冷冻电镜的优势研究生物大分子结构的强有力手段。冷冻电镜重构技术在未来结构生物学中起到了一个联系的纽带基于CryoEM的多种技术的融合，被Science评选为2002年世界十大科技进展之一。Sali et.al. Nature (2003) Trends in Macromolecular CryoE

2、M 背景简介YearsNumber of Public Structures 冷冻电镜三维重构背景简介一、冷冻电镜三维重构简介二、CryoEM面临的科学问题三、CryoET面临的科学问题Outline 冷冻电镜三维重构处理流程生物制样 样品冷冻拍摄 数据采集 图像处理 三维重构 结构分析 评价 Chiu et.al. JEOL News (2006)Cryo-EM 冷冻电镜三维重构问题描述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单颗粒冷冻电镜三维重构200Cryo-EM 冷冻电镜三维重构问题描述9131212157123124579Cryo-EM 冷冻电镜三维重构问题形式描述Data:Unknown Parameters:Density:Rotations:Translations:Objective:C. Yang et.al. JSB (2005)Cryo-EM冷冻电镜三维重构基本思想基本思想：相同生物大分子某方向的投影，在实空间中经过调整，叠加平均，提高信噪比，使共同

4、部分的结构信息得到加强，最后对各种不同方向的投影在三维空间中进行重构,从而获得其三维结构信息。Cryo-EMroofdoorwindows65冷冻电镜三维重构基本思想3421颗粒挑选图像对齐图像分类确定方向三维重构结构分析Cryo-EM颗粒挑选Refine初始模型模型优化冷冻电镜三维重构的基本步骤Cryo-EM冷冻电镜三维重构的基本步骤Cryo-EM冷冻电镜三维重构的基本步骤Cryo-EM冷冻电镜三维重构的基本步骤Cryo-EM冷冻电镜三维重构的基本步骤Cryo-EM冷冻电镜三维重构结果：初始模型Cryo-EM冷冻电镜三维重构结果：第1次迭代Cryo-EM冷冻电镜三维重构结果：第2次迭代Cry

5、o-EM冷冻电镜三维重构结果：第3次迭代Cryo-EM冷冻电镜三维重构结果：第4次迭代Cryo-EM冷冻电镜三维重构结果：第5次迭代Cryo-EM一、颗粒图像信噪比极低二、三维重构计算时间极其漫长三、急需新的重构算法冷冻电镜三维重构面临的科学问题Cryo-EM颗粒图像信噪比极低颗粒图像信噪比极低电子成像技术样品不均一需采集大量图像数据如何快速、准确进行蛋白颗粒的挑选？手工挑选 半自动化200Cryo-EM颗粒图像信噪比极低要达到1精度，需要100万张分子颗粒图片Cryo-EM三维重构时间极其漫长数万数十万颗粒图像ClassificationAverageFourier TransformRef

6、inementAlignmentCross Common LineInverse Fourier TransformCryo-EM三维重构时间极其漫长Near-atomic Resolution Structures by Single Particle Cryo-EM ComplexPublicationSelected ParticlesSoftwareCPU hrsEffective resolution ()Modeling methodCPVNature (453) 15 May 200817,123IMIRS 1033.8Fourier-Bessel&球谐函数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 数据来自 “Current Opinion in Structural Biology” 2008, 18:218-228Cryo-EM急需新的重构算法现有算法绝大部分基于Fou

8、rier-Bessel模型，70年代初提出的。基于现有的算法，重构精度很难再提高如何进一步提高三维重构的精度？Cryo-EM一、颗粒图像的挑选 -颗粒图像识别软件Picker二、三维重构的高性能计算 -重构并行软件ParaEMAN三、重构结果精度优化 -原有算法的完善 -球面坐标系下的三维重构算法我们的工作Cryo-EM颗粒图像挑选 降噪处理原始图片一次降噪二次降噪三次降噪原始电镜图片01nov26b.001.003.001.001 ,来自SCRIPPSCryo-EM 当前研究现状 - 颗粒挑选Algorithms/Criteria for Particle Selection分类典型算法优点

9、缺点基于模板匹配Berns algorithmLudtkes algorithmPenczeks algorithmRosemans algorithmSigworths algorithm手工挑选模板借助3D参照结构实现简单如何保证模板无遗漏结果假阳性高基于特征Bajais algorithmHalls algorithmMallicks algorithmVolkmanns algorithmZhus algorithm少量样本集利用几何与统计信息自动化程度高特征提取困难低对比度图像效果差数据来自 “Nature Methods” 2008, 5(7): 651- 658 “Journal

10、 of Structural Biology” 2004, 145Cryo-EM颗粒挑选 当前研究现状 “Journal of Structural Biology” 145 （1-2）的统计结果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直方图信息熵的方法相关性匹配Adaboost方法基于样本空间分割的方法最小距离分类器贝叶斯分类器模板匹配特征学习开发了多种颗粒识别算法，实现了颗粒识别软件PickerCryo-EM颗粒图像挑选 基于直方图信息熵的方法算法实现（分成三级阈值匹配）：匹配“外围环”，计算公式：匹配“内圆”，计算公式：匹配“四分的网格”，计算公式：各级的阈值可由机器学习的方式得到Cryo-EM颗粒图像挑选 基于adaboost的方法弱分类器强分类器正例反例弱分类器错误率越小，就越小，就越大H(x)为+，则为正例； H(x)为-，则为反例Cryo-EM颗粒图像挑选Cry

12、o-EM颗粒图像挑选Cryo-EM一、颗粒图像的挑选 -颗粒图像识别软件Picker二、三维重构的高性能计算 -重构并行软件ParaEMAN三、重构结果精度优化 -原有算法的完善 -球面坐标系下的三维重构算法我们的工作Cryo-EM三维重构高性能计算 时间分析EMANModuleRatioClassalign250.59%Classesbymra224.86%Classesbymra121.52%Make3d1.61%Project3d0.65%Projtree0.03%Proc3d0.03%Refine12396.97%Cryo-EM三维重构高性能计算开发了单颗粒三维重构并行软件ParaEM

13、AN重构精度优化提出一种颗粒图像聚类优化的重构框架，重构结果精度提高重构速度优化基本操作时间比例优化方式并行策略投影(Projection)0.34%速度优化OpenMP分类(Classification)85.63%速度&精度优化MPI+OpenMP平均(Average)11%速度优化MPI+OpenMP重构(Reconstruction) 2.99% 速度优化OpenMPCryo-EM对原有算法进行了优化Recluster三维重构结果精度优化给定投影颗粒图像旋转平移对齐灰度值转换二维点拟合误差图像分类最小二乘直线拟合颗粒图像重聚类框架PRF：LY Fan, et.al. Bioinform

14、atics 2009Cryo-EM三维重构结果精度优化乙肝病毒 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乙肝病毒数据数据Cryo-EM三维重构高性能计算 核心问题n组图像数目差异很大目标1： N个图像的分类处理时间最短目标2：

15、尽可能使各处理器分配的任务平均Cryo-EM三维重构高性能计算 核心问题问题描述（Makespan Minimization)s : JP （J = 1,2n, P=1,2m)The finishing time of processor iThe makespan is: 强NP难问题Cryo-EM三维重构高性能计算 核心问题提出一种自适应任务动态调度算法Cryo-EM三维重构高性能计算 核心问题ParaEMAN任务调度实验结果Cryo-EM三维重构高性能计算 核心问题单颗粒三维重构并行软件-paraEMAN10Cryo-EMCryoEM EMAN的并行优化ParaEMAN在曙光5000上的

16、测试结果305.6445.4508.5Cryo-EMCryoEM EMAN的并行优化ParaEMAN在“超龙一号”的测试结果FSC曲线Cryo-EMCryoEM EMAN的并行优化“超龙一号”上ParaEMAN同EMAN的比较计算核数加速比Cryo-EM一、颗粒图像的挑选 -颗粒图像识别软件Picker二、三维重构的高性能计算 -重构并行软件ParaEMAN三、重构结果精度优化 -单颗粒三维重构软件ICTISAF我们的工作Cryo-EM基于球谐函数的三维重构算法理论基础0到4阶球谐函数的图形任何空间几何体表面都可以表示成球谐函数各分量的线性组合Cryo-EM基于球谐函数的三维重构算法开发完成了

17、20面体三维重构软件ICTISAF精度优化基于正弦高斯校正和样条插值的CTF校正模型基于滑动窗口的电镜照片全局插值算法速度优化密度函数快速计算方法基于径向采样点旋转角度不变性的快速映射方法基于60对称性的快速映射方法Cryo-EM基于球谐函数的三维重构算法基于正弦高斯校正和样条插值的CTF校正模型电镜成像时电子束经过电镜的调制，得到的显微像存在假像，需要校正CTFi(s)Envi(s)是校正的关键因素Cryo-EM基于球谐函数的三维重构算法基于正弦高斯校正和样条插值的CTF校正模型低频阶段采用正弦调制高频阶段采用高斯调制Cryo-EM基于球谐函数的三维重构算法基于正弦高斯校正和样条插值的CTF

18、校正模型重构中存在放缩，傅里叶半径不一定是整数，所以要插值采用线性插值算法精度不高，应用三次样条插值算法Cryo-EM基于球谐函数的三维重构算法ISAF密度函数快速计算模型密度函数快速计算方法，将其时间复杂度降低一个幂次基于60对称性的快速映射方法，将计算量降低60倍基于径向采样点旋转角度不变性的快速映射方法，计算量降低（Rm+1）/2倍Cryo-EM基于球谐函数的三维重构算法重构结果投影模板取向中心Cryo-EM基于球谐函数的三维重构算法ICTISAF的性能比较Cryo-EMHBV乙肝病毒(HBV)重构Cryo-EM基于球谐函数的三维重构算法鲤鱼呼吸肠道病毒(GCVR)重构基于球谐函数的三维

19、重构算法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一、冷冻电镜三维重构简介二、CryoEM面临的科学问题三、CryoET面临的科学问题Outline生物图像三维重构的高性能算法研究活体、组织、器官细胞细胞器蛋白复合体1m1mm1um1nm

20、蛋白质核酸分子原子光学显微镜扫描共聚焦显微镜STED显微镜电子显微镜X射线晶体学医学CT成像Cryo-ET生物图像三维重构的高性能算法研究Cryo-ET活体、组织、器官细胞细胞器蛋白复合体1m1mm1um1nm蛋白质核酸分子原子光学显微镜扫描共聚焦显微镜STED显微镜电子显微镜NMR、X射线晶体学医学CT成像医学CT、光学成像NMRX-Ray冷冻电镜电子断层三维重构和光电联合成像技术弥补了研究尺度与分辨率两方面空白 冷冻电子断层三维重构问题描述Source:Projection imagesGoal:3D reconstructionCryo-ET生物制样 样品冷冻拍摄 数据采集 图像处理和对

21、位 三维重构 结构分割、分析 冷冻电子断层成像流程Cryo-ETProblems in CryoETNoise (SNR very low)Image alignmentMiss wedgeImage size (huge memory requirement)Computational timeCryo-ETProblems in CryoET投影图像对位，是影响重构质量的关键因素投影图像不对位Cryo-ETProblems in CryoET投影图像信噪比极低Caveolae of PAE cell-60 -50 Cryo-ETProblems in CryoET投影角度无法覆盖整个180

22、 ，投影数据不完整missing wedgeCryo-ETProblems in CryoET三维重构计算时间极其漫长电镜投影图片数量和尺寸不断增加（4K 4K, 8K 8K）生成三维重构文件巨大（约7GB）达到满意结果需要迭代几十次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自适应联合代数迭代算法:ASART 初值：反投影算法 (Backprojection BPT)投影数据访问方式： 多级获取策略(multi-level scheme,MLS)松弛因子：自适应原则差值补偿：自适应补偿（权因子+像素值）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;