+1) x (n+1) matrix. Under the assumption that both input sequences a and b stem from the
same origin, a global alignment tries to identify matching parts and the changes needed to
transfer one sequence into the other. The changes are scored and an optimal set of changes
is identified, which defines an alignment. The dynamic programming approach tabularizes
optimal subsolutions in matrix E, where an entry E (i,j) represents the best score for
aligning the prefixes a 1..i with b 1..j (Fig. 9.2).
Scoring Matrix using Needleman–Wunsch algorithm [6] and the corresponding
traceback Matrix lead to the identification of the best alignment. One possible alignment
result of our example and the related traceback are illustrated in Fig. 9.3.
Fig. 9.2 Needleman–Wunsch. Optimization of distance (left) and optimization of similarity (right)
Fig. 9.3 Needleman–Wunsch Algorithm and the resulting Scoring Matrix (E). Matches are defined
as 0, Mismatches and Gaps as 1/À1. The edist is marked in red [4]. A possible traceback is depicted
by blue arrows and the corresponding alignment at the bottom right. Diagonal jumps within the
scoring Matrix can be interpreted as Matches or Mismatches, Top or Down jumps as Deletions, and
Left or Right jumps as Insertions
114
M. Kappelmann-Fenzl
same origin, a global alignment tries to identify matching parts and the changes needed to
transfer one sequence into the other. The changes are scored and an optimal set of changes
is identified, which defines an alignment. The dynamic programming approach tabularizes
optimal subsolutions in matrix E, where an entry E (i,j) represents the best score for
aligning the prefixes a 1..i with b 1..j (Fig. 9.2).
Scoring Matrix using Needleman–Wunsch algorithm [6] and the corresponding
traceback Matrix lead to the identification of the best alignment. One possible alignment
result of our example and the related traceback are illustrated in Fig. 9.3.
Fig. 9.2 Needleman–Wunsch. Optimization of distance (left) and optimization of similarity (right)
Fig. 9.3 Needleman–Wunsch Algorithm and the resulting Scoring Matrix (E). Matches are defined
as 0, Mismatches and Gaps as 1/À1. The edist is marked in red [4]. A possible traceback is depicted
by blue arrows and the corresponding alignment at the bottom right. Diagonal jumps within the
scoring Matrix can be interpreted as Matches or Mismatches, Top or Down jumps as Deletions, and
Left or Right jumps as Insertions
114
M. Kappelmann-Fenzl