class Align::NeedlemanWunsch
Align
two sequences via [NeedlemanWunsch.align] References:
- www.avatar.se/molbioinfo2001/dynprog/dynamic.html
Constants
- SCORING_ALT1
- SCORING_DEFAULT
Default scoring for
Attributes
Public Class Methods
Aligns two sequences together. @param see (initialize)
# File lib/align/needleman_wunsch.rb, line 152 def self.align(seq1, seq2, opts = {}) self.new(seq1, seq2, opts).align end
@param [#[], size] seq1 The first sequence @param [#[], size] seq2 The second sequence @param [Hash] opts Options @option opts [NeedlemanWunschScoring] :scoring (NeedlemanWunschScoring) An instance of a scoring object. @option opts [Object] :skip_obj (nil) An object to shove into the gaps of
the aligned sequences
# File lib/align/needleman_wunsch.rb, line 21 def initialize(seq1, seq2, opts = {}) super(seq1, seq2, opts[:scoring] || SCORING_DEFAULT) @rows = @seq1.size + 1 @cols = @seq2.size + 1 @skip_obj = opts[:skip_obj] || nil @matrix = Array.new(@rows) do Array.new(@cols) end fill() end
Public Instance Methods
Returns the sequences in aligned arrays. Gaps are filled with :skip_obj @return Two arrays containing the sequences, and their elements.
# File lib/align/needleman_wunsch.rb, line 128 def align alignment_1 = [] alignment_2 = [] traceback do |i, j, flags| seq1_val = seq2_val = @skip_obj case flags when :align seq1_val = @seq1[i] seq2_val = @seq2[j] when :insert seq2_val = @seq2[j] when :delete seq1_val = @seq1[i] end alignment_1.unshift seq1_val alignment_2.unshift seq2_val end [alignment_1, alignment_2] end
Fills the matrix with the alignment map.
# File lib/align/needleman_wunsch.rb, line 41 def fill @matrix[0][0] = 0 # Set up the first column on each row. 1.upto(@rows-1) {|i| @matrix[i][0] = @matrix[i-1][0] + @scoring.score_delete(@seq1[i])} # Set up the first row 1.upto(@cols-1) {|j| @matrix[0][j] = @matrix[0][j-1] + @scoring.score_insert(@seq2[j])} 1.upto(@rows-1) do |i| prv_row = @matrix[i-1] cur_row = @matrix[i] 1.upto(@cols-1) do |j| seq1_obj = @seq1[i-1] seq2_obj = @seq2[j-1] # Calculate the score. score_align = prv_row[j-1] + @scoring.score_align(seq1_obj, seq2_obj) score_delete = prv_row[j] + @scoring.score_delete(seq1_obj) score_insert = cur_row[j-1] + @scoring.score_insert(seq2_obj) max = max3(score_align, score_delete, score_insert) @matrix[i][j] = max end end end
# File lib/align/needleman_wunsch.rb, line 36 def score @matrix[@rows-1][@cols-1] end
Traces backward, finding the alignment. @yield [i,j,step] @yieldparam i [Integer] The location in sequence one @yieldparam j [Integer] The location in sequence two @yieldparam step [Integer] The direction we took
# File lib/align/needleman_wunsch.rb, line 73 def traceback i = @rows - 1 j = @cols - 1 while (i > 0 && j > 0) score = @matrix[i][j] seq1_obj = @seq1[i-1] seq2_obj = @seq2[j-1] score_align = @matrix[i-1][j-1] + @scoring.score_align(seq1_obj, seq2_obj) score_delete = @matrix[i-1][j] + @scoring.score_delete(seq1_obj) score_insert = @matrix[i][j-1] + @scoring.score_insert(seq2_obj) flags = 0 need_select = false if score == score_align flags = :align i-=1 j-=1 elsif score == score_delete flags = :delete i-=1 else flags = :insert j-=1 end yield(i,j,flags) end # while while i > 0 i-=1 yield(i,j,:delete) end while j > 0 j-=1 yield(i,j,:insert) end end
Like traceback, but returns an array of the traceback instead of yielding blocks.
# File lib/align/needleman_wunsch.rb, line 118 def traceback_array trace = [] traceback do |i,j,flags| trace << [i,j,flags] end trace end