title: A Hybrid Parallel Strategy Based on String Graph Theory to Improve De Novo DNA Assembly on the TianHe-2 Supercomputer.
abstract: ' The de novo assembly of DNA sequences is increasingly important for biological researches in the genomic era. After more than one decade since the Human Genome Project, some challenges still exist and new solutions are being explored to improve de novo assembly of genomes. String graph assembler (SGA), based on the string graph theory, is a new method/tool developed to address the challenges. In this paper, based on an in-depth analysis of SGA we prove that the SGA-based sequence de novo assembly is an NP-complete problem. According to our analysis, SGA outperforms other similar methods/tools in memory consumption, but costs much more time, of which 60-70 % is spent on the index construction. Upon this analysis, we introduce a hybrid parallel optimization algorithm and implement this algorithm in the TianHe-2's parallel framework. Simulations are performed with different datasets. For data of small size the optimized solution is 3.06 times faster than before, and for data of middle size it's 1.60 times. The results demonstrate an evident performance improvement, with the linear scalability for parallel FM-index construction. This results thus contribute significantly to improving the efficiency of de novo assembly of DNA sequences.
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China.
authors.forename: Feng
authors.initials: F
authors.lastname: Zhang
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China.
authors.forename: Xiangke
authors.initials: X
authors.lastname: Liao
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China. pengshaoliang@nudt.edu.cn.
authors.forename: Shaoliang
authors.initials: S
authors.lastname: Peng
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China.
authors.forename: Yingbo
authors.initials: Y
authors.lastname: Cui
authors.affiliation: National Supercomputing Center in Shenzhen, Shenzhen, 518055, China.
authors.forename: Bingqiang
authors.initials: B
authors.lastname: Wang
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China. zhu_xiaoqian@nudt.edu.cn.
authors.forename: Xiaoqian
authors.initials: X
authors.lastname: Zhu
authors.affiliation: Department of Computer Science, National University of Defense Technology, Changsha, 410073, China.
authors.forename: Jie
authors.initials: J
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D023281:Genomics; D017422:Sequence Analysis, DNA; D012984:Software
keywords: DNA sequence; De novo assembly; Hybrid parallel optimization; NP-complete; TianHe-2 supercomputer