L'exécution est trop longue pour l'inclinaison GC

Question

Je travaille actuellement sur un script qui analyse les différences de biais. Malheureusement, mon problème est que lorsque la longueur de la chaîne augmente, le temps d'exécution devient trop long et je n'arrive pas à calculer ma réponse.

def SkewGC(file): 
    countG = 0 
    countC = 0 
    diffGtoC = "" 
    # first, we need to find number of G's. 
    # the idea is, if G appears, we add it to the count. 
    # We'll just do the same to each one. 
    for pos in range(0,len(file)): 
     if file[pos] == "G": 
      countG = countG+1 
     if file[pos] == "C": 
      countC = countC+1 
     diffGtoC = diffGtoC + str(countG-countC) + "," 
    return diffGtoC.split(",") 

SkewGCArray = SkewGC(data) 
# This because I included extra "," at the end... 
SkewGCArray = [int(i) for i in SkewGCArray[:len(SkewGCArray)-1]] 

def min_locator(file): 
    min_indices = "" 
    for pos in range(0,len(file)): 
     if file[pos] == min(file): 
      min_indices = min_indices + str(pos) + " " 
    return min_indices 

print min_locator(SkewGCArray) 

Essentiellement, ce script calcule le nombre de G et C (correspond aux nucléotides dans l'ADN), obtient des différences à chaque position, et je suis en train de trouver les indices de minimum. Cela fonctionne bien pour la longueur de fichier basse (c'est la chaîne d'entrée) mais quand la longueur devient grande - même comme 90000+, alors mon manuscrit court mais ne peut pas résoudre une réponse dans le temps raisonnable (~ 4-5 min).

Quelqu'un peut-il me montrer ce que je pourrais faire pour le rendre plus rapide? J'ai réfléchi à la question de savoir s'il vaut mieux dire, obtenir la différence (diffGtoC), mettre cela au minimum, puis recalculer chaque différence jusqu'à ce qu'elle voit quelque chose de différent pendant lequel je remplace aussi la valeur minimum.

Mais le souci que j'avais avec cette approche est de trouver et de retenir les indices de minimum. Si je dis, avait un tableau avec des valeurs:

[-4, -2, -5, -6, -5, -6]

Je peux voir comment changer la valeur minimale (-4 - 5 puis à -6) sera plus rapide en termes d'exécution de l'algorithme mais comment serai-je capable de maintenir la position de -6? Je ne sais pas si cela est tout à fait logique.

Answer 1

Plusieurs suggestions pour améliorer les performances de votre code:

diffGtoC = diffGtoC + str(countG-countC) + "," 
    return diffGtoC.split(",") 

est équivalent à:

diffGtoC = list() 
diffGtoC.append(countG - countC) 

cordes sont immuables en Python, de sorte que vous générez une nouvelle chaîne pour chaque position n'est pas très efficace. L'utilisation d'une liste vous permettra également d'économiser les conversions str et int que vous effectuez et la troncature de votre liste. Vous pouvez également utiliser pop() pour supprimer le dernier élément de votre liste au lieu d'en générer un nouveau.

Une alternative très simple serait de rechercher le minimum et de ne stocker que la valeur minimale et sa position. Puis recommencez à partir de la position minimum et voyez si vous pouvez retrouver le minimum et si oui, l'ajouter à la première position minimum. Moins de manipulation de données qui économise du temps et de la mémoire.