réflexion sur python

Version imprimable

04/12/2009, 22h38
samplaid

réflexion sur python

Bonjour,

J'utilise python pour trouver à partir d'une séquence de départ A contenant plus de 5 000 000 de nucléotides (c'est-à-dire 5 000 000 de lettres qui sont soit A, C, G, T) les sous-régions unique possédant une taille minimum de 20, le tout par rapport à une séquence B de plus ou moins la même taille.

Pour cela, je créé une hashmap<clé, valeur> ayant comme clés toutes les sous-séquences de taille 20 que j'ai dans ma séquence A et comme valeur les positions ou elles ont été trouvée. Ensuite je supprime les doublons par rapport à B.

Pour avoir les régions, il me faut rassembler toutes les valeurs consécutives.
Exemple d'entrées dans ma hashmap:
<"AAAAAAAAAAAAAAAAAAAA", [1555, 18474]>
...
<"CAAAAAAAAAAAAAAAAAAA", [1554]>
...
<"AAAAAAAAAAAAAAAAAAAG", [1556]>
=> on sait que l'on a une region qui est CAAAAAAAAAAAAAAAAAAAAG

Étant donné que je travaille avec de grande quantité de données, les performances peuvent facilement chuter...

Par exemple, au départ j'étais parti sur une idée ou les entrées de ma hashtable auraient comme clé la sous-séquence de taille 20 et comme valeur un vecteur de positions.
<"AAAAAAAAAAAAAAAAAAAA", [1555, 18474]>

Constation, j'ai du remplacer le vecteur de positions par une chaine de caractères:
<"AAAAAAAAAAAAAAAAAAAA", "1555_18474">
Ainsi je passe de + de 300 sec à 7sec!
(pour récupérer les position je split sur "_")

Une autre anomalie que j'ai constaté est que lorsque je veux trier un vecteur de + 3 000 000 d'entrées, je mets plus de 350sec (avec un comparateur que j'ai implémenté : mon_array.sort(monComparateur)).
Comme solution, il est plus rapide de construire une nouvelle hashmap avec 3 000 000 entrées où les clés représentent les indices. Ensuite on incrémente un indice jusque 3 000 000 en testant si la clé existe dans la hashmap. Ainsi je passe à 19sec.

Que pouvez-vous me dire de ces 2 problèmes rencontrés?

Merci
05/12/2009, 14h29
Rozebud
déja, pour chercher dans un dictionnaire(qui un hash map en python) il est totalement inutile d'itérer sur les clés. C'est le principe même des hash tables de ne pas avoir à itérer.

Il existe un Python une methode vraiment bien des dictionnaires:
dict.get(key,default)
qui retourne la valeur de key si key existe dans le dictionnaire(dict[key]), et default si key n'est pas une clé du dictionnaire, et ce (corrigez moi si je me trompe) en temps constant.
Donc si ton dictionnaire s'appelle data:
Code:

1 2 3 value = data.get("AAA...CGT",None) if value: #sous entendu !=None #utilisation de celle ci...
Pour ton deuxième, en fait ton premier problème, je ne suis pas sur de comprendre pourquoi il y a une si grande variation de performance, peut tu nous montrer du code?
13/12/2009, 16h18
N.tox

Citation:

Pour avoir les régions, il me faut rassembler toutes les valeurs consécutives.
Exemple d'entrées dans ma hashmap:
<"AAAAAAAAAAAAAAAAAAAA", [1555, 18474]>
...
<"CAAAAAAAAAAAAAAAAAAA", [1554]>
...
<"AAAAAAAAAAAAAAAAAAAG", [1556]>
=> on sait que l'on a une region qui est CAAAAAAAAAAAAAAAAAAAAG

Je ne connais pas l'impact sur les performances, et je ne connais strictement rien à l'ADN, mais ne serait-il pas plus simple de d'avoir directement un dico avec les bonnes régions ? style :

Citation:

<"AAAAAAAAAAAAAAAAAAAA", ( (1555,20), (18474,20) )>
...
<"CAAAAAAAAAAAAAAAAAAAAG",( (1554, 22) )>

ou même carrément remplir en live une bdd style bsddb qui permet un classement "record" (les clé seront simplement empilée (pas de tri)), ce qui permetterait une plus grande mémoire vive disponible.