Global sequence alignment

A global sequence alignment optimizes the correspondence across both complete input sequences, including their ends.

Table of contents
- Needleman-Wunsch algorithm Global sequence alignment

Needleman-Wunsch algorithm

The Needleman-Wunsch algorithm uses dynamic programming to find an optimal global sequence alignment. For a linear gap penalty

e > 0

, set

F_{0 j} = - j e

F_{i 0} = - i e

and

F_{ij} = max {F_{i - 1, j - 1} + s (x_{i}, y_{j}), F_{i - 1, j} - e, F_{i, j - 1} - e} .

(1)

The final entry scores the best alignment of both complete sequences. The recurrence follows because its last step must align two symbols or a symbol and a gap. Unlike local alignment, there is no zero restart, so unmatched ends contribute to the score. ^[ref]

 Ancestors (5)

 Incoming links (4)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version