Scalable and Highly Parallel Implementation of Smith-Waterman

University of Arizona
posted on 06/08/2009

Background: The Smith-Waterman algorithm is widely used for local sequence alignment when determining similarities between biomolecule sequences, and is primarily used in DNA and protein sequencing. Smith-Waterman is considered a dynamic algorithm that provides the most accurate results when performing local sequence alignment in difficult-to-determine regions of proteins segments that show a low similarity between distantly related biological sequences resulting from evolutionary "noise." A major issue in current Smith-Waterman implementations, however, is that computational overhead is very high, making it a resource intensive algorithm. This problem is compounded by the rapid growth of available DNA and protein databases.

To resolve computational overhead problem, researchers at The University of Arizona developed a software method that utilizes NVIDIA's Compute Unified Device Architecture (CUDA) language, taking advantage of the processing power of NVIDIA's Graphical Processing Units (GPUs). This approach achieves performance gains with a reconfigured Smith-Waterman algorithm that is much faster than that of current technologies. This vastly improved speed will cut processing time and overhead for researchers that rely on the Smith-Waterman algorithm for their sequencing needs.

Stage of Development: The inventors have fully demonstrated this software package and its associated method.

Applications:
* Protein sequencing
* DNA sequencing

Advantages:
* 23X speed increase over current techniques
* Demonstrated and working software

Inventors: Prof. Ali Akoglu; Mr. Greg Stiemer

Status: Provisional Patent Application filed; associated software (case # UA09-063) is protected under Copyright. Seeking commercial partner
to license.

Refer to Case # UA09-064
Related to Case # UA09-063

Advantages

* 23X speed increase over current techniques * Demonstrated and working software

Innovation Details

Detailed Description

The Smith-Waterman algorithm is widely used for local sequence alignment when determining similarities between biomolecule sequences, and is primarily used in DNA and protein sequencing. Smith-Waterman is considered a dynamic algorithm that provides the most accurate results when performing local sequence alignment in difficult-to-determine regions of proteins segments that show a low similarity between distantly related biological sequences resulting from evolutionary "noise." A major issue in current Smith-Waterman implementations, however, is that computational overhead is very high, making it a resource intensive algorithm. This problem is compounded by the rapid growth of available DNA and protein databases. To resolve computational overhead problem, researchers at The University of Arizona developed a software method that utilizes NVIDIA's Compute Unified Device Architecture (CUDA) language, taking advantage of the processing power of NVIDIA's Graphical Processing Units (GPUs). This approach achieves performance gains with a reconfigured Smith-Waterman algorithm that is much faster than that of current technologies. This vastly improved speed will cut processing time and overhead for researchers that rely on the Smith-Waterman algorithm for their sequencing needs. Refer to Case # UA09-064 Related to Case # UA09-063 Contact Lance Creed lcreed@ott.arizona.edu

File Number: UA09-064

Web site: http://www.ece.arizona.edu/~akoglu/

IP Protection

License Online

This innovation currently is not available for online licensing. Please contact Lance Creed at University of Arizona for more information.

request more info