jon*_*lls 7 python bioinformatics sequence-alignment
我正在尝试实现Waterman-Eggert算法来寻找次优的局部序列比对,但我正在努力理解如何"解散"单独的比对组.我有基本的Smith-Waterman算法正常工作.
一个简单的测试,将以下序列与自身对齐:
'HEAGHEAGHEAG'
'HEAGHEAGHEAG'
产生一个fMatrix如下:
[[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 8. 0. 0. 0. 8. 0. 0. 0. 8. 0. 0. 0.]
[ 0. 0. 13. 0. 0. 0. 13. 0. 0. 0. 13. 0. 0.]
[ 0. 0. 0. 17. 0. 0. 0. 17. 0. 0. 0. 17. 0.]
[ 0. 0. 0. 0. 23. 0. 0. 0. 23. 0. 0. 0. 23.]
[ 0. 8. 0. 0. 0. 31. 0. 0. 0. 31. 0. 0. 0.]
[ 0. 0. 13. 0. 0. 0. 36. 0. 0. 0. 36. 0. 0.]
[ 0. 0. 0. 17. 0. 0. 0. 40. 0. 0. 0. 40. 0.]
[ 0. 0. 0. 0. 23. 0. 0. 0. 46. 0. 0. 0. 46.]
[ 0. 8. 0. 0. 0. 31. 0. 0. 0. 54. 4. 0. 0.]
[ 0. 0. 13. 0. 0. 0. 36. 0. 0. 4. 59. 9. 0.]
[ 0. 0. 0. 17. 0. 0. 0. 40. 0. 0. 9. 63. 13.]
[ 0. 0. 0. 0. 23. 0. 0. 0. 46. 0. 0. 13. 69.]]
为了找到次优比对,例如
'HEAGHEAGHEAG '
' HEAGHEAGHEAG'
你必须首先删除最佳对齐(即沿主对角线)并重新计算fMatrix; 这被称为"解块",其中对齐的"丛"被定义为其路径相交/共享一对或多对对齐残基的任何比对.除了fMatrix之外,还有一个辅助矩阵,其中包含有关fMatrix构造方向的信息.
构建fMatrix和回溯矩阵的代码片段如下:
# Generates fMatrix.
for i in range(1, length):
for j in range(1, length):
matchScore = fMatrix[i-1][j-1] + simMatrixDict[seq[i-1]+seq[j-1]]
insScore = fMatrix[i][j-1] + gap
delScore = fMatrix[i-1][j] + gap
fMatrix[i][j] = max(0, matchScore, insScore, delScore)
# Generates matrix for backtracking.
if fMatrix[i][j] == matchScore:
backMatrix[i][j] = 2
elif fMatrix[i][j] == insScore:
backMatrix[i][j] = 3 # INSERTION in seq - Horizontal
elif fMatrix[i][j] == delScore:
backMatrix[i][j] = 1 # DELETION in seq - Vertical
if fMatrix[i][j] >= backtrackStart:
backtrackStart = fMatrix[i][j]
endCoords = i, j
return fMatrix, backMatrix, endCoords
为了消除这种最佳对齐,我尝试使用这个backMatrix来回溯fMatrix(根据原始的Smith-Waterman算法)并按fMatrix[i][j] = 0我的方式设置,但是这并没有移除整个丛,只有那个丛中的精确对齐.
对于一些背景信息,Smith-Waterman算法的维基百科页面解释了如何构建fMatrix,并且这里有关于回溯如何工作的解释.特曼-Eggert的算法大致解释在这里.
谢谢.
好的。这里有一些代码可以完成您想要的操作。我使用了漂亮的打印库 ( pprint)，因此输出看起来不错。（如果矩阵中的数字是个位数，看起来最好，但如果有多位数字，对齐就会有点混乱。）
因为你只需要改变主对角线上的数字以及上下对角线上的数字，所以我们只需要一个 for 循环。matrix[i][i]总是在主对角线上，因为它是i行向下、i列跨的。matrix[i][i-1]始终是下相邻的对角线，因为它是i行向下、i-1列跨的。matrix[i-1][i]始终是上相邻的对角线，因为它是i-1向下的行，i横向的行。
#!/usr/bin/python
import pprint
matrix = [
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
[ 0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0,],
[ 0, 0, 13, 0, 0, 0, 13, 0, 0, 0, 13, 0, 0,],
[ 0, 0, 0, 17, 0, 0, 0, 17, 0, 0, 0, 17, 0,],
[ 0, 0, 0, 0, 23, 0, 0, 0, 23, 0, 0, 0, 23,],
[ 0, 8, 0, 0, 0, 31, 0, 0, 0, 31, 0, 0, 0,],
[ 0, 0, 13, 0, 0, 0, 36, 0, 0, 0, 36, 0, 0,],
[ 0, 0, 0, 17, 0, 0, 0, 40, 0, 0, 0, 40, 0,],
[ 0, 0, 0, 0, 23, 0, 0, 0, 46, 0, 0, 0, 46,],
[ 0, 8, 0, 0, 0, 31, 0, 0, 0, 54, 4, 0, 0,],
[ 0, 0, 13, 0, 0, 0, 36, 0, 0, 4, 59, 9, 0,],
[ 0, 0, 0, 17, 0, 0, 0, 40, 0, 0, 9, 63, 13,],
[ 0, 0, 0, 0, 23, 0, 0, 0, 46, 0, 0, 13, 69,]]
print "Original Matrix"
pprint.pprint(matrix)
print
for i in range(len(matrix)):
matrix[i][i] = 0
if (i > 0) and (i < (len(matrix))):
matrix[i][i-1] = 0
matrix[i-1][i] = 0
print "New Matrix"
pprint.pprint(matrix)
Original Matrix
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 13, 0, 0, 0, 13, 0, 0, 0, 13, 0, 0],
[0, 0, 0, 17, 0, 0, 0, 17, 0, 0, 0, 17, 0],
[0, 0, 0, 0, 23, 0, 0, 0, 23, 0, 0, 0, 23],
[0, 8, 0, 0, 0, 31, 0, 0, 0, 31, 0, 0, 0],
[0, 0, 13, 0, 0, 0, 36, 0, 0, 0, 36, 0, 0],
[0, 0, 0, 17, 0, 0, 0, 40, 0, 0, 0, 40, 0],
[0, 0, 0, 0, 23, 0, 0, 0, 46, 0, 0, 0, 46],
[0, 8, 0, 0, 0, 31, 0, 0, 0, 54, 4, 0, 0],
[0, 0, 13, 0, 0, 0, 36, 0, 0, 4, 59, 9, 0],
[0, 0, 0, 17, 0, 0, 0, 40, 0, 0, 9, 63, 13],
[0, 0, 0, 0, 23, 0, 0, 0, 46, 0, 0, 13, 69]]
New Matrix
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 8, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 13, 0, 0, 0, 13, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 17, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 23, 0, 0, 0, 23],
[0, 8, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0],
[0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 36, 0, 0],
[0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 40, 0],
[0, 0, 0, 0, 23, 0, 0, 0, 0, 0, 0, 0, 46],
[0, 8, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 13, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 17, 0, 0, 0, 40, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 23, 0, 0, 0, 46, 0, 0, 0, 0]]