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

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...

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

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.

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