大规模生物序列比对及其基于异构系统的并行处理技术研究

Biological sequence alignment is a fundamental research in bioinformatics. It is widely used in the research of phylogeny inference, protein structure and function prediction, and disease control. Due to its wide use, highly computational complexity, and massive data, multiple sequence alignment needs to support high performance computing urgently. On the other hand, with the development of high performance computing, it is an effective method to handle NP-hard biological problems on heterogeneous systems which combine CPU with GPU. This project investigates biological sequence alignment and its parallel processing techologies based on heterogeneous systems. First, a method is proposed to achieve load balancing by sequence data transformation. Then, many memory optimization methods, including a fully coalesced sequence accessing, similarity matrix storing and accessing, and scoring matrix computing and compressed storing, are developed to improve the performance of actual systems because of memory shortage. In the end, based on a memory pre-allocation and reuse strategy, a coarse-grained parallel algorithm for large-scale sequence alignment is proposed. This project will provide a useful tool for large-scale sequence alignment. It will also provide new ideas for other data-intensive applications, and then promote the development of related fields.

序列比对是生物信息学的基础性研究工作，已被广泛应用于进化分析、蛋白质结构和功能预测、疾病控制等方面。由于序列比对应用的广泛性、计算的复杂性以及海量的数据特征，对计算机性能提出了越来越高的要求，迫切需要高性能计算的支持。同时，随着高性能计算的快速发展，应用CPU+GPU异构系统求解各类NP-难解生物计算问题已变得越来越普及和流行。本项目研究大规模生物序列比对及其基于异构系统的并行处理技术。首先，对序列优化存储，设计异构系统负载平衡方法；然后，设计异构系统内存优化方法，包括满足合并访问条件的序列存储方法、相似矩阵存储和访问方式、得分矩阵压缩存储，解决由于异构系统存储空间的匮乏而导致的实际计算性能低下；最后，基于内存预分配和复用策略，提出粗粒度序列比对并行算法。本项研究将为生物信息学提供实际可用的序列比对工具，为设计其他数据密集型应用的异构系统解决方案提供新的思路，推动相关领域的发展。

序列比对是生物信息学的基础性研究工作，已被广泛应用于进化分析、蛋白质结构和功能预测、疾病控制等方面。由于序列比对应用的广泛性、计算的复杂性以及海量的数据特征，对计算机性能提出了越来越高的要求，迫切需要高性能计算的支持。同时，随着高性能计算的快速发展，应用CPU+GPU异构系统求解各类NP-难解生物计算问题已变得越来越普及和流行。本项目研究大规模生物序列比对及其基于异构系统的并行处理技术。首先，对序列优化存储，设计异构系统负载平衡方法；然后，设计异构系统内存优化方法，包括满足合并访问条件的序列存储方法、相似矩阵存储和访问方式、得分矩阵压缩存储，解决由于异构系统存储空间的匮乏而导致的实际计算性能低下；最后，基于内存预分配和复用策略，提出粗粒度序列比对并行算法。本项研究在三块NVIDIA GPU卡上进行性能测试，与传统的串行MAFFT 7.015算法相比，所提出的并行算法在Tesla K20m GPU上能取得11.28倍的加速。本项研究将为生物信息学提供实际可用的序列比对工具，为设计其他数据密集型应用的异构系统解决方案提供新的思路，推动相关领域的发展。