A scalable solution for finding overlaps between sequences using map-reduce

Abstract

The overlap stage of a string graph-based assembler is considered one of the most time- and space-consuming stages in any de novo overlap-based assembler. This is due to the huge output of the next-generation sequencing technology which is represented by hundreds of millions of reads. In this study, we take advantage of the MapReduce programming model to find the overlaps between sequences. The proposed solution is scalable and can handle huge input and output sizes that can not be handled in existing solutions. The solution achieves perfect linear performance scalability with increased number of processing nodes for huge data sets. The method optimizes the output size by reporting a string representing a suffix-prefix match once, even if this string is involved in multiple matches. Running the algorithm in an Amazon cloud environment has demonstrated substantially lower cost than using other state of the art techniques for solving the same problem. The solution has been implemented as a tool that is freely available for the research community. Copyright ISCA.