SW algorithm | Python Fiddle

from Bio.SubsMat import MatrixInfo
b62 = MatrixInfo.blosum62
for key in b62.keys():
    b62[(key[1],key[0])] = b62[key]

#Smith-Waterman:
def SW(string1, string2, scoring_dict = b62, gap = -6, verbose = True):
    """
    Performs Smith-Waterman alignment of string1 and string2.
    Returns the array of scores and pointers(arrows).
    If verbose=True (the default) then the alignment is printed out as well.
    
    EXAMPLE:
        Scores, Pointers = SW('Pelican', 'trellisant', verbose = True)
        P-E-LICAN-
        TRELLISANT
        Score: 3
    """   
    # Initialize scoring and 'arrow' (traceback) matrices to 0
    Scores = [[0 for x in range(len(string2)+1)] for y in range(len(string1)+1)]
    Pointers = [[0 for x in range(len(string2)+1)] for y in range(len(string1)+1)]
    
    # Convert to uppercase:
    string1 = string1.upper()
    string2 = string2.upper()
    
    # Initialize borders.
    # For pointers (arrows), use 2 for diagonal, -1 for horizontal, and 1 for vertical moves (these
    # are completely arbitrary codes).
    # The index i is used for rows (vertical positions) in the score and pointer tables, and j for columns (horizontal positions).
    for i in range(len(string1)+1):
        Scores[i][0] = 0*i  
        Pointers[i][0] = 1
    for j in range(len(string2)+1):
        Scores[0][j] = 0*j 
        Pointers[0][j] = -1
        
    # Fill the dynamic programming table with scores
    for i in range(1,len(string1)+1):
        for j in range(1,len(string2)+1):
            letter1 = string1[i-1]
            letter2 = string2[j-1]
            DiagonalScore = Scores[i-1][j-1] + scoring_dict[(letter1, letter2)]
            HorizontalScore = Scores[i][j-1] + gap
            UpScore = Scores[i-1][j] + gap
            # TempScores is list of the three scores and their pointers
            TempScores = [[DiagonalScore,2],[HorizontalScore,-1],[UpScore,1],[0,-1]]
            # Now we keep the highest score, and the associated direction (pointer)
            Scores[i][j], Pointers[i][j] = max(TempScores)
            
            
    # Find where the maximum score is in
    
            
            
            
    # backtrace from the last entry.  
    [i,j] = [len(string1),len(string2)]
    align1 = ''
    align2 = ''
    while [i,j] != [0,0]:
        
        if max(Scores[i],[j])
        
        if Pointers[i][j] == 2:
            align1 = align1 + string1[i-1]
            align2 = align2 + string2[j-1]
            i = i - 1
            j = j - 1
        elif Pointers[i][j] == -1:
            align1 = align1 + '-'
            align2 = align2 + string2[j-1]
            j = j - 1
        else:
            align1 = align1 + string1[i-1]
            align2 = align2 + '-'
            i = i - 1
            
    # the alignments have been created backwards, so we need to reverse them:
    align1 = align1[::-1]
    align2 = align2[::-1]
    
    # print out alignment if desired (if verbose==True)
    if verbose == True:
        print align1
        print align2
        print 'Score: ' + str(Scores[len(string1)][len(string2)])
    
    # in case you want to look at the scores and pointers, the function returns them
    return [Scores,Pointers]

Python Fiddle

Python Cloud IDE