Team:Freiburg Software/User/Robots/Alignment

From 2010.igem.org

(Difference between revisions)
Line 60: Line 60:
<h2 id="Internals">Brief Overview of Algorithm</h2>
<h2 id="Internals">Brief Overview of Algorithm</h2>
<p class="main">
<p class="main">
 +
Alingnobot uses implementations of the Needleman/Wunsch algorithm to find global alignments and the Smith/Waterman algorithm to find local alignments. You can find the definitions on Wikipedia: <a href="http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm" target="blank">Needleman/Wunsch</a> and <a href="http://en.wikipedia.org/wiki/Smith-Waterman_algorithm" target="blank">Smith/Waterman</a> <br />
 +
Once the User clicks send the robot first loads the sequences from the workspace and checks that there are two of them. Then it evaluates the input form and the user specified cost/similarity functions if selected. If there are non-numeric characters it switches back to the default functions.<br />
 +
After these preparations are done the actual alignment calculation starts. The distance/similarity matrices get initialized and then filled following the algorithms.<br />
 +
Now the optimal score is found the robot will calculate the actual alignment using back tracing. In local alignment the robot will display all alignments with the optimal score.<br />
 +
Finally the robot uses the SynBioWave SequenceView function to display the output.
 +
</p>
</p>
</div>
</div>
</html>
</html>

Revision as of 23:28, 26 October 2010

Alignobot

This page describes the use of the Alignment Robot. If you would like to know how it works internally please click here.

With Alignobot you can compare sequences by creating global and local alignments. Alignobot can be found at alignobot@appspot.com. Before you start an alignment be sure that you have 2 sequences selected in the workspace.

Global Alignments

Alignobot finds global alignments using the Needleman/Wunsch Algorithm.

In the main menu you can either select the default distance function or specify your own. At this point the robot only supports one value for each substitution. Transition matrices will be available in a later version. Now click "Send" and Alignobot will calculate your alignment and display it:

Note: The display may slightly differ from this picture due to ongoing development.

Local Alignment

The Alignment Robot can also find local alignments using the Smith/Waterman algorithm. As with the global alignment you can either use the default similarity function or specify your own. Again support for transition matrices is still to come. Once you have selected and sent your request, the robot will find the best local alignment of the selected two sequences. There might be more than one of them with the same score. The robot will then display all of them.

Brief Overview of Algorithm

Alingnobot uses implementations of the Needleman/Wunsch algorithm to find global alignments and the Smith/Waterman algorithm to find local alignments. You can find the definitions on Wikipedia: Needleman/Wunsch and Smith/Waterman
Once the User clicks send the robot first loads the sequences from the workspace and checks that there are two of them. Then it evaluates the input form and the user specified cost/similarity functions if selected. If there are non-numeric characters it switches back to the default functions.
After these preparations are done the actual alignment calculation starts. The distance/similarity matrices get initialized and then filled following the algorithms.
Now the optimal score is found the robot will calculate the actual alignment using back tracing. In local alignment the robot will display all alignments with the optimal score.
Finally the robot uses the SynBioWave SequenceView function to display the output.