Skip to content

Instantly share code, notes, and snippets.

@slowkow
Last active July 29, 2024 19:31
Show Gist options
  • Save slowkow/06c6dba9180d013dfd82bec217d22eb5 to your computer and use it in GitHub Desktop.
Save slowkow/06c6dba9180d013dfd82bec217d22eb5 to your computer and use it in GitHub Desktop.
A simple version of the Needleman-Wunsch algorithm in Python.
#!/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
@slowkow
Copy link
Author

slowkow commented Oct 2, 2022

@Heitor-Leal-Farnese Please see the Wikipedia page for multiple sequence alignment algorithms to learn about some ideas for aligning more than 2 sequences. The publication about MUSCLE might be an interesting starting point.

@rbracco
Copy link

rbracco commented Nov 7, 2022

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.

@slowkow
Copy link
Author

slowkow commented Nov 7, 2022

@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.

@rbracco
Copy link

rbracco commented Nov 7, 2022

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.

@JFOZ1010
Copy link

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 ¿?

@slowkow
Copy link
Author

slowkow commented Oct 25, 2023

@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).

nw-02

@ayush-mourya
Copy link

ayush-mourya commented Mar 21, 2024

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 ??

@slowkow
Copy link
Author

slowkow commented Mar 21, 2024

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment