<jupyter_start><jupyter_text>General alignment implementation<jupyter_code>import numpy as np
import pandas as pd
def create_scoring_matrix(S_raw, rows_string, cols_string):
    df = pd.DataFrame(S_raw)
    df.index = rows_string.split()
    df.columns = cols_string.split()
    return df


def general_alignment(S, reference, read, kind):
    X = '_' + reference
    Y = '_' + read
    m = len(X)
    n = len(Y)
    
    D = np.zeros((m, n), dtype=int)
    T = np.zeros((m, n), dtype=str)
    
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if i == 0 and j == 0:
                D[i, j] = 0
                T[i, j] = ''
            
            elif i == 0:
                if kind == 'ESFV':
                    D[i, j] = 0
                    T[i, j] = 'i'
                else:
                    D[i, j] = D[i, j-1] + S.loc[x][y]
                    T[i, j] = 'I'
            
            elif j == 0:
                if kind == 'ESFV':
                    D[i, j] = 0
                    T[i, j] = 'd'
                else:
                    D[i, j] = D[i-1, j] + S.loc[x][y]
                    T[i, j] = 'D'
            
            else:
                edits = []
                
                match_replace = D[i-1, j-1] + S.loc[x][y]
                edits.append('M' if x == y else 'R')
                    
                if kind == 'ESFV' and j == n-1:
                    deletion = D[i-1, j]
                    edits.append('d')
                else:
                    deletion = D[i-1, j] + S.loc[x]['_']
                    edits.append('D')
                
                if kind == 'ESFV' and i == m-1:
                    insertion = D[i, j-1]
                    edits.append('i')
                else:
                    insertion = D[i, j-1] + S.loc['_'][y]
                    edits.append('I')
                
                actions = np.asarray([match_replace, deletion, insertion])
                
                D[i, j] = max(actions)
                T[i, j] = edits[actions.argmax()]
                
    df_d = pd.DataFrame(D, list(X), list(Y))
    df_t = pd.DataFrame(T, list(X), list(Y))
    
    ret_t = ''
    ret_x = ''
    ret_bars = ''
    ret_y = ''
    
    # i, j = m, n
    
    while True:
        if T[i, j] == '':
            break
                
        if T[i, j] in ['M', 'R']:
            ret_t += T[i, j]
            ret_x += X[i]
            ret_y += Y[j]
            ret_bars += '|' if T[i, j] == 'M' else ' '
            i -= 1
            j -= 1
        elif T[i, j] == 'D':
            ret_t += T[i, j]
            ret_x += X[i]
            ret_y += '_'
            ret_bars += ' '
            i -= 1
        elif T[i, j] == 'I':
            ret_t += T[i, j]
            ret_x += '_'
            ret_y += Y[j]
            ret_bars += ' '
            j -= 1
        elif T[i, j] == 'd':
            ret_t += ' '
            ret_x += X[i]
            ret_y += ' '
            ret_bars += ' '
            i -= 1
        elif T[i, j] == 'i':
            ret_t += ' '
            ret_x += ' '
            ret_y += Y[j]
            ret_bars += ' '
            j -= 1
        
    alignment = '{x}\n{bars}\n{t}\n{bars}\n{y}'.format(x=ret_x[::-1],
                                                       bars=ret_bars[::-1],
                                                       t=ret_t[::-1],
                                                       y=ret_y[::-1])
    
    return df_d, df_t, str(alignment)<jupyter_output><empty_output><jupyter_text>Edit distanceLevenshtein distance<jupyter_code>S_raw = [[0, -1, -1, -1, -1],
         [-1, 0, -1, -1, -1],
         [-1, -1, 0, -1, -1],
         [-1, -1, -1, 0, -1],
         [-1, -1, -1, -1, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T _', 'A C G T _')
reference = 'GCGTATGCACGC'
read = 'GCTATGCCACGC'

D, T, alignment = general_alignment(S, reference, read, 'ED')

print(alignment)
D
T<jupyter_output>GCGTATG_CACGC
|| |||| |||||
MMDMMMMIMMMMM
|| |||| |||||
GC_TATGCCACGC<jupyter_text>Global alignmentNeedleman-Wunsch alignment<jupyter_code>S_raw = [[1, -3, -1, -3, -7],
         [-3, 1, -3, -1, -7],
         [-1, -3, 1, -3, -7],
         [-3, -1, -3, 1, -7],
         [-7, -7, -7, -7, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T _', 'A C G T _')
S
reference = 'TACGTCAGC'
read = 'TATGTCATGC'

D, T, alignment = general_alignment(S, reference, read, 'GA')

print(alignment)
D
reference = 'TAGCGTC'
read = 'TATGTC'

D, T, alignment = general_alignment(S, reference, read, 'GA')

print(alignment)
reference = 'TAGCGTC'
read = 'TAAGTC'

D, T, alignment = general_alignment(S, reference, read, 'GA')

print(alignment)<jupyter_output>TAGCGTC
||  |||
MMRDMMM
||  |||
TAA_GTC<jupyter_text>Longest common subsequence<jupyter_code>S_raw = [[1, -1, -1, -1, 0],
         [-1, 1, -1, -1, 0],
         [-1, -1, 1, -1, 0],
         [-1, -1, -1, 1, 0],
         [0, 0, 0, 0, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T _', 'A C G T _')
S
reference = 'TACGTCAGA'
read = 'AAAGTCATGC'

D, T, alignment = general_alignment(S, reference, read, 'LCS')

print(alignment)
D<jupyter_output>__TACGTCA_G_A
   | |||| |  
IIDMDMMMMIMID
   | |||| |  
AA_A_GTCATGC_<jupyter_text>End space-free variant<jupyter_code>S_raw = [[1, -3, -1, -3, -7],
         [-3, 1, -3, -1, -7],
         [-1, -3, 1, -3, -7],
         [-3, -1, -3, 1, -7],
         [-7, -7, -7, -7, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T _', 'A C G T _')
S
reference = 'TACGTCAGA'
read = 'GTC'

D, T, alignment = general_alignment(S, reference, read, 'ESFV')

print(alignment)
D
T<jupyter_output>TACGTCAGA
   |||   
   MMM   
   |||   
   GTC<jupyter_text>IUPAC Nucleotide representationshttps://en.wikipedia.org/wiki/Nucleic_acid_notation<jupyter_code>S_raw = [[1, -3, -1, -3, 1, -7],
         [-3, 1, -3, -1, 1, -7],
         [-1, -3, 1, -3, 1, -7],
         [-3, -1, -3, 1, 1, -7],
         [1, 1, 1, 1, 1, -7],
         [-7, -7, -7, -7, -7, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T N _', 'A C G T N _')
S
S_raw = [[1, -3, -1, -3, -7],
         [-3, 1, -3, -1, -7],
         [-1, -3, 1, -3, -7],
         [-3, -1, -3, 1, -7],
         [1, 1, 1, 1, -7],
         [-7, -7, -7, -7, np.NaN]]

S = create_scoring_matrix(S_raw, 'A C G T N _', 'A C G T _')
S
S.loc['N','T']
reference = 'TACGNCAGA'
read = 'GTC'

D, T, alignment = general_alignment(S, reference, read, 'ESFV')

print(alignment)
D
reference = 'TACGNCAGA'
read = 'GTC'

D, T, alignment = general_alignment(S, reference, read, 'GA')

print(alignment)
D
T<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1817351598173516, 'fraction_numerical': 0.028462709284627092, 'mean_word_length': 1.411376146788991, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '178446', 'license': 'MIT', 'n_tokens_mistral': 2716, 'n_tokens_neox': 2583, 'n_words': 621, 'path': 'notebooks/08c_general_alignment.ipynb', 'repo_name': 'nlazarevic/gi-2021-etf', 'size': '6570'}