Thursday, 2017-11-23, 0:55 AM
Welcome Guest | RSS

Login form

Total online: 1
Guests: 1
Users: 0

Is Online User
Site Search
Main » 2011 » August » 13 » Smith-Waterman Algorithm
2:01 PM
Smith-Waterman Algorithm

Smith-Waterman Algorithm

1. Description:
   The Smith–Waterman algorithm is a well-known algorithm for performing local sequence alignment; that is, for determining similar regions between two nucleotide or protein sequences. Instead of looking at the total sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure.

2. Explanation:
  1. Sensitive to detect similarity in highly diverged sequences.
  2. Algorithm: similar to global alignment with modified boundary conditions and recurrence rules.
    • The top row and left column are now filled with 0.
    • If the (sub-)alignment score becomes negative, restart the search:
    • Traceback: from the maximum of F (i, j) in the whole matrix to the first 0.
  3. Example: the optimal local alignment between HEAGAWGHEE and PAWHEAE is AWGHE::AW-HE.
  4. Issue: In gapped alignments, the expected score for a random match may be positive.
  • Consider The Simple Example
  1. N x N integer matrix
  2. N is sequence length (both s and t)
  3. Compute M[i ][j ] based on Score Matrix and optimum score compute so far (DP)
Figure: Computation Matrix alginment, M
  • Understanding Matrix
t : − − − − − − − −
s : c c c t a g g t

Figure: Aligning s to gaps

t : c g g g t a t ...
s : − − − − − − − ...

Figure: Aligning t to gaps
  • How to compute cell score?
    1. How to find M[i][j]? 
      Three ways to finish the alignment of s0..i and t0..j

  • Scoring Process
Element Computation M[i ][j ]:

  • Backtracking Process
If we want to find BEST local alignment...

Find Score and then traceback

Category: Algorithms | Views: 1029 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Tag Board
Your Ads
Site friends

Copyright MyCorp © 2017
Free website builderuCoz