Acceleration of the Smith-Waterman Algorithm


Сomputing Acceleration

Description

2017 COMPUTER SCIENCE, SOFTWARE RE-ENGINEERING, BIOINFORMATICS

Eliminating the shortcomings of the Smith-Waterman algorithm through applying computing acceleration technologies, thus making the algorithm produce results for the shortest period of time possible.

Client

One of the leading Biotechnology Company in providing searchable access to all available peptide and nucleotide sequences from multiple databases.

Challenge

The client company uses a dynamic programming Smith-Waterman algorithm, which is known for producing complete local alignment matches between the query sequence and the existing database sequences. The comprehensiveness of the search results is much appreciated, especially by those conducting prior art searches.

But the searches performed by the algorithm, particularly those containing a relatively long query sequence, may be frustratingly slow and took hours to get finished. Using the Smith-Waterman algorithm meant that you sacrifice your time for the accuracy of the results.

Solution

The advancement of cloud and GPU computing, in combination with further improvements to the specialized genetic alignment search technology developed by Azati, allowed our engineering team to reduce the time needed to run the Smith-Waterman queries by 30-50 times. Therefore, the implemented changes made the inordinate delays associated with running excessively long Smith-Waterman queries a thing of a past for our client.

Technologies:

  • C/C++
  • NVIDIA® CUDA® Toolkit

Some detailed information not disclosed due to NDA restrictions