I need to implement the Needleman-Wunsch Algorithm with the following pseudo code, I get to input in to the code two sequences, and the output has to be the best, global alignment of two input sequences.

Pseudocode:

// Initialization

input the two sequences: s1 and s2

N = length of s1

M = length of s2

matrix = array of size [N+1, M+1]

gap = gap score(input)

mismatch = mismatch score(input)

match = match score(input)

// build alignment matrix

set matrix[0,0] to 0

for each i from 1 to N, inclusive

matrix [i, 0] = matrix[i-1, 0] + gap

for each j from 1 to M, inclusive

matrix [0, j] = matrix[0, j-1] + gap

for each i from 1 to N, inclusive

for each j from 1 to M, inclusive

if (s1[i-1] equals s2[j-1])

score1 = matrix[i-1, j-1] + match

else

score1 = matrix[i-1, j-1] + mismatch

score2 = matrix[i,j-1] + gap

score3 = matrix[i-1, j] + gap

matrix[i][j] = max(score1, score2, score3

//create directional strings

string = buildDirectionalString(matrix, N, M)

// build alignments using directional strings

seq1pos = N-1

seq2pos = M-1

drips = 0

while (dirpos < length of directional string)

if (dstring[dirpos] equals "D")

align s1[seq1pos] and s2[seq2pos]

subtract 1 from seq1pos and seq2pos

else if (dstring[dirpos] equals "V")

align s1[seq1pos] and a gap

subtract 1 from seq1pos

else // must be an H

align s2[seq2pos] and a gap

subtract 1 from seq2pos

increment dirpos

// Function to create directional string

function builddirectionalstring(matrix, N, M)

dstring = ""

currentrow = N

currentcol = M

while (currentrow!= 0 or currentcol!= 0)

if (currentrow is 0)

add 'H' to dstring

subtract 1 from currentcol

else if (currentcol is 0)

add 'V' to dstring

subtract 1 from currentrow

else if (matrix[currentrow][currentcol-1] + gap equals matrix[currentrow][currentcol])

add 'H' to dstring

subtract 1 from currentcol

else if (matrix[currentrow-1][currentcol] + gap equals matrix[currentrow][currentcol])

add 'V' to dstring

subtract 1 from currentrow

else

add 'D' to dstring

subtract 1 from currentcol

subtract 1 from currentrow

return dstring