fixed minor issue in align.rb tests

[biopieces.git] / code_ruby / lib / maasha / backtrack.rb

diff --git a/code_ruby/lib/maasha/backtrack.rb b/code_ruby/lib/maasha/backtrack.rb
index 02eb047121e6c61680d89e8cde33f65b9a1811ce..896fe091100d506cecd5b2f7c0cab1f08ba93b2e 100644 (file)
--- a/code_ruby/lib/maasha/backtrack.rb
+++ b/code_ruby/lib/maasha/backtrack.rb
@@ -32,9 +32,10 @@ class BackTrackError < StandardError; end
 # pattern match engine is based on a backtrack algorithm.
 # Insertions are nucleotides found in the pattern but not in the sequence.
 # Deletions are nucleotides found in the sequence but not in the pattern.
-# Algorithm based on code kindly provided by j_random_hacker @ Stackoverflow.
+# Algorithm based on code kindly provided by j_random_hacker @ Stackoverflow:
+# http://stackoverflow.com/questions/7557017/approximate-string-matching-using-backtracking/
 module BackTrack
-  OK_PATTERN = Regexp.new('^[flsycwphqrimtnkvadegu]+$')
+  OK_PATTERN = Regexp.new('^[bflsycwphqrimtnkvadegu]+$')
   MAX_MIS    = 5 # Maximum number of mismatches allowed
   MAX_INS    = 5 # Maximum number of insertions allowed
   MAX_DEL    = 5 # Maximum number of deletions allowed
@@ -55,8 +56,8 @@ module BackTrack
   # pattern. Matches found in block context return the Match object. Otherwise
   # matches are returned in an Array of Match objects.
   def patscan(pattern, offset = 0, max_mismatches = 0, max_insertions = 0, max_deletions = 0)
-    raise BackTrackError, "Bad pattern: #{pattern}" unless pattern.downcase =~ OK_PATTERN
-    raise BackTrackError, "offset: #{offset} out of range (0 ... #{self.length - 1})" unless (0 ... self.length).include? offset
+    raise BackTrackError, "Bad pattern: #{pattern}"                                          unless pattern.downcase =~ OK_PATTERN
+    raise BackTrackError, "offset: #{offset} out of range (0 ... #{self.length - 1})"        unless (0 ... self.length).include? offset
     raise BackTrackError, "max_mismatches: #{max_mismatches} out of range (0 .. #{MAX_MIS})" unless (0 .. MAX_MIS).include? max_mismatches
     raise BackTrackError, "max_insertions: #{max_insertions} out of range (0 .. #{MAX_INS})" unless (0 .. MAX_INS).include? max_insertions
     raise BackTrackError, "max_deletions: #{max_deletions} out of range (0 .. #{MAX_DEL})"   unless (0 .. MAX_DEL).include? max_deletions
@@ -83,10 +84,14 @@ module BackTrack
   inline do |builder|
     builder.add_static "id_seq", 'rb_intern("@seq")', "ID"
 
+    # Macro for matching nucleotides including ambiguity codes.
     builder.prefix %{
       #define MATCH(A,B) ((bitmap[(unsigned short) A] & bitmap[(unsigned short) B]) != 0)
     }
 
+    # Bitmap for matching nucleotides including ambiguity codes.
+    # For each value bits are set from the left: bit pos 1 for A,
+    # bit pos 2 for T, bit pos 3 for C, and bit pos 4 for G.
     builder.prefix %{
       unsigned short bitmap[256] = {
           0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
@@ -108,7 +113,9 @@ module BackTrack
       };
     }
 
-    # ss is the start of the string, used only for reporting the match endpoints.
+    # Backtrack algorithm for matching a pattern (p) starting in a sequence (s) allowing for mm
+    # mismatches, ins insertions and del deletions. ss is the start of the sequence, used only for
+    # reporting the match endpoints.
     builder.prefix %{
       unsigned int backtrack(char* ss, char* s, char* p, int mm, int ins, int del)
       {
@@ -129,8 +136,8 @@ module BackTrack
       }
     }
  
-    # Find all occurrences of p starting at pos in s, with at most
-    # mm mismatches, ins insertions and del deletions.
+    # Find pattern (p) in a sequence (@seq) starting at pos, with at most mm mismatches, ins
+    # insertions and del deletions.
     builder.c %{
       static VALUE track(char* p, unsigned int pos, int mm, int ins, int del)
       {
@@ -146,9 +153,7 @@ module BackTrack
 
               while (*s)
               {
-                  e = backtrack(ss, s, p, mm, ins, del);
-
-                  if (e)
+                  if (e = backtrack(ss, s, p, mm, ins, del))
                   {
                       tuple = rb_ary_new();
                       rb_ary_push(tuple, INT2FIX((int) (s - ss)));
@@ -165,6 +170,7 @@ module BackTrack
     }
   end
 
+  # Class containing match information.
   class Match
     attr_reader :pos, :length, :match