Which Pairwise Global Alignment Tools Are Available?
5
4
Entering edit mode
12.2 years ago

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?

dna sequence alignment software • 3.8k views
ADD COMMENT
4
Entering edit mode
12.2 years ago
lh3 33k

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.

ADD COMMENT
2
Entering edit mode
12.1 years ago
Bill Pearson ★ 1.0k

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.

ADD COMMENT
2
Entering edit mode
12.1 years ago
Botond Sipos ★ 1.7k

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

ADD COMMENT
1
Entering edit mode
12.2 years ago
Gjain 5.8k

You can look at:

ADD COMMENT
1
Entering edit mode
12.2 years ago
brentp 24k

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.

ADD COMMENT
0
Entering edit mode

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

ADD REPLY

Login before adding your answer.

Traffic: 2388 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6