# NeedlemanWunschAligner

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](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_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

Meaning of the symbols:

    = Match
    ! Mismatch
    + Insert
    - Deletion

Insert and Deletion are usually grouped together as `IndDel`.

## 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:

    aligner.print_alignment

    # =>   1 | nil
           2 | 2
           3 | 3
         nil | 4

Inspect the score table:

    aligner.print_as_table(: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:

    aligner.print_as_table(: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.

## Contributing

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