作为生物信息学的传统研究领域，生物序列分析得到了广泛的研究。然而，随着测序技术的发展，生物序列数据在规模和特性上都发生了改变，生物序列分析要求新的软件方法和计算平台。在分析大规模序列数据和解决复杂问题上，并行计算发挥着巨大的作用。在计算平台上，多核CPU和GPU逐渐成为并行计算的主流平台，一方面，多核CPU和GPU已经成为个人电脑、工作站和服务器的标准配置；另一方面，多核CPU和GPU组成的异构体系结构成为高性能计算领域一个重要的发展趋势。因此，研究基于多核CPU和GPU的生物序列分析并行算法具有重要意义。在这个背景下，本文从生物序列索引的构建、生物序列模体发现、高通量测序片段的纠错和定位三个方面出发，研究基于多核CPU和GPU的并行算法。这三个方面的研究是生物序列分析基础性的工作，它们的性能提升是生物序列分析广泛应用的前提。本文的主要工作和创新如下：1.针对快速构建生物序列索引的问题提出了基于多核CPU和基于GPU的两种并行Burrow-Wheeler变换算法。Burrow-Wheeler变换是生物序列索引中常用的数据结构，但是，长序列的Burrow-Wheeler变换在时间和空间上都存在很大的开销。本文分析了现有的两种空间有效的Burrow-Wheeler变换算法，根据它们的特点分别在多核CPU上和GPU上实现并行化。对于长序列的Burrow-Wheeler变换，我们提出的基于多核CPU的并行算法随着CPU核数量增加，能够获得接近线性的加速比，基于GPU的并行算法与原算法相比能够获得超过16倍的性能提升。对于人类全基因组的Burrow-Wheeler变换，基于多核CPU的并行算法在8核CPU上的性能与基于GPU的并行算法在NVIDIA GTX580上的性能相当，只需要不到4分钟的时间。除此之外，这两种并行算法都保持了原算法空间有效的特点。2.针对生物序列模体发现问题提出了一种精确的基于GPU的模体发现算法。生物序列模体发现可以形式化成一个算法问题，称为植入(l, d)模体问题，本文针对该问题，在样本驱动方法的基础上，使用完全簇表示模体。完全簇与现有算法中表示模体的簇相比，它的约束条件更为严格，也更为精确。我们在GPU上实现了完全簇搜索算法，实验表明，与现有的算法相比，本文提出的算法在长的弱模体发现上更加高效和更具扩展性。在NVIDIA GTX580上，它可以在5分钟内发现长模体(40,14)，而现有的最快的算法至少需要5小时，而且，它是第一个能解决植入(25,10)和(27,11)模体问题的算法。此外，在多GPU系统中，随着GPU数量的增多，本文的算法能获得接近线性的加速比。3.针对大规模的高通量测序短片段的纠错问题提出了一种基于多核CPU的并行纠错算法。高通量测序产生的短片段规模很大，现有的算法在纠错过程需要耗费大量的时间和空间为短片段构建索引，其中，使用后缀数组比使用其他索引结构更为高效。本文在这个基础上，根据短片段纠错的特点改进了后缀数组索引的方法，它使用时间和空间上更为高效的部分后缀数组替代完整的后缀数组，同时使用多线程技术对构建部分后缀数组的过程实现并行化。实验表明该方法比原算法在时间和空间上更加高效，而且它支持多线程环境下的并行化，在多核平台上具有良好的可扩展能力。4.针对包含不同类型错误的高通量测序短片段的纠错问题提出了一种基于GPU的纠错算法。高通量测序错误类型有三种：替换、插入和缺失，不同的测序平台可能产生不同类型的错误，这使纠错过程变得更加复杂。针对这个问题，本文把非比对的纠错方法和多重比对的方法结合起来，它使用非比对的方法对短片段进行索引，然后根据索引的信息构建多重比对，通过多重比对发现短片段中所有类型的错误。但是，构建多重比对的过程很耗时，因此我们使用GPU对多重比对进行加速。实验表明本文提出的算法可以纠正任何类型的错误，和现有的算法相比它有更高的精度，同时通过GPU的加速，在速度上也可以与现有的算法媲美甚至更快。5.针对高通量测序长片段的k-失配定位问题提出了一种基于GPU的定位算法。高通量测序技术的发展使它们产生的片段越来越长，而现有的定位算法大多针对短片段，因此本文深入研究了高通量测序长片段的定位问题，为其中的k-失配问题提出了一种基于GPU的精确算法。我们根据鸽笼原理把长片段划分成多个短片段，在GPU实现基于Burrow-Wheeler变换的短片段精确查找，然后扩展到长片段的k-失配定位。实验表明，本文提出的算法能够高效地解决长片段的k-失配定位问题，它在定位精度和计算速度上都胜过现有的长片段定位算法。