生物信息学GPU解决方案

 

生物信息学是一门新兴的交叉学科。利用计算机科学来分析生物学数据,可以发现隐含在数据中的生物学知识,可以在实验之前给出较准确的预测,也可以为实验的设计提供指导方向。在生物数据爆炸式增长的今天,同计算机密切结合的生物信息学成为生物学研究中不可缺少的工具,具备重要的应用价值。对计算机科学的研究者来说,生物信息学是一个综合的应用方向,它结合了算法设计,数据挖掘,模式匹配,高性能计算,程序优化等领域,具备重要的研究价值。生物信息学的算法有很多,总体来说一部分算法侧重于正确性和敏感度,比如蛋白质结构预测;而一部分算法侧重于较快的执行速度,比如在数据库中搜寻序列。为了提高运算速度,可以使用专用的加速卡,FPGA设备,以及高性能集群。前两种解决方案的通用性较差,一般只能针对特定的问题购买特定的设备。构建高性能集群是一种通用性较好的方案,但成本较高,不适用于小规模的研究机构。CUDA平台的出现则提供了一种廉价而且有效的加速手段,使很多生物信息学应用在普通计算机上就可以得到较好的加速。同时CUDA设备也可以用于构建大型的计算服务器,提供比普通集群更高的性能以及更低的成本和功耗。研究生物信息学算法在CUDA上的加速是一个重要的研究方向,同时也是CUDA的重要应用方向。

 

CUDA上的Voting算法

1、模体发现问题简介

    在生物信息学中,一个主要研究方向是对模体(motif)的研究。模体是DNA或蛋白质序列中,有特定生物学意义的短串。在转录的基因的表达中,很大程度上会受到核苷酸序列中一些较固定的短串控制,称为DNA模体。DNA模体本一般均处在受调控基因的上游区域,转录因子可识别这些Motif并与之结合,从而调节DNA的代谢和转录。在蛋白质序列中,也存在一些特殊的序列片段具备某种保守性。这种保守性与蛋白质的生物活性有关或折叠方式有关,从而可以用于蛋白质识别、分类和预测。因此模体发现问题是生物信息学中的一个基本而重要的问题。模体发现问题可以简单描述为,在一组由有限的特定字符集组成的序列中,找到一个较频繁的出现的短串。如果用汉明距离评价,该短串在每个的序列中都存在一个编辑距离不超过特定值的变异子串。模体发现可以不指定模体的长度,由算法自动寻找可能性最高的短串,也可以手动指定目标模体的长度,以缩小搜寻的范围。一般情况下,DNA模体的长度在1020个碱基对,蛋白质模体的长度在510个氨基酸。

PevznerSze提出了一种描述模体发现问题的模型,称为(1d).模型。在这个模型中,给定t个长为W序列,序列中的字符都取自一个字母表Σ。在给定两个参数ld,满足04d<l<W,其中l代表模体的长,d代表模体变种和模体之间的汉明距离。如果在各个序列中都能找到一个长度为l的短串,并且和模体候选短串的距离不大于d,则该候选模体短串就是(1d).模型下的一个模体。有很多算法用于解决模体发现问题,这些算法大致可以分为两类,即确定性算法和非确定性算法。如果模体存在的话,确定性算法一定能够找到满足要求的模体,例如Voting算法,PMSPrune算法。而非确定性算法不一定能找到正确的模体,但算法速度较快,能够解决较大规模的计算任务,例如Gibbs采样算法,期望最大化算法以及随机投影法等。

下面将介绍用于DNA模体发现的Voting算法,以及Voting算法在CUDA平台上的实现及优化。

2 Voting算法

    DNA序列的字符集有4个元素ACG T,因此使用穷举法逐一验证所有的长度为l的短串,需要O(Wt41)的时间复杂度,只能适用于对于l较小的场合。Voting算法是一种确定性的模体发现算法,能够找到所有满足条件的模体,同时有效地降低了时间复杂度。Voting算法由Francis Chin提出,详述如下。记N(sd)是和字符串S的汉明距离为d的所有字符串的集合。将所有的长度为l的字符串视为候选模体,序列组中所有长度为l的子串si都给其对应的N(sid)O的元素投1票,那么最终从每个序列都得到了至少1票的候选模体就是满足(1d).模型的模体。

算法伪码如下:

l:建立两个H2LshvR并初始化每个元素为O。其中V表示每个候选模体获得的票数,

R指示每个同一个序列中的子串最多给一个候选模体投一票。

2 for i=1 to t