Class: Align::NeedlemanWunsch

Inherits:
PairwiseAlgorithm show all
Defined in:
lib/align/needleman_wunsch.rb

Overview

Align two sequences via [NeedlemanWunsch.align] References:

www.avatar.se/molbioinfo2001/dynprog/dynamic.html

Constant Summary collapse

SCORING_DEFAULT =

Default scoring for

Align::BasicScoring.new(1,0,0)
SCORING_ALT1 = 
Align::BasicScoring.new(1,-1,-1)

Instance Attribute Summary collapse

Attributes inherited from PairwiseAlgorithm

#scoring, #seq1, #seq2

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from PairwiseAlgorithm

#max2, #max3, #max4

Constructor Details

#initialize(seq1, seq2, opts = {}) ⇒ NeedlemanWunsch

Returns a new instance of NeedlemanWunsch.

Parameters:

  • seq1 (#[], #size) —

    The first sequence

  • seq2 (#[], #size) —

    The second sequence

  • opts (Hash) (defaults to: {}) —

    Options

Options Hash (opts):

  • :scoring (NeedlemanWunschScoring) — default: NeedlemanWunschScoring —

    An instance of a scoring object.

  • :skip_obj (Object) — default: nil —

    An object to shove into the gaps of the aligned sequences



21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# 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

Instance Attribute Details

#cols ⇒ Object (readonly)

Returns the value of attribute cols.



9
10
11
 
# File 'lib/align/needleman_wunsch.rb', line 9

def cols
  @cols
end

#matrix ⇒ Object (readonly)

Returns the value of attribute matrix.



9
10
11
 
# File 'lib/align/needleman_wunsch.rb', line 9

def matrix
  @matrix
end

#rows ⇒ Object (readonly)

Returns the value of attribute rows.



9
10
11
 
# File 'lib/align/needleman_wunsch.rb', line 9

def rows
  @rows
end

Class Method Details

.align(seq1, seq2, opts = {}) ⇒ Object

Aligns two sequences together.

Parameters:



152
153
154
 
# File 'lib/align/needleman_wunsch.rb', line 152

def self.align(seq1, seq2, opts = {})
  self.new(seq1, seq2, opts).align
end

Instance Method Details

#align ⇒ Object

Returns the sequences in aligned arrays. Gaps are filled with :skip_obj

Returns:

  • Two arrays containing the sequences, and their elements.



128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
# 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

#fill ⇒ Object

Fills the matrix with the alignment map.



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# 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

#score ⇒ Object 



36
37
38
 
# File 'lib/align/needleman_wunsch.rb', line 36

def score
  @matrix[@rows-1][@cols-1]
end

#traceback {|i, j, step| ... } ⇒ Object

Traces backward, finding the alignment.

Yields:

  • (i, j, step)

Yield Parameters:

  • i (Integer) —

    The location in sequence one

  • j (Integer) —

    The location in sequence two

  • step (Integer) —

    The direction we took



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# 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

#traceback_array ⇒ Object

Like traceback, but returns an array of the traceback instead of yielding blocks.



118
119
120
121
122
123
124
 
# File 'lib/align/needleman_wunsch.rb', line 118

def traceback_array
  trace = []
  traceback do |i,j,flags|
    trace << [i,j,flags]
  end
  trace
end