Dylan Freedman edited SmithWaterman.tex  about 9 years ago

Commit id: 66712ecdc0d67e6eedc68fd5cca85f879767a843

deletions | additions      

       

The Smith-Waterman algorithm is used to find optimal local alignments between two sequences based on a cost matrix for symbols of the alphabet being used and defined gap costs.  A matrix $H$ is constructed in the following manner:  \[\cases{1 & 2 & 3} \]  % \[  H(i,0) = 0, 0 \leq i \leq m \]%  \[ H(0,j) = 0, 0 \leq j \leq n \] % \[ H(i,j) = \hbox{Max} \hbox{max}  \begin{cases} 0 & H(i-1,j-1)+s(a_i,b_j) & max_{k \hbox{max}_{k  \geq 1}\left{ H(i-k,j)+W_k \right} & max_{l \hbox{max}_{l  \geq 1}\left{ H(i, j-l)+W_l) \right} \end{cases}$ \]