Hi, I'm working on sequence alignment algorithms. My background is Computer Science. Given two sequences, what could be the max length of a gap and how many insertions/deletion at one stretch I may consider? I think more than one insertion/deletion at one stretch is useless...? My algorithm will accept a large text file, and report locations in the file where the best regions are found.
For example:
Query: ATCGACTAACCA
File: TCAGCTTCCAGCTA
When I executed these two strings on ebi.ac.uk, I got the following result, 7 pairs match.
EMBOSS_001 A T C G A C T A A C C A ---- EMBOSS_001 - T C A G C T - T C C A G C T A
However, my algorithm reports an 8 pairs match, which one is better? Please suggest. Many Thanks in advance...
Query A T C G A C T A A C C A File: - T C A G C T T C C A G C T A
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
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.
- Badges
- Science topic
- Similar topics
- Computer Science