Zhang Feng, Liao Xiangke, Peng Shaoliang, Cui Yingbo, Wang Bingqiang, Zhu Xiaoqian, Liu Jie
Department of Computer Science, National University of Defense Technology, Changsha, 410073, China.
National Supercomputing Center in Shenzhen, Shenzhen, 518055, China.
Interdiscip Sci. 2016 Jun;8(2):169-176. doi: 10.1007/s12539-015-0127-6. Epub 2015 Sep 24.
' 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.
在基因组时代，DNA序列的从头组装对于生物学研究变得越来越重要。自人类基因组计划开展十多年以来，仍然存在一些挑战，并且正在探索新的解决方案以改进基因组的从头组装。基于字符串图理论的字符串图组装器（SGA）是为应对这些挑战而开发的一种新方法/工具。在本文中，通过对SGA的深入分析，我们证明基于SGA的序列从头组装是一个NP完全问题。根据我们的分析，SGA在内存消耗方面优于其他类似的方法/工具，但花费的时间要多得多，其中60 - 70%的时间用于索引构建。基于此分析，我们引入了一种混合并行优化算法，并在天河二号的并行框架中实现了该算法。使用不同的数据集进行了模拟。对于小尺寸数据，优化后的解决方案比以前快3.06倍，对于中等尺寸数据快1.60倍。结果表明性能有明显提升，并行FM索引构建具有线性可扩展性。因此，这些结果对提高DNA序列从头组装的效率有显著贡献。
