-
-
Save slowkow/06c6dba9180d013dfd82bec217d22eb5 to your computer and use it in GitHub Desktop.
#!/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 ¿?
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.
@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.