基因组大数据变异检测算法的并行优化

崔英博，黄春，唐滔，杨灿群，廖湘科，彭绍亮

1. 国防科技大学计算机学院，湖南 长沙 410073；2. 湖南大学信息科学与工程学院，湖南 长沙 410082；3. 国家超级计算长沙中心，湖南 长沙 410082

1 引言

近年来，高通量测序技术的迅猛发展给生命科学带来了巨大变革，测序通量不断提高，测序成本不断下降，如单个人类基因组的测序成本逐年降低，基因组数据规模不断增长。基因组数据大约每7个月就会增加一倍[1]。现有服务器以及序列分析算法已经无法及时有效地处理如此大规模的数据，需要借助并行计算机的强大算力以及并行算法的有效支撑来实现对基因组大数据的有效处理[2]。

测序仪产生读段（reads）后，首先进行质量控制，去除测序质量较差的数据；然后进行序列比对，将读段回帖到基因组，找到读段最可能的起源位置，并输出比对文件；再基于比对文件检测基因组的变异情况，主要包括单核苷酸多态性（single nucleotide polymorphism，SNP）、插入删除变异（indel）、结构变异（structure variation，SV）和拷贝数变异（copy number variation，CNV）等；最后根据需要，进行特定的功能分析。序列比对和变异检测是基因组数据分析的基础环节，是后续功能性分析的基础，也是数据分析流程中最耗时的步骤[3]。

为有效处理高通量测序技术带来的海量基因组大数据，本文选取基因组变异检测中常用的序列比对和SNP检测两个步骤，对相关算法进行了改进，并利用OpenMP（open multi-processing）和消息传递接口（message passing interface，MPI）等并行技术实现了多级并行。在不同数据集和并行规模下的测试中，核心算法的加速比达到9倍以上，大规模测试中算法的并行效率保持在60%以上，在保证精度的前提下获得了良好的并行性能和可扩展性，有效提高了基因组大数据变异检测的能力。……