Advertisement
Guest User

Untitled

a guest
Feb 18th, 2020
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.89 KB | None | 0 0
  1. # returns the cost of a substitution of characters a -> b
  2. def substitute(a, b):
  3. aIndex = letterList.index(a)
  4. bIndex = letterList.index(b)
  5.  
  6. blosumVal = blosumMatrix[aIndex][bIndex]
  7. return blosumVal
  8.  
  9.  
  10. # return the alignment and direction matrix for Needleman-Wunsch algorithm
  11. def nwAlignment(stringA, stringB, gapPenalty):
  12. # get matrix dimensions
  13. m = len(stringA) + 1
  14. n = len(stringB) + 1
  15.  
  16. # initalise the alignment and direction matrix
  17. alignMatrix = np.zeros((n,m), dtype=int)
  18. directionMatrix = np.zeros((n,m), dtype=str)
  19.  
  20. # insert the border values (all gaps vertical and horizontal)
  21. for i in range(n):
  22. alignMatrix[i][0] = gapPenalty * i
  23. directionMatrix[i][0] = 'V'
  24.  
  25. for j in range(m):
  26. alignMatrix[0][j] = gapPenalty * j
  27. directionMatrix[0][j] = 'H'
  28.  
  29. # overwrite the corner value in direction matrix
  30. directionMatrix[0][0] = '-'
  31.  
  32. # calculate the remaining matrix values as the max of the 3 backtracking options
  33. for i in range(1, n):
  34. for j in range(1, m):
  35. a = stringA[j-1]
  36. b = stringB[i-1]
  37.  
  38. vGap = alignMatrix[i-1][j] + gapPenalty
  39. hGap = alignMatrix[i][j-1] + gapPenalty
  40. sub = alignMatrix[i-1][j-1] + substitute(a, b)
  41.  
  42. bestMove = max(sub, hGap, vGap)
  43. alignMatrix[i][j] = bestMove
  44.  
  45. # insert the character in the direction matrix to identify which option was the best move
  46. if bestMove == sub:
  47. directionMatrix[i][j] = 'D'
  48. elif bestMove == hGap:
  49. directionMatrix[i][j] = 'H'
  50. else:
  51. directionMatrix[i][j] = 'V'
  52.  
  53. return (alignMatrix, directionMatrix)
  54.  
  55. # returns the 2 global matching strings
  56. def getGlobalMatch(stringA, stringB, directionMatrix):
  57. # inialises the start position as the bottom right corner of the matrix
  58. i = len(stringB)
  59. j = len(stringA)
  60.  
  61. # recursive function that builds up the match strings
  62. def nextMove(i, j, outputA, outputB):
  63. direction = directionMatrix[i][j]
  64.  
  65. if direction == '-':
  66. outputA = outputA[::-1]
  67. outputB = outputB[::-1]
  68. return (outputA, outputB)
  69.  
  70. elif direction == 'D':
  71. outputA = outputA + stringA[j-1]
  72. outputB = outputB + stringB[i-1]
  73. result = nextMove(i-1, j-1, outputA, outputB)
  74. return result
  75.  
  76. elif direction == 'H':
  77. outputA = outputA + stringA[j-1]
  78. outputB = outputB + '-'
  79. result = nextMove(i, j-1, outputA, outputB)
  80. return result
  81.  
  82. else:
  83. outputA = outputA + '-'
  84. outputB = outputB + stringB[i-1]
  85. result = nextMove(i-1, j, outputA, outputB)
  86. return result
  87.  
  88. result = nextMove(i, j, '', '')
  89.  
  90. return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement