<jupyter_start><jupyter_text>Imports<jupyter_code>import numpy as np
from ete3 import Tree
import pprint
import random<jupyter_output>C:\Users\karna\anaconda3\lib\site-packages\ete3-3.1.2-py3.7.egg\ete3\evol\parser\codemlparser.py:221: SyntaxWarning: "is" with a literal. Did you mean "=="?
C:\Users\karna\anaconda3\lib\site-packages\ete3-3.1.2-py3.7.egg\ete3\evol\parser\codemlparser.py:221: SyntaxWarning: "is" with a literal. Did you mean "=="?<jupyter_text>Variables<jupyter_code>STEP_MATRIX = np.array([[0, 3, 4, 9],
                       [3, 0, 2, 4],
                       [4, 2, 0, 4],
                       [9, 4, 4, 0]])

N_SPECIES = STEP_MATRIX.shape[0]

STR_JOIN = "+"

CHAR_ORDER = ["A", "C", "G", "T"]

DIC1 = {
          'Probopass':np.array([0,np.inf,np.inf,np.inf]),
          'Aggron':np.array([np.inf,np.inf,np.inf,0]),
          'Bastiodon':np.array([np.inf,np.inf,np.inf,0]),
          'Regirock':np.array([np.inf,np.inf,0,np.inf]),
          'Registeel':np.array([np.inf,np.inf,0,np.inf]),
          'Regice':np.array([np.inf,np.inf,0,np.inf]),
          'Klingklang':np.array([np.inf,np.inf,0,np.inf]),
          'Metagross':np.array([np.inf,0,np.inf,np.inf]),
          'Genesect':np.array([0,np.inf,np.inf,np.inf]),
          'Porygon=Z':np.array([np.inf,0,np.inf,np.inf]),
          'Magnezone':np.array([np.inf,0,np.inf,np.inf]),
          'Forretress':np.array([np.inf,np.inf,np.inf,0]),
          'Electrode':np.array([0,np.inf,np.inf,np.inf]),
          'Ferrothorn':np.array([np.inf,np.inf,0,np.inf]),
       }

N1 = "(((( Electrode , Magnezone) ,Porygon=Z) , (((( Aggron , Bastiodon ) , Forretress ) , Ferrothorn ) , ((((( Regirock , Regice ) , Registeel ) , Metagross ) , Klingklang ) , Genesect ))) , Probopass );"
N2 = "((((( Regirock , Regice ) , Registeel ) , (( Metagross , Klingklang ) , Genesect )) , ((( Aggron , Bastiodon ) ,( Forretress , Ferrothorn )) , Probopass )) ,( Porygon=Z,( Magnezone , Electrode )));"<jupyter_output><empty_output><jupyter_text>Trees   Tree visualization<jupyter_code>tree1 = Tree(N1)
print(N1)
print(tree1)<jupyter_output>(((( Electrode , Magnezone) ,Porygon=Z) , (((( Aggron , Bastiodon ) , Forretress ) , Ferrothorn ) , ((((( Regirock , Regice ) , Registeel ) , Metagross ) , Klingklang ) , Genesect ))) , Probopass );

            /-Electrode
         /-|
      /-|   \-Magnezone
     |  |
     |   \-Porygon=Z
     |
     |            /-Aggron
     |         /-|
     |      /-|   \-Bastiodon
   /-|     |  |
  |  |   /-|   \-Forretress
  |  |  |  |
  |  |  |   \-Ferrothorn
  |  |  |
  |  |  |               /-Regirock
  |  |  |            /-|
  |   \-|         /-|   \-Regice
--|     |        |  |
  |     |      /-|   \-Registeel
  |     |     |  |
  |     |   /-|   \-Metagross
  |     |  |  |
  |      \-|   \-Klingklang
  |        |
  |         \-Genesect
  |
   \-Probopass<jupyter_text>Sankoff algorithm >Ca aurait du être beaucoup plus simple et beaucoup moins long, je m'en suis rendu compte mais je voulais voir si j'étais capable de réussir en continuant sur ma premiere intuition.<jupyter_code>def sankoff(tree):
    init_solo_leaves() # Initialisation of the solo leaves for the traceback function
    new_tree = parse_string(tree) # In this part we clean and parse the string to get an array
    merge_cluster(new_tree) # In this part we merge the clusters and add the new array values of intern nodes in the dictionnary
    new_chars = traceback() # Traceback in the dictionnary and gets the new characters of the nodes
    new_dic = update_dic(new_chars)
    parcimony_score = compute_score(new_chars, new_dic) # Computes the parcimony score of the tree
    return new_dic, parcimony_score

def parse_string(tree):
    tree = tree.replace(" ","")
    tree = tree.replace(";","")
    new_tree = []
    for i in range(len(tree)):
        if tree[i] == ")":
            cpt = 0
            for j in range(i, 0, -2):
                if tree[j] == ")" and tree[j-1] == ")": # Discriminate mini/big cluster and get offset
                    cpt += 1
            tmp_tree = tree[:i] # Cut after parenthesis
            n_close_par = tmp_tree.count(")") # Counts open and close parenthesis
            n_open_par = tmp_tree.count("(")
            if cpt == 1: # Big cluster
                parenthesis_to_cut = n_open_par - n_close_par + cpt + 1 # FIX BUG HERE WITH N2
                nth = find_nth(tmp_tree, "(", parenthesis_to_cut) # Finds the index to cut at the right open parenthesis
                tmp_tree = tmp_tree[nth:] 
            else: # Mini cluster
                index_par = tmp_tree.rfind("(") # For mini cluster : just cut at first open parenthesis met
                tmp_tree = tmp_tree[index_par:]
            tmp_tree = tmp_tree.replace("(","") # Delete all parenthesis to extract leaves
            tmp_tree = tmp_tree.replace(")","")
            leaves = tmp_tree.split(",")
            new_tree.append(leaves) # We build a new list of list containing leaves
    return new_tree

def merge_cluster(new_tree):
    visited = []
#     species = np.unique(np.concatenate(np.array(new_tree)).flatten()) # Gets the species of the tree
    for i in range(len(new_tree)):
        if len(new_tree[i]) == 2: # Merge of 2 elements
            elt1 = new_tree[i][0]
            elt2 = new_tree[i][1]
            new_ancester = add_ancester(elt1, elt2)
            visited.append(new_ancester)
        else: # Merge of clusters
            tmp_str = new_tree[i][0]
            str_possible = []
            for j in range(1, len(new_tree[i])-1):
                tmp_str += STR_JOIN + new_tree[i][j]
                str_possible.append(tmp_str)
            str_possible.reverse() # All the existing clusters in this array
            if tmp_str in visited: # Merge of mini clusters
                visited.remove(tmp_str) # If we find one we remove it from the visited array
                del_elt = tmp_str.split(STR_JOIN)
                new_elt = new_tree[i].copy() # Copy because we remove from new_elt after that
                for elt in del_elt:
                    new_elt.remove(elt)
                new_ancester = add_ancester(tmp_str, new_elt[0])
                visited.append(new_ancester)
            else: # Merge of big clusters
                str_possible = []
                for j in range(1, len(new_tree[i])):
                    tmp_str += STR_JOIN + new_tree[i][j]
                    str_possible.append(tmp_str)
                str_possible.reverse() 
                new_list = []
                for j in range(len(visited)):
                    if visited[j] in tmp_str: # This time there can be multiple clusters
                        new_list.append(visited[j])
                new_ancester = add_ancester(new_list[0], new_list[1])
                visited.append(new_ancester)
                visited.remove(new_list[0])
                visited.remove(new_list[1])
    
def find_nth(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+len(needle))
        n -= 1
    return start
    
def add_ancester(elt1, elt2):
    new_ancester = elt1+STR_JOIN+elt2 
    if len(DIC1[elt1]) != 4: # Have to check if we just have the basic array
        val1 = DIC1[elt1][0] # or if we have the array + backtrack characters
    else:
        val1 = DIC1[elt1]
    if len(DIC1[elt2]) != 4:
        val2 = DIC1[elt2][0]
    else:
        val2 = DIC1[elt2]
    new_values = compute_new_values(val1, val2)
    add_to_backtrack_dic(val1, val2, new_ancester, new_values)
    return new_ancester
    
def compute_new_values(val1, val2):
    new_array = np.zeros((N_SPECIES))
    for i in range(N_SPECIES):
        new_array[i] = np.min(STEP_MATRIX[i]+val1) + np.min(STEP_MATRIX[i]+val2)
    return new_array

def add_to_backtrack_dic(val1, val2, new_ancester, new_values):
    min_index1, min_index2 = np.argmin(val1), np.argmin(val2)
    DIC1[new_ancester] = [new_values, CHAR_ORDER[min_index1], CHAR_ORDER[min_index2]] 
    
def init_solo_leaves():
    for key in DIC1:
        if STR_JOIN not in key:
            DIC1[key] = [DIC1[key], CHAR_ORDER[np.argmin(DIC1[key])]]

def get_parent(dic, child):
    for k in dic.keys():
        if child + STR_JOIN + k in dic.keys():
            return child + STR_JOIN + k
        elif k + STR_JOIN + child in dic.keys():
            return k + STR_JOIN + child
    return child

def copy_dic(dic):
    new_dic = {}
    for key, value in dic.items():
        new_dic[key] = value
    return new_dic

def traceback():
    new_chars = []
    first_elem = True
    dic_save = copy_dic(DIC1) # Copy not working ? Function copy() not working either ? Have to mutate the global DIC...
    for key, item in reversed(DIC1.items()): # The values are already possible values for the final one
        tmp_item = item[1:] # Ignoring array values
        if len(tmp_item) == 2 and tmp_item[0] == tmp_item[1]: # When we have to chose between same letters
            element_to_add = tmp_item[0] # we have pick the first one
            dic_save[key].remove(tmp_item[1]) # and delete the other one
        else:
            if STR_JOIN in key: # If its not a leaf we need to chose a character
                if first_elem: # Chose character randomly for the first node
                    element_to_add = tmp_item[1]
                    first_elem = False
                else: # If it's not the first node
                    for elt in tmp_item: # For each element in the list
                        tmp_parent = get_parent(dic_save, key) # Get the parent of the key to check if the element can be chosen according to its parent
                        if elt in dic_save[tmp_parent]: # If the element is the same than one of the parent one 
                            element_to_add = elt # Then we append it
                            break
                        else:
                            element_to_add = tmp_item[1]
                            break
            else: # If its a leaf we just copy the value
                element_to_add = tmp_item[0]  
        new_chars.append(element_to_add)
        if len(dic_save[key]) > 2: # This block deletes the element that is not selected by the previous conditions
            for element in dic_save[key]:
                if len(element) != 4 and element != element_to_add:
                    dic_save[key].remove(element)
    return new_chars

def update_dic(new_chars):
    new_dic = {}
    index = 0
    for key in reversed(DIC1):
        new_dic[key] = new_chars[index]
        index += 1
    return new_dic

def compute_score(new_chars, new_dic):
    score = 0
    for k1 in new_dic.keys():
        for k2 in new_dic.keys():
            if k1 + STR_JOIN + k2 in new_dic.keys(): # If k1 and k2 are leaves
                if new_dic[k1] != new_dic[k1 + STR_JOIN + k2]: # Then check if their values are the same as their parents
                    score += 1
                if new_dic[k2] != new_dic[k1 + STR_JOIN + k2]:
                    score += 1
    return score

# Forgot a dictionnary isn't ordered :) 
# def order_dic(dic): # Reversing parsing function to find the right connections between nodes
#     couples = []
#     parent = []
#     for key in reversed(dic):
#         for elt in reversed(dic.keys()):
#             if elt in key and elt != key: # We find the biggest child thanks to the reversed key
#                 elt1 = elt # The first element is the big one
#                 elt2 = key.replace(elt, "") # The second element is the remaining node
#                 if elt2[0] == STR_JOIN:
#                     elt2 = elt2[1:]
#                 if elt2[-1] == STR_JOIN:
#                     elt2 = elt2[:-1]
#                 parent.append(dic[elt])
#                 couples.append([elt1, elt2])
#                 break
#     flatten_couples = []
#     for i in range(len(couples)): # Flatten the array
#         flatten_couples.append(couples[i][0])
#         flatten_couples.append(couples[i][1])
#     new_dic = {}
#     first_elem = True
#     for node in flatten_couples: # Use the flattened array order to sort the dic
#         for key in reversed(dic): 
#             if first_elem: # Init with first value
#                 new_dic[key] = dic[key]
#                 first_elem = False
#             if node == key:
#                 new_dic[key] = dic[key]
#     return new_dic, parent<jupyter_output><empty_output><jupyter_text>Result for N1<jupyter_code>new_dic1, parcimony_score1 = sankoff(N1)
print("Parcimony score N1:", parcimony_score1)
print("Dictionnary after sankoff process on N1:")
pprint.pprint(DIC1, sort_dicts=False)<jupyter_output>Parcimony score N1: 6
Dictionnary after sankoff process on N1:
{'Probopass': [array([ 0., inf, inf, inf]), 'A'],
 'Aggron': [array([inf, inf, inf,  0.]), 'T'],
 'Bastiodon': [array([inf, inf, inf,  0.]), 'T'],
 'Regirock': [array([inf, inf,  0., inf]), 'G'],
 'Registeel': [array([inf, inf,  0., inf]), 'G'],
 'Regice': [array([inf, inf,  0., inf]), 'G'],
 'Klingklang': [array([inf, inf,  0., inf]), 'G'],
 'Metagross': [array([inf,  0., inf, inf]), 'C'],
 'Genesect': [array([ 0., inf, inf, inf]), 'A'],
 'Porygon=Z': [array([inf,  0., inf, inf]), 'C'],
 'Magnezone': [array([inf,  0., inf, inf]), 'C'],
 'Forretress': [array([inf, inf, inf,  0.]), 'T'],
 'Electrode': [array([ 0., inf, inf, inf]), 'A'],
 'Ferrothorn': [array([inf, inf,  0., inf]), 'G'],
 'Electrode+Magnezone': [array([ 3.,  3.,  6., 13.]), 'C'],
 'Electrode+Magnezone+Porygon=Z': [array([ 6.,  3.,  7., 11.]), 'C'],
 'Aggron+Bastiodon': [array([18.,  8.,  8.,  0.]), 'T'],
 'Aggron+Bastiodon+Forretress': [array([18.,  8.,  8., [...]<jupyter_text>Reset of the global variable DIC1 because we removed items while processing N1<jupyter_code>DIC1 = {
          'Probopass':np.array([0,np.inf,np.inf,np.inf]),
          'Aggron':np.array([np.inf,np.inf,np.inf,0]),
          'Bastiodon':np.array([np.inf,np.inf,np.inf,0]),
          'Regirock':np.array([np.inf,np.inf,0,np.inf]),
          'Registeel':np.array([np.inf,np.inf,0,np.inf]),
          'Regice':np.array([np.inf,np.inf,0,np.inf]),
          'Klingklang':np.array([np.inf,np.inf,0,np.inf]),
          'Metagross':np.array([np.inf,0,np.inf,np.inf]),
          'Genesect':np.array([0,np.inf,np.inf,np.inf]),
          'Porygon=Z':np.array([np.inf,0,np.inf,np.inf]),
          'Magnezone':np.array([np.inf,0,np.inf,np.inf]),
          'Forretress':np.array([np.inf,np.inf,np.inf,0]),
          'Electrode':np.array([0,np.inf,np.inf,np.inf]),
          'Ferrothorn':np.array([np.inf,np.inf,0,np.inf]),
       }<jupyter_output><empty_output><jupyter_text>Result for N2<jupyter_code>new_dic2, parcimony_score2 = sankoff(N2)
print("Parcimony score N2:", parcimony_score2)
print("Dictionnary after sankoff process on N2:")
pprint.pprint(new_dic2, sort_dicts=False)<jupyter_output>Parcimony score N2: 7
Dictionnary after sankoff process on N2:
{'Regirock+Regice+Registeel+Metagross+Klingklang+Genesect+Aggron+Bastiodon': 'T',
 'Magnezone+Electrode': 'C',
 'Forretress+Ferrothorn+Probopass': 'G',
 'Forretress+Ferrothorn': 'G',
 'Aggron+Bastiodon': 'T',
 'Regirock+Regice+Registeel+Metagross+Klingklang+Genesect': 'A',
 'Metagross+Klingklang+Genesect': 'A',
 'Metagross+Klingklang': 'G',
 'Regirock+Regice+Registeel': 'G',
 'Regirock+Regice': 'G',
 'Ferrothorn': 'G',
 'Electrode': 'A',
 'Forretress': 'T',
 'Magnezone': 'C',
 'Porygon=Z': 'C',
 'Genesect': 'A',
 'Metagross': 'C',
 'Klingklang': 'G',
 'Regice': 'G',
 'Registeel': 'G',
 'Regirock': 'G',
 'Bastiodon': 'T',
 'Aggron': 'T',
 'Probopass': 'A'}
{'fraction_non_alphanumeric': 0.1440748573992181, 'fraction_numerical': 0.016214830481317697, 'mean_word_length': 2.393649412788169, 'pattern_counts': {'":': 2, '<': 25, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '420931', 'license': 'MIT', 'n_tokens_mistral': 5734, 'n_tokens_neox': 5541, 'n_words': 1274, 'path': 'S1/AAGB/TME/PARTIE BIOINFORMATICS/TME3/TME3DurandKordon.ipynb', 'repo_name': 'hanzopgp/MasterBioInformaticsPTs', 'size': '15603'}