Accurate Sequence Alignment using Distributed Filtering on GPU Clusters

Farivar, Reza; Venkataraman, Shivaram; Li, Yanen; Chan, Ellick M.; Verma, Abhishek; Campbell, Roy H.

Permalink

https://hdl.handle.net/2142/18904 Copy

Description

Title

Accurate Sequence Alignment using Distributed Filtering on GPU Clusters

Author(s)

• Farivar, Reza
• Venkataraman, Shivaram
• Li, Yanen
• Chan, Ellick M.
• Verma, Abhishek
• Campbell, Roy H.

Issue Date

2011-05-03

Keyword(s)

• Sequence Alignment
• Clusters
• GPU

Abstract

Advent of next generation gene sequencing machines has led to computationally intensive alignment problems that can take many hours on a modern computer. Considering the fast increasing rate of introduction of new short sequences that are sequenced, the large number of existing sequences and inaccuracies in the sequencing machines, short sequence alignment has become a major challenge in High Performance Computing. In practice gaps as well as mismatches are found in genomic sequences, resulting in an edit distance problem. In this paper we describe the design of a distributed filter, based on shifted masks, to quickly reduce the number of potential matches in the presence of gaps and mismatches. Furthermore, we present a hybrid dynamic programming method, optimized for GPGPU targets, to process the filter outputs and find the accurate number of insertions, deletions and mismatches. Finally we present results from experiments performed on an NCSA cluster of 128 GPU units using the Hadoop framework.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/18904

Owning Collections