基于CUDA的多序列比对并行算法的设计与实现开题报告

1.1研究背景

(1)蛋白质序列研究

蛋白质作为生命现象的物质基础之一，是构成一切细胞组织结构的重要组成成分，参与了生物体内许多方面的重要生命过程，是生命活动的重要承担者。虽然说脱氧核糖核酸(DNA)是遗传信息的载体，但是遗传信息的复制、转录和表达都需要依靠各种蛋白质之间的协作才能完成。蛋白质组学较之于基因组学，对于生命现象的解释更直接、更准确，近年得到了快速发展，并受到世界各国学者的高度关注。在后基因组时代，随着蛋白质测序技术的飞速发展，蛋白质序列的数据呈爆炸性增长，目前在著名的蛋白质数据库uniprotkb中，已经存有超过120,243,849条蛋白质的一级序列信息(截止到2018-07-16)，并继续保持快速增长的趋势。然而，对于构成基因家族的成组的序列来说，我们要建立多个序列之间的关系，这样才能揭示整个基因家族的特征。多序列比对在阐明一组相关序列的重要生物学模式方面起着相当重要的作用。

（2）序列比对算法

所谓的序列比对，就是两个或者多个序列按照碱基排列进行比较，从而反映片段之间的相似性和阐明序列的同源性。这里主要是将未知功能的序列与已知序列进行比对，从而确定序列分析。序列比对的基本思想是，基于生物学中序列决定结构，结构决定功能的普遍规律，将核酸序列和蛋白质一级结构上的序列都看成由基本字符组成的字符串，检测序列之间的相似性，发现生物序列中的功能、结构和进化的信息。序列比对也可分为双序列比对和多序列比对，多序列比对是双序列比对的扩展，难度也更大。序列比对是生物信息学中最基本的运算 , Needleman 等最早将动态规划方法引入到生物序 列比对中, 提出了 Needleman-Wunsch 算法^[1],实现序 列的全局比对.Smith 等改进了 Needleman-Wunsch 算法 ,提出了著名的 Smith-Waterman(SW)算法^[2], 实现序列的局部比对.虽然 SW 算法能良好地表示 2 个比对序列的相似性 ,但计算速度非常慢,其时间复杂度为 О(mn),其中 m , n 分别表示进行比对的 2 条序列字符串的长度.为了降低 SW 算法的复杂性, Altschul^[3]等和 Rearson^[4]等提出了一系列启发式算法,这些算法虽然在速度上有很大改进 ,然而却是以牺牲比对结果的质量为代价.

（3）CUDA平台

随着越来越多的基因组序列被测定,生物序列变得越来越庞大,对比对算法性能的提高、效率的改善提出了更高的要求。与此同时,多核 众核体系架构的引入使得计算 机的计算能力成倍增长 .GPU 的并行处理能力越来越强大,而且不再拘泥于传统的图形处理,开始辅助CPU 完成图形计算以外的运算.如果能充分利用 GPU 的并行处理能力,与单纯的 CPU 计算相比, 计算性能可得到很大的提升(如下图1.1与图1.2)。

图1.1：GPU和CPU每秒浮点操作数

图1.2：GPU与CPU存储器带宽

CUDA(Compute Unified Device Architecture)^[5]，是显卡厂商NVIDIA推出的运算平台。CUDA是一种由NVIDIA推出的通用并行计算架构，该架构使GPU能够解决复杂的计算问题。它包含了CUDA指令集架构(ISA)以及GPU内部的并行计算引擎。开发人员可以使用C语言来为CUDA架构编写程序，C语言是应用最广泛的一种高级编程语言。所编写出的程序可以在支持CUDA的处理器上以超高性能运行。CUDA3.0已经开始支持C 和FORTRAN,如图1.3。

图1.3：CUDA设计为支持多种语言和应用编程接口

1.2 研究目的及意义

多序列比对有时用来区分一组序列之间的差异，但其主要用于描述一组序列之间的相似性关系，以便对一个基因家族的特征有一个简明扼要的了解。多序列比对的目标是使得参与比对的序列中有尽可能多的列具有相同的字符，即，使得相同残基的位点位于同一列，这样以便于发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系。通过对生物核酸序列的分析，人们希望找到基因和基因调控序列，揭示生物的遗传和进化规律。此外，通过基因比对还可以进一步预测蛋白质的结构和功能，如预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。而蛋白质是生命存在的物质基础，在细胞生命活动的各个方面发挥着各种各样的作用，如决定生物的结构和性状、参与基因的表达和调控，负责生物化学的催化等等，对现代生物研究具有重大的意义。