Stack Exchange
Finding similarities between all IDs and associates string/sequences
I have a dataframe, which consists of two columns as shown below. I want to compute Smith Water Similarity between all these sequences using the function defined below.
def smith_waterman(seq2, seq1, d=-8):
    m = len(seq1)
    n = len(seq2)
    mat = np.zeros((m+1, n+1))      # Creating empty matrix
    
    # Add elements to all rows and columns
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            diag = mat[i-1][j-1] + sub_cost(seq1[i-1], seq2[j-1])
            up = mat[i-1][j] + d
            left = mat[i][j-1] + d
            mat[i][j] = max(0, diag, up, left)
    
    #print("Matrix:")
    #print(mat)
    
    # Finding highest value and storing its location
    highest_value = np.where(mat == np.amax(mat))
    highest_value_location = list(zip(highest_value[0], highest_value[1]))[0]
    
    traceback_seq1, traceback_seq2 = '', ''
    i, j = highest_value_location[0], highest_value_location[1]
    
    # Backward algorithm for getting traceback sequences
    while i > 0 or j > 0:
        current_score = mat[i][j]
        diag_score = mat[i-1][j-1]
        left_score = mat[i][j-1]
        up_score = mat[i-1][j]
                
        if (current_score==0):
            break
        
        if (current_score == diag_score + sub_cost(seq1[i-1], seq2[j-1])):
            t1, t2 = seq2[j-1], seq1[i-1]
            i,j = i-1,j-1
        elif (current_score == up_score + d):
            t1, t2 = '-', seq1[i-1]
            i -= 1
        elif (current_score == left_score + d):
            t1, t2 = seq2[j-1], '-' 
            j -= 1
        traceback_seq1 += t1
        traceback_seq2 += t2
    
    traceback_seq1 = (traceback_seq1[::-1])
    traceback_seq2 = (traceback_seq2[::-1])
    
    #print()
    #print("Highest value in matrix: ", np.amax(mat))
    #print()
    #print("Traceback Sequences for", seq2, "versus", seq1)
    #print(traceback_seq1)
    #print(traceback_seq2)
    return np.amax(mat)

finalDF[['Variant ID','original_sequence']].head()
Variant ID  original_sequence
0   rs1800872   GCCTTAGTTTCCCCAAGTAAAAATGAGGGGGTGGGCTAAATATCCT...
1   rs5743626   CCTGCTGGTCTGTAGGAGATGGTATTTTGGGGGCAGCTGCAAGGGA...
2   rs139073251 CTTCACTCTGCTGAAGGCATCTCGGAGATCTCGAAGCATGTTAGGC...
3   rs139352858 TCACATGCGCCTTGATGTCTGGGTCTTGGTTCTCAGCTTGGGGCAT...
4   rs141219090 GTCTTCACTCTGCTGAAGGCATCTCGGAGATCTCGAAGCATGTTAG...

the above function take two strings and return a number.
How, can I calculate the similarity between all these sequences and put the most similar together
in a dataframe.
                Variants                 Similarity RANK
0   rs1800872, rs139073251                   1    
1   rs5743626, rs139352858                   2
2   rs139073251, rs139352858, rs141219090    3
....


Hey! You have the same IDs on several rows? It it correct in your case? How many groups would you like to have?

@roddar92 No, all the IDs are different, the groups can have any number of similar IDs, but if I can get an ID vs ID matrix, I think, I can define a threshold.

You can use one of clustering algorithm with your metric (hierarchical or k-medoids), create a dataframe with groups on he each row and then assign a rank based on similarity. In your case, the similarity of a group is a sum of distance of distances between group's objects and their cluster centroid.
Although this method has some of disadvantages:

you need choose number of clusters of your own;

each sequence could have ONLY one label;



I want to use the function for calculating similarity, I defined above, that's the case
