Accurate Sequence Alignment Using Distributed Filtering on GPU Clusters

C. Victor Jongeneel, University of Illinois at Urbana-Champaign

Usage Details

Modern gene sequencing machines generate enormous amount of genomic data in the span of a few hours. A fundamental problem is aligning these short sequence reads back to a reference genome. This project introduces a new technique to find all the matches within a pre-specified edit distance. It first uses a distributed filter based on the pigeonhole principle to find all potential matches. The filter is fast, but allows false positives. The filtered matches are then passed to GPUs as hardware accelerators to accurately weed out all false positives by applying a GPU-specific algorithm derived from the classic Needleman-Wunsch. In the end, our results are exact: There will neither be a false positive nor a false negative.