并行计算是解决单处理器速度瓶颈的最好方法,它能充分利用计算机硬件资源,实现程序的高效执行。它的研究方向包括：计算机并行硬件平台、并行软件、并行算法等。目前并行计算的现状是：并行算法发展的速度不及并行硬件性能增长的速度,一些现有的并行算法无法高效的利用并行硬件资源。高效并行算法的缺乏是发展并行计算很大的障碍。这种现状的一个很重要原因是并行算法的设计和优化要比串行算法复杂得多,例如计算子任务的划分、负载均衡、并行任务之间的通信和同步等。每一部分的设计都会影响算法最后的性能。所以研究如何设计出高效的并行算法具有重要意义。我们选取了生物信息学领域中的两个基础课题：蛋白质序列比对和DNA序列拼接,进行研究。它们是生物信息学领域最基础的课题之一,也是难度较大但十分有意义的课题,很多其他的课题都需要依托这两个基础算法。DNA序列是由4种碱基组成(ATCG),蛋白质序列包含20种氨基酸(amino acid) ,从计算机角度来看它们都是由一串字符组成。但根据实际操作的不同,我们需要采取不同的加速优化策略。序列比对是生物信息学的基本组成和重要基础。它的基本思想是基于生物学中序列决定结构,结构决定功能的普遍规律。通过检测序列之间的相似性,发现生物序列中的功能、结构和进化信息。因此蛋白质序列比对对于研究蛋白质在生物体中的作用功能,并研究它们的进化起源有重要价值。但是随着人类基因组计划的实施,蛋白质序列数据库的规模已呈指数增长,单纯的依靠串行的比对算法已经很难满足实际应用的需求,这就需要研究并设计高效的并行算法来加速蛋白质比对。我们利用最新的基于Intel MIC (Many Integrated Core,集成众核)架构的Xeon Phi协处理器,设计出了支持异构系统架构的蛋白质序列比对算法,XPFS,实现CPU和协处理器的高效并行工作。算法中我们实现了三级并行：指令集并行(例如利用SSE)、线程级并行和设备级并行。为了使硬件得到高效利用,我们采用动态任务分配的策略,由任务分配器将总的任务切割成小的任务块,每一个计算进程在完成当前任务块后,主动向任务分配器申请下一个任务块。由于任务块可以分割的比较小,所以避免了负载不均衡的问题。通过实际的实验测试,并与传统的PFSearch算法作比较,在保证比对结果相同的前提下,我们的算法获得了将近4倍的加速比。DNA序列包含生物体的最基本的遗传信息,是分子生物学研究的根本源头。获得生物体DNA全部序列对于揭示生命的本质具有重要意义。由于测序技术的局限,当前的测序仪只能一次读取很短的DNA片段(75～400bp),这对于分子生物学研究是远远不够的。序列拼接指的是通过联配和融合一些短的测序片段形成更长的DNA序列从而重构生物体DNA序列。这对于分子生物学是不可或缺的研究方向。序列拼接分为：全新拼接(de novo)和映射拼接(mapping assembly)。而全新拼接(de novo)一直是分子生物学领域研究的热点问题。它是在没有参照序列的前提下,将测序所得的reads片段,通过比对、连接、组装等步骤,最终尽量还原出原始的DNA序列。它的主要难点在于：reads片段数据量大、测序存在错误、没有参考基因组、DNA内部存在大量重复区域,内存需求大等,这都加大了全新拼接(de novo)的难度。我们根据拼接中的难点和现有基因拼接算法的不足,设计研发出全新的de novo拼接算法,ARCS。与其他算法不同,首先,ARCS将序列中的unique区域和repeat区域分开处理,降低repeat区域对后续拼接的影响。其次,在scaffold构建构成中,我们采用的是unique区域的全局最优排列,而不是局部最优。为了降低内存和加速算法,我们自行设计实现了性能良好的哈希表,缩短了kmer查找时间。通过实验,我们实际比较了ARCS和现有拼接算法的结果,ARCS在实验物种上取得了更长的拼接结果,时间内存都有明显的提升。