面向新一代测序大数据量的计算模型与体系结构研究

lovegene

面向新一代测序大数据量的计算模型与体系结构研究
重点从计算模型和计算机体系结构方面研究新一代测序所面临的计算与存储瓶颈，基本技术路线是：1、深入发掘哈希索引（Hash indexing）算法的潜力，实现高效的读段回帖和拼接算法；2、充分利用基因组数据自身特点，研究数据压缩和冗余数据删除技术，实现高效的数据压缩与存储方法；3、参考分布式并行系统和MapReduce编程模型，研究实现针对高密度压缩海量基因组数据的搜索核心算法；4、在计算机体系结构方面，通过提取各种测序数据处理算法的核心特征，研究可重构计算技术的混合异构系统结构及其编程模型，利用可重构计算技术突破商业处理器中的指令集和系统结构的限制，实现序列回帖、数据压缩及传输、数据检索等核心算法的加速。本课题是面向新一代测序数据所提出的现实和未来需求的探索性研究，研究成果将不但是生物信息学领域的创新，也将是对计算、存储技术自身的重要创新。
以最常用的短序列回帖和拼接算法为例，目前方法都采用哈希索引和动态规划方法提高程序效率，进一步分析表明，影响算法性能的主要原因有：哈希索引表没有数据局部性，导致CPU的缓存命中率低；建立索引需要消耗大量内存；缺乏针对性的计算指令，大量的高并行度位运算只能在CPU中低效率进行；动态规划中数据紧耦合，在CPU难以并行，需要脉动阵列并行系统；通用CPU中强大的浮点运算单元和深度流水线技术在基因序列数据运算中得不到有效利用甚至可能带来负面影响。
基于这些分析和对计算机体系结构发展历程的研究，我们设想提出新型的可重构的体系结构以满足深度测序数据处理需求，利用商业的双CPU系统设计，包含一个X86CPU和标准芯片组和基于FPGA的可重构协处理器，动态地载入针对不同应用优化的指令，配备大容量高宽带内存系统和统一编址的内存空间，X86指令和协处理器扩展指令在同一个虚地址和实地址空间中执行。在新的结构中，我们拟对测序数据处理程序进行重新设计，解决哈希表和动态规划计算中的性能瓶颈，发展深度测序数据处理的软件包，预期处理速度至少可以比现有基于CPU的系统高出一个数量级以上。
数量巨大且不断增加的数据量是新一代测序对信息技术的一大挑战，我们将从数据压缩方法和存储方法两方面进行深入研究。基因序列数据有很多自身的特点，我们希望利用这些特点，通过改进基于参考序列的压缩方法达到对巨量测序数据的高密度压缩，而这其中同样涉及到高效的序列回帖算法问题。我们将把序列回帖与拼接和数据压缩结合起来研究，发展高效的条件压缩方法，并通过考虑序列的生物学性质帮助提高压缩率。
目前的测序数据存储主要依赖传统的磁盘阵列技术，随着数据量超摩尔定律速度的增长，预计近三五年内，一个基因组数据中心需要存储和访问的数据量将达到EB（260）量级，远非当前的磁盘阵列技术能够解决，十分需要前瞻性地对存储方法和系统结构进行研究。这里的主要问题是存储容量和访问速度。在硬件层次，采用分层管理的异构介质分级存储系统是拟发展的方向，将SSD固态硬盘、磁盘、磁带、光盘等不同存储介质通过高速网络整合成透明的逻辑存储池，辅以高效能动态分级存储管理软件，有效解决数据中心内冷热数据的合理存放，在可以控制的成本内实现EB级存储。在软件层次，深入研究面向基因组序列的冗余数据删除技术以降低对物理存储容量的需求，结合高性能序列数据计算系统实现在有限的计算代价下高效的冗余数据删除。针对访问速度问题，拟采用集群化Scale-out的方法解决数据I/O瓶颈问题，通过多个廉价X86处理节点达到比传统高端存储更优的性能。
从海量的数据进行检索和查询是测序数据应用中的一个基本需求。基因组数据属于比较典型的非结构化数据，无法利用现有数据库技术进行高效的检索与查询，存储经过高度压缩的数据更增加了检索和查询的难度。我们将充分考虑测序数据在压缩、存储和处理方案上的特点，参考分布式并行系统和针对大规模数据的MapReduce编程模型，研究发展适应海量基因组数据的搜索引擎核心算法和软件。