我被分配了一个任务,需要对两个DNA序列之间的最低成本进行对齐。其中一个失败的输入如下:
CGCAATTCTGAAGCGCTGGGGAAGACGGGT & TATCCCATCGAACGCCTATTCTAGGAT
适当的对齐成本是24,但我得到了23的成本。
我必须读取切换碱基的成本,例如A->T,G->C等等...我收到的成本文件如下:
*,-,A,T,G,C
-,0,1,2,1,3
A,1,0,1,5,1
T,2,1,0,9,1
G,1,5,9,0,1
C,3,1,1,1,0
我已经创建了一个Python字典,完美地将所有基本部分连接起来,它看起来像这样:
{'AT': '1', '-C': '3', 'TG': '9', '-G': '1', 'AC': '1', 'C-': '3', 'CA': '1', 'AA': '0', '--': '0', 'TA': '1', 'T-': '2', 'CG': '1', '-T': '2', 'CC': '0', 'GG': '0', 'A-': '1', 'CT': '1', 'AG': '5', 'GC': '1', 'GT': '9', 'GA': '5', 'G-': '1', '-A': '1', 'TC': '1', 'TT': '0'}
目前我的实现在某些情况下可以工作,在其他情况下可能会与实际结果相差 +/- 1。
下面是我的代码片段:
def align(one_Line, costBook):
Split_Line = one_Line.split(",")
array = [[0] * len(Split_Line[1]) for i in Split_Line[0]] # Zero fill array,
xLine = Split_Line[0]
yLine = Split_Line[1]
for i in range(1, len(xLine)):
array[i][0] = array[i - 1][0] + int(costBook['-' + xLine[i - 1]])
for i in range(1, len(yLine)):
array[0][i] = array[0][i - 1] + int(costBook[yLine[i - 1] + '-'])
for i in range(1, len(xLine)):
for j in range(1, len(yLine)):
array[i][j] = min(array[i - 1][j] + diff('-', xLine[i], costBook),
array[i][j - 1] + diff(yLine[j], '-', costBook),
array[i - 1][j - 1] + diff(yLine[j], xLine[i], costBook))
diff函数的作用是:
def diff(x, y, cost):
if x == y:
return 0
keyStr = x + y
return int(costBook[keyStr])
我哪里出错了?是在实际的数组填充过程中,还是我的基本情况处理有误?
编辑:这是一个半工作的版本,至少编辑成本是正确的:
AGTTGTGAAAGAACAAGCGCACAATATTGCCGCGCCGAAAGCT,TTCTTTCATTATTCAAATGTATAGTTTAGAGCGTTAA