-
- private
-
- # Method for indexing a sequence given a search space, oligo size
- # and step size. All oligo positions are saved in a lookup hash
- # where the oligo is the key and the position is the value. Non-
- # unique oligos are removed and the index returned.
- def index_seq(space_beg, space_end, seq, kmer_size, step_size)
- index = Hash.new
- index_count = Hash.new(0)
-
- i = space_beg
-
- while i < space_end - kmer_size + 1
- oligo = seq[i ... i + kmer_size]
-
- index[oligo] = i
- index_count[oligo] += 1
- i += step_size
- end
-
- index_count.each do |oligo, count|
- index.delete(oligo) if count > 1
- end
-
- index
- end
-
- # Method for locating matches between two indexes where one is created
- # using non-overlapping unique oligos and their positions and one is
- # using overlapping unique oligos and positions. Thus iterating over the
- # non-overlapping oligos and checking last match, this can be extended.
- def find_matches(q_index, s_index, kmer_size)
- matches = []
-
- q_index.each do |oligo, q_pos|
- if s_pos = s_index[oligo]
-
- last_match = matches.last
- new_match = Match.new(q_pos, s_pos, kmer_size)
-
- if last_match and
- last_match.q_beg + last_match.length == new_match.q_beg and
- last_match.s_beg + last_match.length == new_match.s_beg
-
- last_match.length += kmer_size
- else
- matches << new_match
- end
- end
- end
-
- matches
- end
-
- # Class for Match objects.
- class Match
- attr_accessor :length
- attr_reader :q_beg, :s_beg
-
- def initialize(q_beg, s_beg, length)
- @q_beg = q_beg
- @s_beg = s_beg
- @length = length
- end
-
- def q_end
- @q_beg + @length - 1
- end
-
- def s_end
- @s_beg + @length - 1
- end
-
- def to_s
- "q_beg=#{q_beg} q_end=#{q_end} s_beg=#{s_beg} s_end=#{s_end} length=#{length}"
- end
-
- # Method to expand a match as far as possible to the left and right
- # within a given search space.
- def expand(q_seq, s_seq, q_space_beg, q_space_end, s_space_beg, s_space_end)
- expand_left(q_seq, s_seq, q_space_beg, s_space_beg)
- expand_right(q_seq, s_seq, q_space_end, s_space_end)
- end
-
- private
-
- # Method to expand a match as far as possible to the left within a given
- # search space.
- def expand_left(q_seq, s_seq, q_space_beg, s_space_beg)
- while @q_beg > q_space_beg and @s_beg > s_space_beg and q_seq[@q_beg - 1] == s_seq[@s_beg - 1]
- @q_beg -= 1
- @s_beg -= 1
- @length += 1
- end
- end
-
- # Method to expand a match as far as possible to the right within a given
- # search space.
- def expand_right(q_seq, s_seq, q_space_end, s_space_end)
- while q_end + 1 <= q_space_end and s_end + 1 <= s_space_end and q_seq[q_end + 1] == s_seq[s_end + 1]
- @length += 1
- end
- end
- end