A Hybrid Parallel Strategy Based on String Graph Theory to Improve De Novo DNA Assembly on the TianHe-2 Supercomputer

作者：Zhang, Feng; Liao, Xiangke; Peng, Shaoliang^*; Cui, Yingbo^*; Wang, Bingqiang; Zhu, Xiaoqian^*; Liu, Jie

来源：Interdisciplinary Sciences, Computational Life Sciences, 2016, 8(2): 169-176.

DOI：10.1007/s12539-015-0127-6

• DNA sequence
• De novo assembly
• NP-complete
• Hybrid parallel optimization
• TianHe-2 supercomputer

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

• 出版日期2016-6
• 单位中国人民解放军国防科学技术大学; 国家超级计算深圳中心