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

doi:10.11959/j.issn.2096-0271.2020041

Abstract

Abstract:

Sequence alignment and mutation detection are the basic steps of genomic data analysis.They are the premise of subsequent functional analysis,and the most time-consuming steps.In order to effectively deal with the massive genomic big data brought by high-throughput sequencing technology,MPI,OpenMP and other technologies to perform multi-level parallel optimization of sequence alignment algorithm and SNP detection algorithm were used.By testing on different data sets and parallel scales,the core algorithm reached more than 9x speedup,and the parallel efficiency remained above 60% in large-scale test.The improved algorithms obtain good parallel performance and scalability,that effectively improves the ability of genomic big data mutation detection.

Key words: sequence alignment, SNP, OpenMP, MPI

CLC Number:

TP391

Yingbo CUI, Chun HUANG, Tao TANG, Canqun YANG, Xiangke LIAO, Shaoliang PENG. Parallel optimization of variation detection algorithms for large-scale genome data[J]. Big Data Research, 2020, 6(5): 16-28.

Figures/Tables 14

References 32

[1]	STEPHENS Z D , LEE S Y , FAGHRI F ,et al. Big data:astronomical or genomical?[J]. PLoS Biology, 2015,13(7):e1002195.
[2]	MARX V . Biology:the big challenges of big data[J]. Nature, 2013,498(7453): 255-260.
[3]	KATHIRESAN N , TEMANNI R , ALMABRAZI H ,et al. Accelerating next generation sequencing data analysis with system level optimizations[J]. Scientific Reports, 2017,7(1):9058.
[4]	LI H , HOMER N . A survey of sequence alignment algorithms for next-generation sequencing[J]. Briefings in Bioinformatics, 2010,11(5): 473-483.
[5]	ALTSCHUL S F , GISH W , MILLER W ,et al. Basic local alignment search tool[J]. Journal of Molecular Biology, 1990,215(3): 403-410.
[6]	LI R , LI Y , KRISTIANSEN K ,et al. SOAP:short oligonucleotide alignment program[J]. Bioinformatics, 2008,24(5): 713-714.
[7]	JIANG H , WONG W H . SeqMap:mapping massive amount of oligonucleotides to the genome[J]. Bioinformatics, 2008,24(20): 2395-2396.
[8]	SMITH A D , XUAN Z , ZHANG M Q . Using quality scores and longer reads improves accuracy of Solexa read mapping[J]. BMC Bioinform, 2008,9(1):128.
[9]	HOMER N , MERRIMAN B , NELSON S F . BFAST:an alignment tool for large scale genome resequencing[J]. PLoS One, 2009,4(11):e7767.
[10]	SCHATZ M C . CloudBurst:highly sensitive read mapping with MapReduce[J]. Bioinformatics, 2009,25(11): 1363-1369.
[11]	CHEN Y , SOUAIAIA T , CHEN T . PerM:efficient mapping of short sequencing reads with periodic full sensitive spaced seeds[J]. Bioinformatics, 2009,25(19): 2514-2521.
[12]	CLEMENT N L , SNELL Q , CLEMENT M J ,et al. The GNUMAP algorithm:unbiased probabilistic mapping of oligonucleotides from next generation sequencing[J]. Bioinformatics, 2010,26(1): 38-45.
[13]	FERRAGINA P , MANZINI G . Opportunistic data structures with applications[C]// The 41st Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2000: 390-398.
[14]	LI H , DURBIN R . Fast and accurate short read alignment with Burrows-Wheeler transform[J]. Bioinformatics, 2009,25(14): 1754-1760.
[15]	LANGMEAD B , TRAPNELL C , POP M ,et al. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[J]. Genome Biology, 2009,10(3).
[16]	LI R , YU C , LI Y ,et al. SOAP2:an improved ultrafast tool for short read alignment[J]. Bioinformatics, 2009,25(15): 1966-1967.
[17]	LI R , LI Y , FANG X . SNP detection for massively parallel whole-genome resequencing[J]. Genome Research, 2009,19(6): 1124-1132.
[18]	TANG J , LEUNISSEN J A M , VOORRIPS R E . HaploSNPer:a web-based allele and SNP detection tool[J]. BMC Genetics, 2008,9(1).
[19]	DEREEPER A , NICOLAS S , LE C L . SNiPlay:a web-based tool for detection,Application to grapevine diversity projects[J]. BMC Bioinformatics, 2011,12(1).
[20]	TANG J , VOSMAN B , VOORRIPS R E . QualitySNP:a pipeline for detecting single nucleotide polymorphisms and insertions/deletions in EST data from diploid and polyploid species[J]. BMC Bioinformatics, 2006,7(1).
[21]	LI H , HANDSAKER B , WYSOKER A . The sequence alignment/map format and SAMtools[J]. Bioinformatics, 2009,25(16): 2078-2079.
[22]	DEPRISTO M A , BANKS E , POPLIN R . A framework for variation discovery and genotyping using next-generation DNA sequencing data[J]. Nature Genetics, 2011,43(5): 491-498.
[23]	RACZY C , PETROVSKI R , SAUNDERS C T . Isaac:ultra-fast whole-genome secondary analysis on Illumina sequencing platforms[J]. Bioinformatics, 2013,29(16): 2041-2043.
[24]	WEI Z , WANG W , HU P ,et al. SNVer:a statistical tool for variant calling in analysis of pooled or individual nextgeneration sequencing data[J]. Nucleic Acids Research, 2011,39(19):132.
[25]	KOBOLDT D C , CHEN K , WYLIE T ,et al. VarScan:variant detection in massively parallel sequencing of individual and pooled samples[J]. Bioinformatics, 2009,25(17): 2283-2285.
[26]	KOBOLDT D C , ZHANG Q , LARSON D E ,et al. VarScan2:somatic mutation and copy number alteration discovery in cancer by exome sequencing[J]. Genome Research, 2012,22(3): 568-576.
[27]	LANGMEAD B , SCHATZ M C , LIN J . Searching for SNPs with cloud computing[J]. Genome Biology, 2009,10(11).
[28]	ZHAO S , PRENGER K , SMITH L . Rainbow:a tool for large-scale wholegenome sequencing data analysis using cloud computing[J]. BMC Genomics, 2013,14(1).
[29]	LU M , ZHAO J , LUO Q . GSNP:a DNA single-nucleotide polymorphism detection system with GPU acceleration[C]// International Conference on Parallel Processing.[S.l.:s.n]. 2011: 592-601.
[30]	彭绍亮, 牛琦, 李肯立 ,等. CPU-MIC异构并行架构下基于大规模频繁子图挖掘的药物发现算法[J]. 大数据, 2019,5(2): 89-103.
	PENG S L , NIU Q , LI K L ,et al. A scalable CPU-MIC coordinated drug-finding tool by frequency subgraph mining[J]. Big Data Research, 2019,5(2): 89-103.
[31]	彭绍亮, 杨顺云, 孙哲 ,等. 生物效应大数据评估聚类算法的并行优化[J]. 大数据, 2018,4(3): 24-36.
	PENG S L , YANG S Y , SUN Z ,et al. Parallel optimization for clustering algorithm of large-scale biological effect evaluation[J]. Big Data Research, 2018,4(3): 24-36.
[32]	SCHINDLER M , . A fast block-sorting algorithm for lossless data compression[C]// The Conference on Data Compression. Piscataway:IEEE Press, 1997.

Metrics

Recommended 0

No Suggested Reading articles found!

算法1 遍历base_info的原始算法	算法2 遍历base_array的优化算法
for o_base = 0 to 3	for ix=0 to base_array_size
for q_score = q_max to 0	//likelihood computation
for coord = 0 to read_length	……
for strand = 0 to 1	end for
for k = 0 to base_info[index]
// likelihood computation
……
end for
end for
end for
end for
end for

基因型	计算机表示	索引
AA	0000	0
AC	0001	1
AG	0010	2
AT	0011	3
CC	0101	5
CG	0110	6
CT	0111	7
GG	1010	10
GT	1011	11
TT	1111	15

名称	详情
CPU	Intel Xeon E5-2692 v2
接口数/核数/线程数	2/12/2
时钟频率/GHz	2.20
L1/L2/L3,Cache/KB	32/256/30,720
内存大小/GB	64

进程数/个	1	2	4	8	16	32	64
时间/s	954	485	250	132	72	50	34

进程数/个	1	2	4	8	16	32	64
时间/s	104	125	126	122	126	127	128

Parallel optimization of variation detection algorithms for large-scale genome data

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 32

Related Articles 2

Metrics

Recommended 0

[1]	Zhenlong DENG, Zhiguang CHEN. An optimization of MPI-IO interface for non-volatile memory [J]. Big Data Research, 2021, 7(2): 172-181.
[2]	Shaoliang PENG, Shunyun YANG, Zhe SUN, Minxia CHENG, Yingbo CUI, Xiaowei WANG, Fei LI, Xiaochen BO, Xiangke LIAO. Parallel optimization for clustering algorithm of large-scale biological effect evaluation [J]. Big Data Research, 2018, 4(3): 24-36.