It is currently Mon Jun 17, 2019 8:49 am



Reply to topic  [ 1 post ] 
FAQ: Sensitivity and X dropoff in Sequence Confirmation 
Author Message

Joined: Tue Feb 08, 2011 8:23 pm
Posts: 19
Post FAQ: Sensitivity and X dropoff in Sequence Confirmation
The combination of X-dropoff and Sensitivity is very important to be able to "jump" over gaps. The current version of the algorithm simply finds the best match and then extends it in each direction until it reaches the end of one of the sequences or the alignment quality degenerates until its not worth extending any more. The X-dropoff value determines when the alignment quality is so bad its time to give up. Here's a more detailed description of how the two parameters interact:

The Sensitivity parameter determines how far ahead the algorithm looks to try to get past mismatches. The default of 4 means that when it encounters a mismatch, it will test every combination of insertion/deletion on each sequence up to a maximum of 3 additional mismatches as it tries to extend the initial match. This means that if you have a gap of 4 residues, it should be able to see past that and come up with the perfect alignment. However, if you have a gap of 5 residues, the algorithm won't look far enough ahead and will likely not make the correct guess at the optimum alignment. So, as a rule of thumb, set the sensitivity to at least one more than the maximum gap you expect. Of course, as gaps are often in areas where the quality is poor and additional insertions/deletions may be present, even then the alignment may not be optimal.

The X-dropoff parameter is used to determine when an alignment is degenerating and its time to give up with the extension. It does not affect the quality of the extension, only the speed. When the algorithm is extending, it keeps track of the best score it obtained. When attempting to extend across a large gap, the "current" score will get reduced by the "Mismatch" or "Gap Penalty" value each time a mismatch or gap is introduced. If the current score falls more than X-dropoff below the best score, the extension attempt is aborted.

This means that if you have a gap of 8 residues, you need to not only make sure that sensitivity is set to at least 8, but you also need to make sure that X-dropoff is set to at least 8 x Mismatch, otherwise the algorithm will give up on the extension before it reaches the end of the gap. For the defaults, where Mismatch is -4, this means X-Dropoff would need to be at least 24. The disadvantage of large X-Dropoff values is simply that the algorithm spends a lot of time on "red herring alignments" - trying to extend matches beyond the end of the real alignment. In all cases, when the algorithm finally gives up on the extension, it always resets the alignment to the alignment that produced the best score. That means that if your 8 residue gap is near the end of an alignment (e.g. there are only 8 matching residues after the gap), the alignment may get cut back to the edge of the gap because the 8 matches (value +16 with the defaults) can not make up for the 8 gaps (-24 with the defaults). In fact you would need 12 perfect matches after the 8 gaps before the extended score would be equal to or greater than the previous best score.


Mon Feb 14, 2011 2:29 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 1 post ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.