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

Yingbo CUI; Chun HUANG; Tao TANG; Canqun YANG; Xiangke LIAO; Shaoliang PENG

doi:10.11959/j.issn.2096-0271.2020041

您当前的位置：

首页 >

文章列表页 >

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

TOPIC：MEDICAL BIG DATA | 更新时间：2024-06-03

- Parallel optimization of variation detection algorithms for large-scale genome data
- Big Data Research Vol. 6, Issue 5, Pages: 2020041-1(2020)
- 作者机构：
  
  1. 国防科技大学计算机学院，湖南长沙 410073
  2. 湖南大学信息科学与工程学院，湖南长沙 410082
  3. 国家超级计算长沙中心，湖南长沙 410082
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2020041
  CLC： TP391
- Online First：2020-09，
  
  Published：15 September 2020
- 稿件说明：
移动端阅览
Yingbo CUI, Chun HUANG, Tao TANG, et al. Parallel optimization of variation detection algorithms for large-scale genome data[J]. Big Data Research, 2020, 6(5): 2020041-1.
DOI：

Yingbo CUI, Chun HUANG, Tao TANG, et al. Parallel optimization of variation detection algorithms for large-scale genome data[J]. Big Data Research, 2020, 6(5): 2020041-1. DOI： 10.11959/j.issn.2096-0271.2020041.

摘要

序列比对和变异检测是基因组数据分析的基础步骤，是后续各种功能性分析的前提，也是基因组数据分析中最耗时的环节。为有效处理高通量测序技术产生的海量基因组大数据，采用OpenMP、MPI等技术，对序列比对算法和SNP检测算法进行了多级并行优化，并对相关算法进行了改进。在不同数据集和并行规模下的测试中，核心算法加速比达到9倍以上，大规模测试中算法的并行效率保持在60%以上，在保证精度的前提下获得了良好的并行性能和可扩展性，有效提高了基因组大数据变异检测的能力。

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.

关键词

Keywords

references

STEPHENS Z D , LEE S Y , FAGHRI F , et al . Big data:astronomical or genomical? [J ] . PLoS Biology , 2015 , 13 ( 7 ):e1002195.

MARX V . Biology:the big challenges of big data [J ] . Nature , 2013 , 498 ( 7453 ): 255 - 260 .

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.

LI H , HOMER N . A survey of sequence alignment algorithms for next-generation sequencing [J ] . Briefings in Bioinformatics , 2010 , 11 ( 5 ): 473 - 483 .

ALTSCHUL S F , GISH W , MILLER W , et al . Basic local alignment search tool [J ] . Journal of Molecular Biology , 1990 , 215 ( 3 ): 403 - 410 .

LI R , LI Y , KRISTIANSEN K , et al . SOAP:short oligonucleotide alignment program [J ] . Bioinformatics , 2008 , 24 ( 5 ): 713 - 714 .

JIANG H , WONG W H . SeqMap:mapping massive amount of oligonucleotides to the genome [J ] . Bioinformatics , 2008 , 24 ( 20 ): 2395 - 2396 .

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.

HOMER N , MERRIMAN B , NELSON S F . BFAST:an alignment tool for large scale genome resequencing [J ] . PLoS One , 2009 , 4 ( 11 ):e7767.

SCHATZ M C . CloudBurst:highly sensitive read mapping with MapReduce [J ] . Bioinformatics , 2009 , 25 ( 11 ): 1363 - 1369 .

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 .

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 .

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 .

LI H , DURBIN R . Fast and accurate short read alignment with Burrows-Wheeler transform [J ] . Bioinformatics , 2009 , 25 ( 14 ): 1754 - 1760 .

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 ).

LI R , YU C , LI Y , et al . SOAP2:an improved ultrafast tool for short read alignment [J ] . Bioinformatics , 2009 , 25 ( 15 ): 1966 - 1967 .

LI R , LI Y , FANG X . SNP detection for massively parallel whole-genome resequencing [J ] . Genome Research , 2009 , 19 ( 6 ): 1124 - 1132 .

TANG J , LEUNISSEN J A M , VOORRIPS R E . HaploSNPer:a web-based allele and SNP detection tool [J ] . BMC Genetics , 2008 , 9 ( 1 ).

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 ).

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 ).

LI H , HANDSAKER B , WYSOKER A . The sequence alignment/map format and SAMtools [J ] . Bioinformatics , 2009 , 25 ( 16 ): 2078 - 2079 .

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 .

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 .

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.

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 .

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 .

LANGMEAD B , SCHATZ M C , LIN J . Searching for SNPs with cloud computing [J ] . Genome Biology , 2009 , 10 ( 11 ).

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 ).

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 .

彭绍亮 , 牛琦 , 李肯立 , 等 . 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 .

彭绍亮 , 杨顺云 , 孙哲 , 等 . 生物效应大数据评估聚类算法的并行优化 [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 .

SCHINDLER M , . A fast block-sorting algorithm for lossless data compression [C ] // The Conference on Data Compression . Piscataway:IEEE Press , 1997 .

Views

773

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Parallel optimization for clustering algorithm of large-scale biological effect evaluation

Related Author

Shaoliang PENG

Shunyun YANG

Zhe SUN

Minxia CHENG

Yingbo CUI

Xiaowei WANG

Fei LI

Xiaochen BO

Related Institution

College of Computer Science and Electronic Engineering ＆National Supercomputer Centre in Changsha,Hunan University

Department of Computer Science, National University of Defense Technology

Academy of Military Medical Sciences

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273228 Visits Today：134

⁰