diff --git a/alignment/align.py b/alignment/align.py index 7a35de0..ef6dd73 100644 --- a/alignment/align.py +++ b/alignment/align.py @@ -1,3 +1,4 @@ + MATCH_SCORE = 1 MISMATCH_SCORE = 0 DELETION_SCORE = 0 @@ -5,29 +6,29 @@ INSERTION_SCORE = 0 def align(left, right): - matrix = {} + matrix = [[0] * (len(right) + 1) for i in range(len(left) + 1)] # Initialise - matrix[0, 0] = 0 - traceback = {} + matrix[0][0] = 0 + traceback = [[None] * (len(right) + 1) for i in range(len(left) + 1)] for i in xrange(len(left)): - matrix[i+1, 0] = (i+1) * DELETION_SCORE - traceback[i+1, 0] = i, 0 + matrix[i+1][0] = (i+1) * DELETION_SCORE + traceback[i+1][0] = i, 0 for i in xrange(len(right)): - matrix[0, i+1] = (i+1) * INSERTION_SCORE - traceback[0, i+1] = 0, i + matrix[0][i+1] = (i+1) * INSERTION_SCORE + traceback[0][i+1] = 0, i for i, symbol_left in enumerate(left): for j, symbol_right in enumerate(right): - match_score = matrix[i, j] + MATCH_SCORE if symbol_left == symbol_right else MISMATCH_SCORE - deletion = matrix[i, j+1] + DELETION_SCORE - insertion = matrix[i+1, j] + INSERTION_SCORE - matrix[i+1, j+1], traceback[i+1, j+1] = max((match_score, (i, j)), + match_score = matrix[i][j] + MATCH_SCORE if symbol_left == symbol_right else MISMATCH_SCORE + deletion = matrix[i][j+1] + DELETION_SCORE + insertion = matrix[i+1][j] + INSERTION_SCORE + matrix[i+1][j+1], traceback[i+1][j+1] = max((match_score, (i, j)), (deletion, (i, j+1)), (insertion, (i+1, j)), key=lambda x: x[0]) - return matrix[len(left), len(right)], traceback \ No newline at end of file + return matrix[len(left)][len(right)], traceback diff --git a/alignment/alignment.py b/alignment/alignment.py index f10c00e..0a085e7 100644 --- a/alignment/alignment.py +++ b/alignment/alignment.py @@ -9,7 +9,7 @@ def construct_alignment(left, right, traceback): # While we're not at the border while l > 0 or r > 0: - new_l, new_r = traceback[l, r] + new_l, new_r = traceback[l][r] if new_l == l: # insertion sequence_l.append('-') @@ -47,7 +47,12 @@ def main(left, right): if __name__ == '__main__': from sequences import P53_MOUSE, P53_HUMAN - main(P53_HUMAN, P53_MOUSE) - + import time + t = [] + for i in range(4): + t0 = time.time() + main(P53_HUMAN, P53_MOUSE) + t.append(time.time() - t0) + print t