Class: NeedlemanWunschAligner

Inherits:
Object
  • Object
show all
Defined in:
lib/needleman_wunsch_aligner.rb,
lib/needleman_wunsch_aligner/version.rb,
lib/needleman_wunsch_aligner/example_paragraph_and_sentence_aligner.rb

Overview

Finds the optimal alignment of two sequences using the Needleman-Wunsch algorithm. This basic implementation works with any Ruby object and just looks at object identity for the scoring algorithm.

See ExampleParagraphAndSentenceAligner for an example of a more sophisticated scoring algorithm.

Direct Known Subclasses

ExampleParagraphAndSentenceAligner

Defined Under Namespace

Classes: ExampleParagraphAndSentenceAligner

Constant Summary collapse

VERSION = 
"1.0.3"

Instance Method Summary collapse

Constructor Details

#initialize(left_seq, top_seq) ⇒ NeedlemanWunschAligner

Returns a new instance of NeedlemanWunschAligner.

Parameters:

  • left_seq (Array<Object>) —

    sequence drawn at left of matrix

  • top_seq (Array<Object>) —

    sequence drawn at top of matrix



16
17
18
19
 
# File 'lib/needleman_wunsch_aligner.rb', line 16

def initialize(left_seq, top_seq)
  @left_seq = left_seq
  @top_seq = top_seq
end

Instance Method Details

#compute_score(left_el, top_el) ⇒ Numeric

This is a basic implementation of the scoring algorithm. See ExampleParagraphAndSentenceAligner for a more complex scoring function.

Parameters:

  • left_el (Object)
  • top_el (Object)

Returns:

  • (Numeric) 


34
35
36
 
# File 'lib/needleman_wunsch_aligner.rb', line 34

def compute_score(left_el, top_el)
  left_el == top_el ? 1 : -3
end

#default_gap_penalty ⇒ Numeric

Returns the default penalty for a gap.

Returns:

  • (Numeric) 


40
41
42
 
# File 'lib/needleman_wunsch_aligner.rb', line 40

def default_gap_penalty
  -1
end

#gap_indicator ⇒ Object

Returns a sequence element to indicate a gap. Needs to be compatible with other sequence elements and your scoring function.

Returns:

  • (Object) 


47
48
49
 
# File 'lib/needleman_wunsch_aligner.rb', line 47

def gap_indicator
  nil
end

#get_optimal_alignment ⇒ Object

Returns two arrays that represent the optimal alignment.



22
23
24
25
26
27
 
# File 'lib/needleman_wunsch_aligner.rb', line 22

def get_optimal_alignment
  @get_optimal_alignment ||= (
    construct_score_matrix_and_traceback_matrix
    compute_optimal_alignment
  )
end

#inspect_alignment(col_width = 20) ⇒ String

Returns a string representation of the optimal alignment in two columns.

Parameters:

  • col_width (Integer, optional) (defaults to: 20) —

    max width of each col in chars

Returns:

  • (String) 


54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/needleman_wunsch_aligner.rb', line 54

def inspect_alignment(col_width = 20)
  aligned_left_seq, aligned_top_seq = get_optimal_alignment
  s = []
  aligned_left_seq.each_with_index do |left_el, idx|
    top_el = aligned_top_seq[idx]
    delimiter = if top_el == left_el
      '=' # match
    elsif gap_indicator == top_el
      '-' # delete
    elsif gap_indicator == left_el
      '+' # insert
    else
      '!' # mismatch
    end
    s << [
      left_el.inspect[0...col_width].rjust(col_width),
      top_el.inspect[0...col_width].ljust(col_width),
    ].join("  #{ delimiter }  ")
  end
  s.join("\n")
end

#inspect_matrix(which_matrix, col_width = 3) ⇒ String

Returns string representation of either the score or the traceback matrix.

Parameters:

  • which_matrix (Symbol) —

    one of :traceback or :score

  • col_width (Integer, optional) (defaults to: 3) —

    , defaults to 3

Returns:

  • (String) 


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/needleman_wunsch_aligner.rb', line 80

def inspect_matrix(which_matrix, col_width = 3)
  get_optimal_alignment  # make sure we have computed the matrices
  the_matrix = case which_matrix
  when :traceback
    @traceback_matrix
  when :score
    @score_matrix
  else
    raise "Handle this: #{ which_matrix.inspect }"
  end

  s = ''
  s << 'left_seq = ' + @left_seq.join + "\n"
  s << 'top_seq = ' + @top_seq.join + "\n"
  s <<  "\n"
  # Header row
  s << ' ' * 2 * col_width
  @top_seq.each_index { |e| s << @top_seq[e].to_s.rjust(col_width) }
  s << "\n"

  traverse_score_matrix do |row, col|
    if 0 == col and 0 == row
      # first column in first row
      s << ' '.rjust(col_width)
    elsif 0 == col
      # first col in subsequent rows
      s << @left_seq[row - 1].to_s.rjust(col_width)
    end
    # subsequent cells
    s << the_matrix[row][col].to_s.rjust(col_width)
    # finalize row
    s << "\n" if col == the_matrix[row].length - 1
  end
  s
end