An efficient algorithm for DNA fragment assembly in MapReduce

作者：Xu Baomin^*; Gao Jin; Li Chunyan

来源：Biochemical and Biophysical Research Communications, 2012, 426(3): 395-398.

DOI：10.1016/j.bbrc.2012.08.101

• Eulerian superpath problem
• Parallel assembly
• Fragment assembly
• MapReduce

Fragment assembly is one of the most important problems of sequence assembly. Algorithms for DNA fragment assembly using de Bruijn graph have been widely used. These algorithms require a large amount of memory and running time to build the de Bruijn graph. Another drawback of the conventional de Bruijn approach is the loss of information. To overcome these shortcomings, this paper proposes a parallel strategy to construct de Bruijin graph. Its main characteristic is to avoid the division of de Bruijin graph. A novel fragment assembly algorithm based on our parallel strategy is implemented in the MapReduce framework. The experimental results show that the parallel strategy can effectively improve the computational efficiency and remove the memory limitations of the assembly algorithm based on Euler superpath. This paper provides a useful attempt to the assembly of large-scale genome sequence using Cloud Computing.

• 出版日期2012-9-28
• 单位北京交通大学; 唐山师范学院