With classical biological sequence alignment algorithms such as blast, psiblast and fastA, the number of gaps inserted is controlled by two parameters, by the gap insertion penalty and gap extension penalty, which contribute to the alignment score. A high gap insertion penalty and low gap extension penalty gives preference to few large gaps rather then many short gaps.

In an era of splice variants, sequence alignments are much more difficult. You can have very large gaps (whole introns) as well as SNPs. You might do some research on what algorithms that Compugen (an Israeli company) used when they processed DNA sequences to discovery splice variants in the late 1990s and early 2000s.

Dear Vinod,

Many papers currently point a max alignment size of 1.5x the length of the greatest sequence.

Regards.

You somehow forgot to include like three gaps in your alignment. So it should read:

A T C G A - C T A A C C A

- T C - A G C T T - C C A G C T A

Why would you develop newly something that has been already described so many times? Need a local alignment? Look up for Smith-Watermann algorithm

https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm

Want global alignment? Look up Needleman-Wunsch algorithm

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

The details you're asking for depend on your model (simple similarity, evolution, etc.) and are reflected in the substitution matrix you use and the gap-scoring.

I don't recall there would be any maximum length or number of gaps in any algorithm. Simply if it's better (assuming the gap-scoring you use) to get new gap or extend the existing one, it will. Of course, if you put the opening penalty or elongation penalty large, it will be discriminated against the gaps.

@ Tomas Thanks for your reply. Well, I want to develop algorithm for large online text. The algorithms you have mention may not be appropriate in that situation, the process will be incredibly slow. For a given input string, my aim is to find best alignment locations in the online text or database. The algorithm would ask user to enter the maximum allowed gap/insertion/deletion between the two characters of the string and then report the best locations accordingly.

You mean text or biological sequences?

If you're concerned with the speed of alignment, then there is BLAST.

Dear Prasad,

It all depends on two things:

1. What is the type of text you want to align/compare

2. What is the reason to compute the alignment/comparison.

Sequence alignment (or string matching) has a very long history in computer science (and also computational biology), with many algorithms proposed for solving different -- yet related tasks (see e.g. https://en.wikipedia.org/wiki/Approximate_string_matching).

There is a vast amount of literature published but, unless we know the exact problem you are trying to solve, it is practically impossible to point you to the most useful literature.

Best,

Vasilis

@ Vasilis J Promponas Thanks for your suggestions...

With classical biological sequence alignment algorithms such as blast, psiblast and fastA, the number of gaps inserted is controlled by two parameters, by the gap insertion penalty and gap extension penalty, which contribute to the alignment score. A high gap insertion penalty and low gap extension penalty gives preference to few large gaps rather then many short gaps.

@ Annemarie Honegger Thanks for taking time to answer this question.