A simple version of the Needleman-Wunsch algorithm in Python.

needleman-wunsch.py

#!/usr/bin/env python
"""
The Needleman-Wunsch Algorithm
==============================

This is a dynamic programming algorithm for finding the optimal alignment of
two strings.

Example
-------

    >>> x = "GATTACA"
    >>> y = "GCATGCU"
    >>> print(nw(x, y))
    G-ATTACA
    GCA-TGCU


LICENSE

This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

For more information, please refer to <http://unlicense.org/>
"""

import numpy as np

def nw(x, y, match = 1, mismatch = 1, gap = 1):
    nx = len(x)
    ny = len(y)
    # Optimal score at each possible pair of characters.
    F = np.zeros((nx + 1, ny + 1))
    F[:,0] = np.linspace(0, -nx * gap, nx + 1)
    F[0,:] = np.linspace(0, -ny * gap, ny + 1)
    # Pointers to trace through an optimal aligment.
    P = np.zeros((nx + 1, ny + 1))
    P[:,0] = 3
    P[0,:] = 4
    # Temporary scores.
    t = np.zeros(3)
    for i in range(nx):
        for j in range(ny):
            if x[i] == y[j]:
                t[0] = F[i,j] + match
            else:
                t[0] = F[i,j] - mismatch
            t[1] = F[i,j+1] - gap
            t[2] = F[i+1,j] - gap
            tmax = np.max(t)
            F[i+1,j+1] = tmax
            if t[0] == tmax:
                P[i+1,j+1] += 2
            if t[1] == tmax:
                P[i+1,j+1] += 3
            if t[2] == tmax:
                P[i+1,j+1] += 4
    # Trace through an optimal alignment.
    i = nx
    j = ny
    rx = []
    ry = []
    while i > 0 or j > 0:
        if P[i,j] in [2, 5, 6, 9]:
            rx.append(x[i-1])
            ry.append(y[j-1])
            i -= 1
            j -= 1
        elif P[i,j] in [3, 5, 7, 9]:
            rx.append(x[i-1])
            ry.append('-')
            i -= 1
        elif P[i,j] in [4, 6, 7, 9]:
            rx.append('-')
            ry.append(y[j-1])
            j -= 1
    # Reverse the strings.
    rx = ''.join(rx)[::-1]
    ry = ''.join(ry)[::-1]
    return '\n'.join([rx, ry])

x = "GATTACA"
y = "GCATGCU"
print(nw(x, y))
# G-ATTACA
# GCA-TGCU

np.random.seed(42)
x = np.random.choice(['A', 'T', 'G', 'C'], 50)
y = np.random.choice(['A', 'T', 'G', 'C'], 50)

print(nw(x, y, gap = 0))
# ----G-C--AGGCAAGTGGGGCACCCGTATCCT-T-T-C-C-AACTTACAAGGGT-C-CC-----CGT-T
# GTGCGCCAGAGG-AAGT----CA--C-T-T--TATATCCGCG--C--AC---GGTACTCCTTTTTC-TA-

print(nw(x, y, gap = 1))
# GCAG-GCAAGTGG--GGCAC-CCGTATCCTTTC-CAAC-TTACAAGGGTCC-CCGT-T-
# G-TGCGCCAGAGGAAGTCACTTTATATCC--GCGC-ACGGTAC-----TCCTTTTTCTA

print(nw(x, y, gap = 2))
# GCAGGCAAGTGG--GGCAC-CCGTATCCTTTCCAACTTACAAGGGTCCCCGTT
# GTGCGCCAGAGGAAGTCACTTTATATCC-GCGCACGGTAC-TCCTTTTTC-TA

Hi, I'm interested in adapting this to have a variable gap penalty. This would bias the algorithm to prefer one large continuous gap (more likely to occur in nature) than a number of small gaps that add up to the same length. This means having two gap penalties, one for the start of a new gap (higher) and one for the continuation of an existing gap (lower). Can you possibly point me in the right direction for how to add this? I'm trying to trace through the code now but I'm having trouble. Thank you.

@rbracco I wrote a few notes below, and I hope they are helpful. Good luck!

---

To implement a variable gap penalty, we need to know if the previous step in the alignment introduced a gap or not. Then, we can decide if the appropriate gap penalty is the gap start or the gap continuation.

First, please consider studying a visualization of the score matrix and pointer arrows. Personally, I rely on such visualizations to develop understanding. I like to put the code and the visualization side-by-side so I can cross-reference back and forth as I think about the algorithm.

Next, let's consider the P matrix that keeps track of which options (match/mismatch, gap in x, gap in y) are compatible with the best scores. I hope the notes below can shed some light on what is going on in the code.

We are keeping track of 3 possible temporary scores in t (match/mismatch, gap in x, gap in y):

t = np.zeros(3)

In this implementation, we use t[0] to indicate the match/mismatch score, t[1] for gap in x, and t[2] for gap in y.

The integers 2, 3, 4 are placeholders in P to keep track of which temporary scores are equal to the maximum score:

if t[0] == tmax:
    P[i+1,j+1] += 2
if t[1] == tmax:
    P[i+1,j+1] += 3
if t[2] == tmax:
    P[i+1,j+1] += 4

We add either 3 or 4 to the "pointer" matrix P when one of the gapped scores (t[1] or t[2]) equals the maximum.

Once we understand the purpose of the integers 2, 3, 4, we can consider these lines:

P[i,j] in [3, 5, 7, 9]
P[i,j] in [4, 6, 7, 9]

Rewrite the lines to clarify the intent:

P[i,j] in [3, 2+3, 3+4, 2+3+4]
P[i,j] in [4, 2+4, 3+4, 2+3+4]

If either statement returns True, then we know that P[i,j] has a gap. In other words, P[i,j] includes 3 or 4.

Thank you so much for taking the time to write this out, it is very helpful. I've been working through some of the visualizations of the score matrices and it's starting to click. I'll post here if I get really stuck, or I'll post the solution if I succeed.

Adenina con timina (A - T), ¿eso es correcto como alineación optima resultante? en la linea 116 y 117 hay un resultado que alinea adenina con timina, ¿me podrian explicar si eso se toma en cuenta como una alineación? ¿no debería haber un gap? o deleción ¿?

@JFOZ1010

Mantenemos la puntuación por coincidencia, no coincidencia y gap. La elección en cada posición depende de la mejor puntuación posible para la alineación global.

Podemos aumentar la puntuación no coincidente para evitar (A - T):

In [2]: print(nw(x, y, gap = 1, mismatch = 1))
GCAG-GCAAGTGG--GGCAC-CCGTATCCTTTC-CAAC-TTACAAGGGTCC-CCGT-T-
G-TGCGCCAGAGGAAGTCACTTTATATCC--GCGC-ACGGTAC-----TCCTTTTTCTA

In [3]: print(nw(x, y, gap = 1, mismatch = 2))
--GCAGGCA-AGTG-GGGCACCCGTATCCT-T-TCCAACTTACAAGGGT-C-CC-----CGTT
GTGC-GCCAGAG-GAAGTCA--C-T-T--TATATCC-GC--GC-ACGGTACTCCTTTTTC-TA

In [4]: print(nw(x, y, gap = 1, mismatch = 3))
----G-C--AGGCAAGTGGGGCACCCGTATCCT-T-T-C-C-AACTTACAAGGGT-C-CC-----CGT-T
GTGCGCCAGAGG-AAGT----CA--C-T-T--TATATCCGCG--C--AC---GGTACTCCTTTTTC-TA-

In [5]: print(nw(x, y, gap = 1, mismatch = 4))
----G-C--AGGCAAGTGGGGCACCCGTATCCT-T-T-C-C-AACTTACAAGGGT-C-CC-----CGT-T
GTGCGCCAGAGG-AAGT----CA--C-T-T--TATATCCGCG--C--AC---GGTACTCCTTTTTC-TA-

---

This R code is slow, but it might be useful for visualizing some examples of sequence alignments: https://gist.github.com/slowkow/508393

The score matrix F is represented with numbers.

The pointer matrix P is represented with arrows pointing up, left, or up-left to indicate gaps (up or left) or match/mismatch (up-left).

can you please tell me the changes i need to do in this code for finding the most optimal alignment cosidering Smith Watterman algorithm for local alignment ??

@ayush-mourya There are lot of resources online that you might want to look at. Don't give up, keep reading!

Here is one resource that seems relevant to your question: https://open.oregonstate.education/appliedbioinformatics/chapter/chapter-3/

(University websites are always a great starting point, try searching for queries like smith-waterman site:edu to get results from universities.)

In the Needleman-Wunsch (global alignment) algorithm, we start from the bottom-right corner of the matrix, and we move upward and to the left, stopping in the top-left corner of the matrix. This ensures that we globally align all of the bases from the two sequences.

In the Smith-Waterman (local alignment) algorithm, we do not always start from the bottom-right corner of the matrix. Instead, we choose the maximum value from the bottom row or the right-most column. From that position, we proceed upward and to the left, but we can stop before we reach the top-left corner. This means we are interested in the local alignment of a subset of the first and second sequences, not the global alignment of the entirety of the two sequences.

I hope that helps! Good luck with your learning.