아핀 갭 페널티가있는 Smith-Wateman 알고리즘의 추적

Question

아핀 갭 패널티 함수를 사용하여 로컬 시퀀스 정렬을위한 Smith-Waterman 알고리즘을 구현하려고합니다. 나는 정렬 점수를 계산하는 데 필요한 행렬을 시작하고 계산하는 방법을 이해하지만 정렬을 찾기 위해 역 추적하는 방법을 알지 못한다고 생각합니다. 필요한 3 행렬을 생성하려면 다음 코드를 사용하십시오.

for j in range(1, len2): 
    for i in range(1, len1): 
     fxOpen = F[i][j-1] + gap 
     xExtend = Ix[i][j-1] + extend 
     Ix[i][j] = max(fxOpen, xExtend) 

     fyOpen = F[i-1][j] + gap 
     yExtend = Iy[i-1][j] + extend 
     Iy[i][j] = max(fyOpen, yExtend) 

     matchScore = (F[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]]) 
     xScore = Ix[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] 
     yScore = Iy[i-1][j-1] + simMatrixDict[seq1[i-1]+seq2[j-1]] 
     F[i][j] = max(0, matchScore, xScore, yScore) 

역 추적을위한 단일 행렬이 필요한지 확실하지 않습니까? F에서 최대 점수를 추적하는 방법에 대한 명확한 설명을 주시면 감사하겠습니다.

Answer 1

Smith-Waterman의 추적에 대해 기억해야 할 중요한 점은 값이있는 행렬이 이동하는 방향을 결정한다는 것입니다. 따라서 F에 있으면 대각선으로 이동합니다. Ix이면 가로로 이동하고, Iy이면 세로로 이동합니다. 즉, 포인터 행렬에 저장해야하는 것은 사각형에 도착한 행렬입니다. 당신이가는 행렬이 아닌 당신이 오는 행렬이 갈 방향을 결정합니다.

예를 들어

:

당신이 F[5][5]에있다 말 : 포인터 매트릭스 Ix로 이동 말한다

• 경우 포인터 행렬 Iy에 가서 말한다면, Ix[4][4]
• 로 이동, 이동 ~ Iy[4][4]
• 포인터 행렬이 F으로 이동한다고하면로 이동하십시오. 당신이 Ix[5][5]에있는 경우 반면

: 포인터 매트릭스 F에 가서 말한다면

• 포인터 행렬 Ix에 가서 말한다면
  이 Ix[4][5]
• 로 이동 F[4][5]

로 이동

또는 Iy[5][5] 인 경우 :

012 포인터 행렬 Iy로 이동라고하면 포인터 행렬 F로 이동라고하면 3,516,

• , Iy[5][4]
• 이동, 첫 번째 인덱스는이 X 좌표라고 가정 F[5][4]

로 이동하여 상기 제는 y 좌표

는 포인터 행렬을 구축 0

의 최대 값을 셀에 도달 할 때까지 다시 추적을 계속 : 당신은 F, Ix 및 Iy에 대해 하나의 포인터 매트릭스 각이 필요합니다. 이 행렬은 어느 행렬에서 값이 왔는지 나타낼 필요가 있습니다. 이는 행렬이 어느 방향으로 이동했는지 알려주기 때문입니다.따라서 알고리즘의 동적 프로그래밍 단계를 실행하면서 포인터 행렬을 구축해야합니다. F, Ix 또는 Iy의 셀에 새로운 최대 값을 저장할 때마다 해당 행렬을 업데이트하여 해당 출처를 나타냅니다. 예를 들어 F[5][5]에있을 수있는 가장 높은 값이 F[4][4]에있을 때 두 개의 다음 기지를 정렬하면 F 행렬에 있기 때문에 Fpointer [5] [5]를 F으로 설정해야합니다.