Needleman Wunsch algorithm

The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences.

Usage

import bionim

let s1: string = "GCATGCU"
let s2: string = "GATTACA"

let match: int8 = 1
let mismatch: int8 = -1
let indel_penal: int8 = -1
#This return the matrix used in the algorithm
let grid = needlemanWunsch(s1, s2, indel_penal, match, mismatch)
let alignment: (string, string) = calculateAlignment(grid, s1, s2, indel_pen, match, mismatch)

echo alignment[0]
echo alignment[1]

This should output:

GCA-TGCU
G-ATTACA

If you want to print the matrix you can use the helper function printGrid like this

printGrid(grid, s1, s2)

This should output

    -   G   C   A   T   G   C   U
-   0  -1  -2  -3  -4  -5  -6  -7
G  -1   1   0  -1  -2  -3  -4  -5
A  -2   0   0   1   0  -1  -2  -3
T  -3  -1  -1   0   2   1   0  -1
T  -4  -2  -2  -1   1   1   0  -1
A  -5  -3  -3  -1   0   0   0  -1
C  -6  -4  -2  -2  -1  -1   1   0
A  -7  -5  -3  -1  -2  -2   0   0

Options structure

If you need your configurations in other places you can use the needlemanWunschConfig type

let options = needlemanWunschConfig(sequence1: "GCATGCU", sequence2: "GATTACA", indel_penal: -1, match: 1, mismatch: -1)

There are overloads which accept this type instead of all five required arguments separately.

let grid = needlemanWunsch(options)
let alignment = calculateAlignment(grid, options)

References

https://upload.wikimedia.org/wikipedia/en/c/c4/ParallelNeedlemanAlgorithm.pdf