Question: Using Fasta For Pairwise Global Alignment Of Dna Sequences
gravatar for Talal
10.0 years ago by
Talal0 wrote:


I invented new heuristic global pairwise sequence alignment algorithm and want to compare it with the FASTA algorithm. I downloaded fasta35 software and used it. The problem that fasta35 is a local alignment program, and I can not compare it with my algorithm.

Anyone has idea how can I use FASTA for global alignment?

Is there any software for heuristic global alignment?


fasta sequence alignment dna • 4.6k views
ADD COMMENTlink modified 10.0 years ago by Jeremy Leipzig19k • written 10.0 years ago by Talal0
gravatar for Casey Bergman
10.0 years ago by
Casey Bergman18k
Athens, GA, USA
Casey Bergman18k wrote:

If your method is for global pairwise alignment, you should be benchmarking against the full dynamic programming Needleman-Wunsch algorithm and other global pairwise hueristic alignment algorithms (see wikipedia site mentioned by Lars).

I would think you need at least to benchmark against an implementation of the Needleman-Wunsch algorithm like needle, which is available for download in the EMBOSS package. I would also recommend benchmarking against Lagan and Dialign, which we found in a previous study to have the highest performance on modest sized (10 kb) noncoding DNA sequences. Another method to try would be ACANA, which came out after this study and had higher performance on the same simulated benchmark dataset.

ADD COMMENTlink written 10.0 years ago by Casey Bergman18k
gravatar for Lars Juhl Jensen
10.0 years ago by
Copenhagen, Denmark
Lars Juhl Jensen11k wrote:

There are numerous global alignment tools that you could compare to MUMmer was the first I thought of, but do make sure to check the long list of pairwise alignment tools on Wikipedia.

ADD COMMENTlink written 10.0 years ago by Lars Juhl Jensen11k

I fear you will be disappointed. Generally, famous heuristics are famous because they give results that are close to the exact solutions. If your heuristic gives results that are so far from the exact solution that you cannot compare them, it is a pretty bad sign.

ADD REPLYlink written 10.0 years ago by Lars Juhl Jensen11k

I fail to see why you would only want to compare to heuristic methods. If you want to convince people that your heuristic is good, you need to show that you come close to the exact solution, not just that your heuristic is "less bad" than some other heuristic.

ADD REPLYlink written 10.0 years ago by Lars Juhl Jensen11k

MUMmer is not heuristic algorithm. It is based on Smith-Waterman which gives exact matches. I am looking for heuristic global alignment.

ADD REPLYlink written 10.0 years ago by Talal0

Thanks Lars for your comments. My heurstic performs much faster than the exact solution (needlman) but on the other hand the alignment score is almost far from the exact solution. Fo that I can not compare with it. I want to compare with a famous heuristic one like Fasta which is already far from the exact one but is much slower than mine.

ADD REPLYlink written 10.0 years ago by Talal0
gravatar for lh3
10.0 years ago by
United States
lh332k wrote:

For sequence alignment, "heuristic" typically denotes that the algorithm is not guaranteed to find the optimal alignment reported by dynamic programming.

By "global alignment", we usually mean aligning each residue between two sequences while retaining colinearity, what the Needleman algorithm is achieving.

Actually I do not recall any heuristic global alignment algorithms. We do not develop such algorithms simply because we do not need them. Even if by "global alignment" you mean to break colinearity, there are probably very few, if any.

[Except needle, most algorithms mentioned in the two answers are local alignment algorithms. The selling point of Dialign is its ability to do local alignment, as I remember. But if you check the benchmarks by other groups, its accuracy is far below the popular ones. This was true at least a few years ago. Whole-genome aligners such as Lagan almost certainly perform local alignment. Mummer is heuristic, but I do not think it does global alignment, either.]

ADD COMMENTlink written 10.0 years ago by lh332k
gravatar for Jeremy Leipzig
10.0 years ago by
Philadelphia, PA
Jeremy Leipzig19k wrote:

Vmatch does semi-global or glocal in the sense that the 'complete' option specifies that query sequences must match completely. Using a suffix-tree I don't consider that to be heuristic, however

The need to either penalize end gaps or extend an alignment to the 5' end of a query sequence has long been sore point with BLAST and BLAT. Especially when you are trying to do things like determine integration sites.

Short read mappers are so stringent that the issue does not really come up too often.

Looks like this question by Ryan Thompson deals with the semi-global issue: Semi-Global Alignment Tool?

ADD COMMENTlink modified 17 months ago by Ram32k • written 10.0 years ago by Jeremy Leipzig19k
Please log in to add an answer.


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