Question: Which Pairwise Global Alignment Tools Are Available?
4
gravatar for Frédéric Mahé
9.0 years ago by
France, Montpellier, CIRAD
Frédéric Mahé3.1k wrote:

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?

software sequence alignment dna • 2.7k views
ADD COMMENTlink modified 2.9 years ago by Biostar ♦♦ 20 • written 9.0 years ago by Frédéric Mahé3.1k
4
gravatar for lh3
9.0 years ago by
lh332k
United States
lh332k wrote:

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 COMMENTlink written 9.0 years ago by lh332k
2
gravatar for Bill Pearson
8.9 years ago by
Bill Pearson1.0k
Bill Pearson1.0k wrote:

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 COMMENTlink written 8.9 years ago by Bill Pearson1.0k
2
gravatar for Botond Sipos
8.9 years ago by
Botond Sipos1.7k
United Kingdom
Botond Sipos1.7k wrote:

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

ADD COMMENTlink written 8.9 years ago by Botond Sipos1.7k
1
gravatar for Gjain
9.0 years ago by
Gjain5.5k
Bengaluru, India
Gjain5.5k wrote:

You can look at:

ADD COMMENTlink modified 16 months ago by _r_am32k • written 9.0 years ago by Gjain5.5k
1
gravatar for brentp
9.0 years ago by
brentp23k
Salt Lake City, UT
brentp23k wrote:

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 COMMENTlink written 9.0 years ago by brentp23k

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

ADD REPLYlink written 9.0 years ago by Frédéric Mahé3.1k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 2495 users visited in the last hour
_