Which Pairwise Global Alignment Tools Are Available?

Question

[Frédéric Mahé]

Dear community,

I am looking for fast implementations of the Needleman–Wunsch algorithm. I used to work with needle (Emboss package), but I recently replaced it with ggsearch (FASTA package), which is nearly two-orders of magnitude faster (maybe because it uses SSE2 instructions? I am not completely sure it does). Is there any new implementations (not listed in Wikipedia) that I should know about?

Answer 1

[lh3]

If your purpose is to search against a protein database, you can hardly find anything better than ggsearch. Ggsearch is based on SSE2 and was written by Michael Farrar who developed the original striped SSE2-SW algorithm. It is the only open-source global aligner so far as I know.

Another notable implementation is swat from phrap. It does global alignment as well. Swat is probably the fastest (or very close to the fastest) SW/NW aligner without SIMD, but it may be tens of times slower than ggsearch.

A problem with needle, if I am right, is that it always fills the trace-back matrix and is thus not suitable search against a protein database. I believe ggsearch and swat compute the score first and only fill the trace-back matrix when they think the alignment score is high enough.

Answer 2

[Bill Pearson]

ggsearch36 does use sse2 instructions, but it also achieves a speed-up by not considering for alignment library sequences that are 25% shorter or 33% longer than the query.

Answer 3

[Botond Sipos]

There is also exonerate, which is quite mature and supports a variety of alignment models and heuristics.

Answer 4

[Gjain]

You can look at:

• Global Pairwise Alignment Tools
• A previous BioStar post mentioned MUMmer

Answer 5

[brentp]

Marcin Cieślik and I wrote this module for python.

This is surely not as fast as anything that uses SSE, but it uses Cython/C so it's has pretty good performance.

[Frédéric Mahé]

It looks very handy! I'll definitively give it a try.