面向SAM基因序列的压缩算法及并行化研究

作     者：法虎 

作者单位：南京邮电大学 

学位级别：硕士

导师姓名：陈国良

授予年度：2023年

学科分类：0831[工学-生物医学工程（可授工学、理学、医学学位）] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0836[工学-生物工程] 

主      题：SAM 基因序列压缩 并行优化 分布式存储 分布式计算 

摘      要：精准医疗的实施、新型药物的研制以及遗传规律的揭示离不开基因数据的强大支撑。随着大型基因测序项目的不断涌现,SAM基因序列的数据量呈现爆炸式增长。为了降低海量SAM基因数据的存储成本,数据压缩技术显得尤为重要。无参考序列的压缩方法灵活性高,但现有的算法在编码过程中没有充分利用SAM文件中包含的关联信息,并且在压缩QUAL字段时只考虑原始次序下的冗余。此外,现有算法的并行处理受限于单台机器内部的多线程操作,无法满足高性能的需求。论文主要研究SAM基因序列的数据压缩及并行算法,为基因测序相关应用提供技术支撑,主要贡献如下:(1)针对目前无参考序列算法压缩率低的问题,提出一种基于假设参考序列和两级重排序的压缩算法ZSAM。该算法对QUAL字段按照频率评分和图相似度评分进行排序,增加局部冗余度。引入CIGAR字段对RNAME可用的SEQ序列进行差异编码。通过布隆过滤器来构造高质量索引,并对RNAME不可用的SEQ序列进行匹配编码。根据剩余字段的类型和变化特征,分别选择适当的编码和压缩工具。实验结果表明,ZSAM算法的压缩率优于现有无参考序列算法。(2)针对并行压缩算法的速度受到单机限制的问题,提出一种基于Spark的SAM基因序列并行压缩算法ZSAM-Spark。该算法对SAM文件进行细粒度分区,同时避免任务之间的数据倾斜问题。通过使用丰富的RDD算子,设计一种高效且容错性强的并行压缩流程。在Spark Application中,采用多线程的方式对多个Job进行并行处理,并利用高性能的序列化机制降低Shuffle过程中数据传输的成本。实验结果表明,ZSAM-Spark适用于分布式场景,能够有效提升压缩速度。(3)针对目前压缩算法在实际场景中应用不足的问题,设计并实现了一个面向SAM的基因压缩及并行化系统。不仅实现核心服务的负载均衡及高可用,同时在功能模块设计中充分考虑用户的多样化需求。基于多Master多Slave架构,实现任务的异步提交和实时监控,从而保证系统的灵活性和稳定性。