Elaboration d'un BLAST Local

Bonjour à tous,

je suis sur un projet bio-informatique depuis quelques semaines, le but étant de blaster 82.000.000 de reads sur un megatranscriptome de 200.000 références. Jusqu'à présent, je faisais un Regex Match (on prend un read, on boucle 200.000X pour toutes les références et ainsi de suite), mais il s'avère qu'il me fait un read / secondes. Autant dire que le résultat est ridicule compte tenu de la masse d'informations à traiter.

Donc je suis en pleine réflexion pour effectuer de nouvelles approches, notamment l'implémentation d'une regex global travaillant directement sur tout le fichier (sans la perte de temps du bouclage), la gestion du multithreading ou tout simplement un nouvel algorithme d'arbre pour le match. Mais j'aimerais éviter de perdre trop de temps.

A moins que vous connaissiez une meilleur méthode, je reste ouvert à d'autres solutions.

Merci.

Euh, j'ai une certaine expérience sur les questions des performances en Perl (et dans d'autres langages), mais, n'étant pas versé dans la bio-informatique, "blaster 82 millions de reads sur un megatranscriptome de 200.000 références", je ne sais pas du tout ce que ça veut dire. Mais peut-être que si tu montres ton code et expliques ce qu'il cherche à faire, j'aurais des idées à te suggérer.

Bonsoir,

ça tombe bien, car je recherche vraiment de bonnes performances pour aboutir à des temps d'exécution acceptables.

Il me semble que tu avais participé à un autre sujet me concernant sur le forum général de Perl, c'est dans la continuité en fait. On doit prendre les 82.000.000 de micros séquences (reads) une par une, on ne conserve que les offsets ou ça match une seule fois sur chaque macros séquences du megatranscriptome. Ce n'est que de la comparaison de chaînes de caractères.

Oui, mais pour que j'ai une chance de pouvoir t'aider, il faudrait que tu montres ton code, ou du moins la partie de ton code que tu cherches à optimiser. Perso, je ne sais pas comment on détermine une micro séquence ou une macro séquence dans une chaîne d'ADN (enfin, je suppose que c'est de l'ADN dont tu parles). De même l'offset, je suppose que c'est une distance (nombre de nucléotides) par rapport à quelque chose, mais je ne sais pas par rapport à quoi (le début de la chaîne? le début d'une séquence ?).

Oublions la biologie. Si on raisonne purement informatique:

$a = "aaa";
$b = "atcaaatcgatcacfa";

ça peut matcher dès le début, en plein milieu, ou à la fin. ça n'a pas d'importance. On compte uniquement le nombre de match. Si match = 1, on conserve les offsets ou $a match sur $b, soit [3;6] dans l'exemple ci-dessus. Rien de bien compliqué en somme, mais il y a 80 millions de micro chaines de caractère à matcher sur 300.000 de macros chaines. Et la forcément, les performances ne suivent pas avec mon algo actuel. voir ici: http://pastebin.com/yXFp2qj9

as-tu essayé d'utiliser bowtie ?

Si comme l'indique ta question, tu veux faire un blast, pourquoi ne pas utiliser les outils de blast déjà existant et qui on fait l'objet d'optimisation algo? Est-ce que tu as un besoin qui n'est pas compatible avec leur fonctionnement?

Au pire il te suffira ensuite de trier/filtrer les résultat non?

Citation:

---

Si comme l'indique ta question, tu veux faire un blast, pourquoi ne pas utiliser les outils de blast déjà existant et qui on fait l'objet d'optimisation algo?

---

Je ne veux pas interroger les bases de données online. Je dois effectuer un blast strict (100%). J'ai un jeux de données de 40 Go en local et je dois effectuer le travail dessus. Donc oui, j'avais pensé utiliser des algorithmes déjà existants comme Needleman-Wunsch ou Smith-Waterman. Mais comme je suis informaticien pur spécialisé en bioinformatique depuis peu, j'ai voulu faire une implémentation personnel et j'avoue que je manque d'informations sur des solutions en local pour ce type d'application. D'où ma question initiale, dois-je aborder de nouvelles approches algorithmiques, si oui lesquelles éventuellement? ou alors avez-vous des solutions déjà implémentées, ou des outils, dont je peux m'inspirer ou utiliser?

Citation:

---

Envoyé par bowow

Je ne veux pas interroger les bases de données online. Je dois effectuer un blast strict (100%). J'ai un jeux de données de 40 Go en local et je dois effectuer le travail dessus. Donc oui, j'avais pensé utiliser des algorithmes déjà existants comme Needleman-Wunsch ou Smith-Waterman. Mais comme je suis informaticien pur spécialisé en bioinformatique depuis peu, j'ai voulu faire une implémentation personnel et j'avoue que je manque d'informations sur des solutions en local pour ce type d'application. D'où ma question initiale, dois-je aborder de nouvelles approches algorithmiques, si oui lesquelles éventuellement? ou alors avez-vous des solutions déjà implémentées, ou des outils, dont je peux m'inspirer ou utiliser?

---

Bowtie et BWA sont des aligneurs spécifiquement créés pour répondre à ce genre de besoin, aligner un très grand nombre de séquences courtes sur un large génome de référence. Ils sont optimisés et bien plus efficaces que BLAST, alors pourquoi vouloir réinventer la roue ? De plus, tu n'as pas à utiliser des bases publiques pour faire un blast ou un bowtie, il suffit d'indexer ta banque de référence (ton mégatranscriptome) pour pouvoir l'utiliser.

je suis complètement d'accord avec @gardyen, avant de te lancer dans le code, regarde ce qu'il existe car beaucoup d'outils sont déjà développés (par exemple si tu veux faire de l'assemblage génomique par toi même ça risque d'être long... et très compliqué)

Le principe d'un Blast (quelque soit l'outil utilisé) a pour principe de "matcher" des séquences souhaitées sur un base MAIS cette base peut être n'importe quel fichier contenant une série de séquences: dans l'absolu, rien n'empêcherait que les 2 fichiers soient identiques (recherche de séquence identiques...)

Même si les algorithmes déjà existants sont performants, la case "mainframe" est quasi-inévitable, vu la quantité de données à traiter? Je n'ai aucune idée de combien de temps ça pourrait me prendre.

note: autant linker la dernière version de l'outil bowtie2

Ces outils (bowtie, cufflinks, tophat, etc) ont été développés pour répondre à la problématique du séquençage nouvelle génération (donc à ton genre de problème), où l'on doit aligner de très nombreux reads sur une référence, ce sont actuellement les outils les plus rapides et optimisés dans ce domaine. Ils sont utilisés pour séquencer, ré assembler et annoter des génomes entiers.

Bowtie n'utilise pas d'algo type Needleman-Wunsch ou Smith-Waterman, mais un système d'index sur la référence, augmentant de beaucoup la vitesse d'alignement, cf FM-Index, au prix d'une petite perte de sensibilité. Mais vu que tu veux un alignement strict, ce devrait être l'outil indiqué. Maintenant si tu veux créer un nouvel outil d'alignement, bon courage !

Alors... Tu ne me sembles pas familier avec ces nouvelles technologies. Utiliser Blast n'est pas indiqué pour l'alignement des reads.. Tu risquerais d'attendre un temps certain, si ce n'est un certain temps ! De nouveaux algos ont été développés spécifiquement pour le NGS. Commence par te familiariser avec des technos en faisant un peu de biblio. Bon courage !