论文部分内容阅读
多序列比对(Multiple Sequence Alignment,MSA)是分析生物序列及其结构、功能,进化分析以及其他生物信息学中基础领域的关键步骤。随着下一代生物测序规模的大幅高,现有的多序列比对方法在大规模数据下已经体现出显著的性能瓶颈,甚至无能为力。针对该问题,本文出依据HDFS数据存储系统和Spark框架来加速多序列比对算法用于完成分布式多序列比对任务。本文完成了如下几个方面的工作:实现用于大规模蛋白质多序列比对的Smith-Waterman算法和用于大规模核酸多序列比对的后缀树后缀数组算法。Smith-Waterman算法是利用动态规划思想计算得分矩阵的局部最优比对算法,其比对结果质量高但较耗内存。后缀树后缀数组算法具有O(??????)的时间效率,比对质量可靠,且空间复杂度可通过前缀倍增优化到O(?)。该算法与Smith-Waterman算法的空间复杂度都能够依靠HDFS分布式存储系统进一步降低,具备稳定高可用性。针对Spark集群环境做深入的并行优化,充分发挥其弹性负载、内存均摊和分布式存储的优势。在负载均衡方面,通过自适应算法来调整“大变量”的广播,调整RDD算子中的块数量,高网络吞吐性能。在内存优化方面,优化数据结构和序列化对象调节内存回收和缓存大小。在分布式存储方面,利用HDFS存储大规模序列高容灾性。在工程实现方面,采用面向对象设计,轻耦合封装,利于日后的维护和算法扩展。将单机多线程环境下和集群环境下的一系列不同规模的蛋白质及核酸序列数据做横向对比,将目前最优秀的多序列比对软件如MUSCLE等与本文工具一起做纵向对比。结果表明,无论是在时间效率、内存效率、加速比还是结果质量上,基于Spark计算平台的大规模序列比对算法与其他各算法相比都有着更突出的表现,证明了本文工作的重要价值。最后,已将本文工作连接高性能分布式集群部署于网站上,供科研人员自由访问。