Multilevel Parallelization of the Smith-Waterman Algorithm

Marine Biological Laboratory Computer Science, 2001-02

Liaison(s): Michael Cummings
Advisor(s): Elizabeth Sweedyk
Students(s): Ben Zeckel (TL Spring), Kurt Dresner (TL Fall), Drew Levin, Andrew Magis, Eric Ong

A common task in molecular biology is the search for similarity between a given strand of DNA or protein and the sequences in a database such as GenBank. The most accurate search programs aimed at this problem are based on the Smith-Waterman algorithm. Typical open-source implementations are slow while fast commercial implementations are quite expensive. We have implemented a parallelized version intended to be freely distributed while being performance competitive with commercial packages.