28 lines
1.2 KiB
Plaintext
28 lines
1.2 KiB
Plaintext
// NeedlemanWunschScore: the best score of a global alignment of S and T
|
|
// (Needleman and Wunsch, 1970) with a linear gap model, by dynamic
|
|
// programming. D[I, J] is the best score of aligning the first I letters of
|
|
// S with the first J letters of T; each cell takes the best of three moves:
|
|
// align S[I - 1] with T[J - 1], or put a gap in one sequence or the other.
|
|
USE align.MatchScore
|
|
USE align.LinearGapPenalty
|
|
FUNCTION NeedlemanWunschScore(S : STRING, T : STRING, Match : INTEGER, Mismatch : INTEGER, Gap : INTEGER) RETURNS INTEGER
|
|
DECLARE N : INTEGER <- LENGTH(S)
|
|
DECLARE M : INTEGER <- LENGTH(T)
|
|
DECLARE D : ARRAY[N + 1, M + 1] OF INTEGER
|
|
FOR I <- 0 TO N + 1
|
|
D[I, 0] <- LinearGapPenalty(I, Gap)
|
|
NEXT I
|
|
FOR J <- 1 TO M + 1
|
|
D[0, J] <- LinearGapPenalty(J, Gap)
|
|
NEXT J
|
|
FOR I <- 1 TO N + 1
|
|
FOR J <- 1 TO M + 1
|
|
DECLARE Diagonal : INTEGER <- D[I - 1, J - 1] + MatchScore(S[I - 1], T[J - 1], Match, Mismatch)
|
|
DECLARE Down : INTEGER <- D[I - 1, J] + Gap
|
|
DECLARE Across : INTEGER <- D[I, J - 1] + Gap
|
|
D[I, J] <- MAX(Diagonal, Down, Across)
|
|
NEXT J
|
|
NEXT I
|
|
RETURN D[N, M]
|
|
ENDFUNCTION
|