Partage
  • Partager sur Facebook
  • Partager sur Twitter

Optimisation d'un code

    11 juillet 2019 à 11:45:08

    Bonjour à tous, 

    J'ai du créer un algorithme qui me donnera le chemin d'interactions le plus court entre 2 protéines, je m'explique: 

    J'ai un premier fichier qui contient les couples de protéines à tester (ex):

    prot1 prot2 (la chaine commencera par prot1 et finira par prot2)

    prot3 prot4

    ect..

    Mon second fichier est un fichier d'interactions binaire entre différentes protéines, ex :

    prot15 prot20

    prot3 prot1

    prot100 prot21

    prot1 prot16

    prot16 prot2

    ect...

    par exemple ici le chemin le plus court entre prot1 et prot2 est : prot1 prot16 prot2

    Voici mon code 

    import sys
    sys.setrecursionlimit(1000000)
    from collections import defaultdict
    dd = defaultdict(set)
    P=[]
    L=[]
    
    #Fichier contenant les proteines à tester, je met tout les couples dans une liste
    with open("C:/Users/lveillat/Desktop/Chaines minimales/3080_interactions_pour_736.txt","r") as f0:
    	for lignes0 in f0:
    		lignes0=lignes0.rstrip('\n').split(" ")
    		lignes0=lignes0[0],lignes0[1]
    		P.append(list(lignes0))
    	#print(P)
    
    #Fichier contenant toutes les interactions, je fais un dictionnaire avec en clé une protéine et en valeur toutes les protéines avec lesquelles elle intéragit
    with open("736(int_connues_avec_scores_sup_0).txt","r") as f1:
    	for lignes in f1:
    		if lignes.startswith('9606'):
    			lignes=lignes.rstrip('\n').split(" ")
    			prot1=lignes[2]
    			prot2=lignes[3]
    			dd[prot1].add(prot2)
    	#print(dd)
    
    #Fonction me permettant de construire les chaines d'interctions
    def chain(proteine1, proteine2, maillon, pathway, limite=10): 
    	next_= maillon.get(pathway[-1],None)
    
    	if len(pathway) < limite  :
    		for m in next_:
    			if m not in pathway:
    
    				if m != proteine2:
    					yield from chain(proteine1, proteine2, maillon, pathway + [m])
    
    				if m==proteine2 and pathway[0]==proteine1:
    						pathway.append(m)
    						yield pathway
    
    #Pour mes couples de protéines à étudier
    for c in P:
    	#print(c)
    	proteine1=c[0]
    	proteine2=c[1]
    	L.clear()
    	print("The first protein in the chain is", proteine1)
    	print("The last protein in the chain is", proteine2)
    	print("")
    	print("Minimal size chain(s):")
    	print("")
    
    	#Je met dans une liste toutes les chaines d'interactions possible commençant par protéine1 et terminant par protéine2
    	for k in dd: 
    		for z in chain(proteine1,proteine2, dd, pathway = [k]):
    			if z not in L:
    				L.append(z)
    	#print(L)
    
    	#J'affiche les plus petits éléments de la liste = les chaines les plus courtes
    	for z in L:
    		min_len=min(len(z) for z in L)
    		mins=[z for z in L if len(z) == min_len]
    	#print(mins)
    	for chaine in mins:
    		if chaine in mins and chaine[-1]==proteine2:
    			print(' '.join(chaine))
    		else:
    			print('ERROR - NO CHAINS BELOW THE LIMIT', )
    
    	print("")
    	print("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
    	print("")
    

    Le problème c'est qu'il est extrémement lent...y a t'il des lignes qui selon vous peuvent être optimisées et me faire gagner du temps de calcul ? 

    Merci à vous :) 

    -
    Edité par LoisVeillat 11 juillet 2019 à 11:50:40

    • Partager sur Facebook
    • Partager sur Twitter
      11 juillet 2019 à 13:57:04

      Le for dans le premier bloc with est équivalent à ça :

          for lignes0 in f0:
              P.append(lignes0.rstrip("\n").split(" ")[:2])

      Ligne 37 tu peux utiliser elif :

                      elif pathway[0]==proteine1:

      Et sinon le truc qui prend le plus de temps c'est le for ligne 61, je n'ai pas compris à quoi il sert, vu que tu n'utilise pas z (tu l'écrase dans les deux expressions génératrices)

      Tu peux juste supprimer la ligne 61 et corriger l'indentation des lignes 62 et 63.

      Ligne 66 il est inutile de tester si "chaine in mins" puisque tu boucle justement sur mins...

      Voilà, il y a certainement d'autres trucs à optimiser...


      • Partager sur Facebook
      • Partager sur Twitter
        11 juillet 2019 à 15:21:57

        Merci beaucoup thelinekioubeur pour ta réponse ! Ca va déjà me faire gagner quelques précieuses secondes ! :)

        • Partager sur Facebook
        • Partager sur Twitter
          11 juillet 2019 à 23:22:48

          Salut,

          J'ai pas trop regardé le code. Quel algorithme utilises-tu (tu peux peut-être gagner du temps là-dessus) ? Un parcours en profondeur dans le graphe des protéines devrait être l'une des meilleures solutions. Tu construis le graphe une seule fois en début de programme, et ensuite tu l'utilises.

          • Partager sur Facebook
          • Partager sur Twitter
          Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
            12 juillet 2019 à 20:30:42

            Ligne 66, chaine in mins est inutile, et se vérifie logiquement ligne 65.

            EDIT: Oups pas vu, grilled !

            -
            Edité par fred1599 12 juillet 2019 à 20:31:08

            • Partager sur Facebook
            • Partager sur Twitter

            Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
            La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

            Optimisation d'un code

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown