Using Fasta For Pairwise Global Alignment Of Dna Sequences

Question

[Talal]

Hi,

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?

Thanks,

Answer 1

[Casey Bergman]

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.

Answer 2

[Lars Juhl Jensen]

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.

[Lars Juhl Jensen]

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.

[Lars Juhl Jensen]

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.

[Talal]

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

[Talal]

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.

Answer 3

[lh3]

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.]

Answer 4

[Jeremy Leipzig]

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?