Needleman Wunsch Aligner

This gem finds the optimal alignment of two sequences of any kind of Ruby Objects. You can implement sophisticated scoring functions, using any of the Objects’ attributes.

The Needleman-Wunsch algorithm is typically used in bioinformatics to align protein or nucleotide sequences, however it works really well for any kind of sequence. I have used this gem to align paragraphs and sentences of pairs of bilingual texts.

Given two sequences

seq1 = 'GCATGCU'
seq2 = 'GATTACA'

The algorithm will find the optimal alignment based on a scoring function you specify:

GCATG-CU
G-ATTACA

Installation

Add this line to your application's Gemfile:

gem 'needleman_wunsch_aligner'

And then execute:

$ bundle

Or install it yourself as:

$ gem install needleman_wunsch_aligner

Usage

Instantiate a new aligner with the two sequences and compute the optimal alignment:

require 'needleman_wunsch_aligner'

aligner = NeedlemanWunschAligner.new([1,2,3], [2,3,4])
aligner.get_optimal_alignment
# => [[1, 2, 3, nil], [nil, 2, 3, 4]]

Inspect the alignment:

puts aligner.inspect_alignment

# =>   1 - nil
       2 = 2
       3 = 3
     nil + 4

Inspect the score table:

puts aligner.inspect_matrix(:score)
# =>            2   3   4
            0  -1  -2  -3
        1  -1  -2  -3  -4
        2  -2   0  -1  -2
        3  -3  -1   1   0

Inspect the traceback table:

puts aligner.inspect_matrix(:traceback)
# =>  2  3  4
   x  ←  ←  ←
1  ↑  ↑  ↑  ↑
2  ↑  ⬉  ←  ←
3  ↑  ↑  ⬉  ←

Customization

The gem comes with a very basic scoring function. You can implement much more sophisticated ones by subclassing the NeedlemanWunschAligner class and overriding the following instance methods:

compute_score
default_gap_penalty
gap_indicator

Please see NeedlemanWunschAligner::ExampleParagraphAndSentenceAligner for an example.

You can also override these methods which are related to #inspect_alignment:

element_for_inspection_display
elements_are_equal_for_inspection

Contributing

Fork it ( https://github.com/jhund/needleman_wunsch_aligner/fork )
Create your feature branch (git checkout -b my-new-feature)
Commit your changes (git commit -am 'Add some feature')
Push to the branch (git push origin my-new-feature)
Create a new Pull Request

Resources

License

MIT licensed.