论文部分内容阅读
基因组测序是生物信息学最基本、最重要的研究领域之一。在测序的过程中,生物信息学手段是完成序列组装和比对分析的关键。第二代测序技术的出现,使个体基因组测序成为可能。但与传统测序技术相比,来自新测序平台的测序片段(称为:read)更短,测序精度和测序覆盖度更高。高通量的测序数据带来了基因组绝对数据量的巨大增加,为短序列的比对与组装算法带来了新的挑战。本文探讨了生物信息学中基于第二代测序技术的两个问题:短序列比对与短序列组装,叙述了在可变剪接分析软件AltSplice及motif识别算法的并行优化两方面的工作。本文的主要贡献如下:
1.提出了一种基于参考序列索引的高效短序列回贴(remapping)算法SRMA(Short Reads ReMapping Algorithm)。SRMA算法对参考序列压缩存储,对短序列分三段定位。在短序列与其目标区域之间允许出现不超过两个失配的情况下,可以回贴不超过72bp长的短序列。SRMA算法在确保高查全率和查准率的情况下,使用更少的内存。在实际测序数据和模拟测序数据上的测试表明,相比于其他流行的短序列回贴程序,基于此算法的程序SRMP(Short Reads ReMapping Program)在运行速度、精确性以及内存消耗上都处于领先水平;
2.提出了一种基于de Bruiin图的短序列组装算法DSSA(De novo ShortSequences AssemblyAlgorithm)。DSSA算法先对待组装数据进行比对和纠错处理,然后构造de Bruijn图进行组装。在测试数据集上的实验表明,DSSA算法在长短混合的测序数据组装方面取得了很好的组装结果,是对第二代测序技术短序列组装问题的成功尝试;
3.分析短序列回贴问题的并行处理方法,在对参考序列进行分布式散列实验的基础上,提出了适合短序列回贴问题的并行多线程方法,实现了并行多线程的SRMP程序。通过对实际测序数据及大规模模拟数据的分析得出,并行多线程的SRMP程序能够完成大规模测序数据的回贴任务;
4.对生物信息软件的并行优化方法进行了总结,归纳了生物信息学软件在并行优化方面的几种并行策略。完成了两方面的并行优化工作:
1)可变剪接分析软件AltSplice的并行优化;
2)Motif识别方面的算法分析与Weeder算法的并行优化及实现;
5.为了加强生物信息资源共享,叙述了生物信息软件在中国国家网格的集成以及网格接口设计方面的部分工作。