Changeset 869 for trunk/yat/utility/Alignment.h

Timestamp:

Sep 14, 2007, 8:59:46 PM (16 years ago)

Author:

Peter

Message:

Adding Smith-Waterman local alignment and modified ssearch to use this instead. Also added some convenient max functions in stl_utility.

File:

• trunk/yat/utility/Alignment.h (modified) (2 diffs)

trunk/yat/utility/Alignment.h

@@ -27 +27 @@
 */
 
+#include <string>
 #include <utility>
 #include <vector>
@@ -61 +62 @@
 
   /**
-     SSearch does a rigorous Smith-Waterman (Needleman-Wunsch with no gap
-     cost) search for similarity between a sequnces. For long sequences this
-     may be very expensive (both in time and space) and BLAST or FASTA is
-     preferable.
+     \brief Local alignment following the Smith-Waterman
+     algorithm. 
 
-     @return number of matches
+     The original paper can be found here:
+     http://gel.ym.edu.tw/~chc/AB_papers/03.pdf
+
+     Instead of looking at each sequence in its entirety the S-W algorithm
+     compares segemnt of all possible lengths (LOCAL alignment) and chooses
+     whichever maximises the similarity measure.
+
+     \param s score matrix in which element $(i,j)$ is the score between
+     element $i$ in first sequence vs element $j$ in second sequence.
+     \param gap cost for having a gap (insertion or deletion)
+     \param open_gap cost for open up a gap in sequence, in other words, for a
+     gap of length $l$ the total cost is $open_gap + l*gap$.
    */
-  unsigned int ssearch(std::string first, std::string second);
+  double SmithWaterman(const utility::matrix& s,
+                       double gap, double open_gap);
+
+  /**
+     SSearch does a rigorous Smith-Waterman search for similarity between 
+     sequnces. For long sequences this may be very expensive (both in time and
+     space) and BLAST or FASTA is preferable.
+
+     @return score
+   */
+  double ssearch(std::string first, std::string second, double gap, 
+                 double open_gap);
 
 }}} // of namespace utility, yat, and theplu