Re: [Denovoassembler-devel] RE : RAY

[Sébastien B. <seb...@ul...>]

Combien de séquences as-tu ?


On 27/05/13 01:58 PM, Carl Poirier wrote:
> Bonjour Sébastien,
>
> J'ai une petite question concernant les ressources.
>
> Si on roule un gros problème d'assemblage sur un trop petit nombre de noeuds du super-calculateur (pas assez de RAM pour charger tous les reads, le graph et autres), nous croyons que le programme ne fait que planter. Sommes-nous justes?
>
> Merci,
>
> Carl
> ________________________________________
> De : Carl Poirier
> Date d'envoi : 24 mai 2013 14:12
> À : Sébastien Boisvert
> Cc : Cyril Marpaud; Jacques Corbeil; François Laviolette; den...@li...
> Objet : RE : RAY
>
> Bonjour Sébastien,
>
> Merci pour les clarifications. C'est très apprécié.
>
> Nous devrions commencer quelques expérimentations dès la semaine prochaine. Nous vous tiendrons au courant des développements.
>
> Carl Poirier
> ________________________________________
> De : Sébastien Boisvert [seb...@ul...]
> Date d'envoi : 23 mai 2013 11:30
> À : Marpaud@Gmail
> Cc : Carl Poirier; Cyril Marpaud; Jacques Corbeil; François Laviolette; den...@li...
> Objet : Re: RAY
>
> (J'ai mis en C.C. Jacques Corbeil et  François Laviolette pour les laisser savoir
> que je mets du temps sur ce projet.)
>
> On 21/05/13 04:27 PM, Marpaud@Gmail wrote:
>> Rebonjour,
>>
>> j'ai joint à ce mail un .txt produit par Carl Poirier (l'étudiant en maîtrise qui m'a rejoint sur le projet) et moi-même. Puis-je vous demander d'y jeter un coup d'œil pour :
>>
>>    * confirmer que notre analyse est correcte
>>    * clarifier certains points
>>
>> si vous en avez le temps ? Les points à clarifier sont signalés dans le fichier par la présence de la chaine "=> ?".
>>
>> Encore une fois, merci !
>>
>> --
>> Cyril MARPAUD
>> Étudiant ingénieur à l'ENSICAEN
>> 3ème année électronique et physique appliquée
>> Signal, Automatique et Télécoms pour l'Embarqué
>> Ligne fixe : 418 656-7777 poste 1-7839
>> @ : cma...@gm...
>
>
> Reviewer: Sébastien Boisvert
> File: descriptionAlgorithme.txt
>
> Patch applies cleanly:
> [ ] Yes
> [ ] No
> [x] Not applicable
>
> The code works:
> [ ] Yes
> [ ] No
> [x] Not applicable
>
> Major concerns:
>
> Code Review:
>
>> * : les noms de plugins précédés d'une étoile sont ceux dont les master modes sont situés dans le fichier MachineHelper.cpp
>
> Dans le meilleur des mondes, ces adapteurs devraient être migrés dans d'autres plugins.
>
>>
>> Partitioner
>> Il s'agit de compter le nombre d'entrées dans les fichiers fournis au séquenceur.
>
> fournis à l'assembleur, pas au séquenceur.
>
>> Chaque esclave a un certain nombre de fichiers à compter.
>
> Exactement ! Ça comprend aussi le rang 0.
>
>>
>> Les fichiers peuvent être de 3 formats différents:
>> -SFF: Voir ray-master/code/SequencesLoader/SffLoader.cpp
>> -FASTA: Voir ray-master/code/SequencesLoader/FastaLoader.cpp
>> -FASTQ: Voir ray-master/code/SequencesLoader/FastqLoader.cpp
>>
>
> Il y a beaucoup plus de formats:
>
>        .fasta
>        .fa
>        .fasta.gz (needs HAVE_LIBZ=y at compilation)
>        .fa.gz (needs HAVE_LIBZ=y at compilation)
>        .fasta.bz2 (needs HAVE_LIBBZ2=y at compilation)
>        .fa.bz2 (needs HAVE_LIBBZ2=y at compilation)
>        .fastq
>        .fq
>        .fastq.gz (needs HAVE_LIBZ=y at compilation)
>        .fq.gz (needs HAVE_LIBZ=y at compilation)
>        .fastq.bz2 (needs HAVE_LIBBZ2=y at compilation)
>        .fq.bz2 (needs HAVE_LIBBZ2=y at compilation)
>        export.txt
>        qseq.txt
>        .sff (paired reads must be extracted manually)
>        .csfasta (color-space reads)
>        .csfa (color-space reads)
>
>
> Si votre est en C++, vous pouvez utiliser directement les classes de Ray.
>
> Sinon, je vous suggère de gérer initialement le fastq et le fastq.gz.
>
>> *SequencesLoader
>> Charger en mémoire les reads. Le maître calcule le partitionnement des reads, puis chaque esclave charge sa partie en mémoire, dans machine::ArrayOfReads.
>
> Oui.
>
> Il y a une partition sur les fichiers et une partitions sur les rangs. La première est envopyer à tout le monde et la seconde est calculée avec la
> première.
>
>>
>> *KmerAcademyBuilder
>> Chaque esclave compte le nombre de k-mers dans ses reads et l'envoie.
>
> Ce module calcul les sommets du graphe et utilise un filtre de Bloom.
>
>>
>> *CoverageGatherer
>> Les slaves envoient la distribution de la couverture, soit le nombre de k-mers ayant la couverture donnée.
>>
>
> oui
>
>> *VerticesExtractor
>> RAY_MASTER_MODE_SEND_COVERAGE_VALUES
>> - Le maître envoie à tous les esclaves les valeurs maximales, minimales et de répétition de la couverture.
>> RAY_SLAVE_MODE_ADD_EDGES
>> - Les esclaves fabriquent des edges. Lorsqu'ils en ont amassé un certain nombre, ils les envoient. Pour trouver un edge, ils commencent par décoder la séquence ADN d'un read. Si un k-mer a un sommet précédent, il envoie le edge au bon rank à l'aide du BufferedData. Sinon, il renverse le k-mer et refait la même vérification. Si n'en a toujours pas un, il passe au prochain k-mer, qui aura comme sommet précédent ce dernier.
>> -ligne 148 de VerticesExtractor.cpp: comment un DNA pourrait ne pas être valide, ça provient de codeToChar() qui retourne que les bons chars => ?
>
> Un ADN invalide contient autre chose que des A, T, C, G. En pratique, ça n'arrive pas je crois car
> il y a du code ailleur qui gère ça.
>
>>
>> *EdgePurger
>> RAY_MASTER_MODE_PURGE_NULL_EDGES
>> - passage en mode DO_NOTHING
>> - Avertit les autres de passer à cette étape via le message RAY_MPI_TAG_PURGE_NULL_EDGES
>> RAY_SLAVE_MODE_PURGE_NULL_EDGES
>> -EdgePurger est un TaskCreator. Chaque worker demande aux autres la couverture d'un certain sommet. Si la couverture est nulle, il élimine le sommet.
>> -ligne 49 de EdgePurgeWorker.cpp: Pourquoi vérifie-t-on seulement la première réponse et pas les suivantes => ?
>
> Parce que le message est démultiplexé déjà avant par le VirtualCommunicator (demande faite par le VirtualProcessor qui a réveillé
> le Worker.)
>
>>
>> MachineHelper.cpp
>> RAY_MASTER_MODE_WRITE_KMERS
>> - Chaque esclave ecrit dans le fichier kmers.txt les k-mers ainsi que leur couverture. Ils envoient aussi la distribution des edges. Il s'agit du nombre de k-mers avec un nombre de parents
>> et un nombre d'enfants donnés.
>
>
> (actif avec -write-kmers).
>
>> C'est le master qui écrira ceci dans le fichier degreeDistribution.txt.
>>
>> *SequencesIndexer
>> Chaque worker commence par demander la couverture des vertex. Il sélectionne ensuite un vertex qui n'est pas une erreur selon la couverture maximale et minimale. Il envoie ce vertex ainsi que sa position dans le read. Il fait pareil pour son inverse. Selon les options, il peut aussi écrire dans un fichier des marqueurs décrivant les reads, soit leur position, leur coverage et autres.
>
> Exactement.
>
> Initialement, le code choisissait toujours index=0, mais ça donne de meilleurs résultats avec cet algorithme.
>
>>
>> *SeedingData
>> RAY_MASTER_MODE_PREPARE_SEEDING
>> - mise à jour de deux attributs
>> - closeMasterMode()
>> RAY_MASTER_MODE_TRIGGER_SEEDING
>> - envoi d'un message (RAY_MPI_TAG_START_SEEDING) à tous les ranks
>> RAY_SLAVE_MODE_START_SEEDING
>> - génération des seeds dans SeedWorker.cpp
>> RAY_SLAVE_MODE_SEND_SEED_LENGTHS
>> - envoi du message RAY_MPI_TAG_IS_DONE_SENDING_SEED_LENGTHS au rank 0
>> - passage en mode DO_NOTHING
>>
>> SpuriousSeedAnnihilator
>> RAY_MASTER_MODE_REGISTER_SEEDS & RAY_MASTER_MODE_FILTER_SEEDS & RAY_MASTER_MODE_CLEAN_SEEDS & RAY_MASTER_MODE_PUSH_SEED_LENGTHS
>> - distribution non démarrée -> openMasterMode
>> - distribution terminée -> closeMasterMode
>> RAY_SLAVE_MODE_REGISTER_SEEDS
>> - si skip ou checkPoint déjà atteit -> return
>> - => ?
>> RAY_SLAVE_MODE_FILTER_SEEDS
>> - si checkPoint ou skip -> closeSlaveModeLocally()
>> - sinon TaskCreator.mainLoop() (cf FusionTaskCreator l.117)
>> RAY_SLAVE_MODE_CLEAN_SEEDS
>> - si checkPoint ou skip -> closeSeModeLocally()
>> - désallocation de pointeurs devenus inutiles après l'étape d'extension des seeds
>> RAY_SLAVE_MODE_PUSH_SEED_LENGTHS
>> - récupération de "length" et "count" (deux attributs relatifs aux seeds obtenus grâce à un itérateur sur map<int,int>)
>> - envoi de ces données au rank 0 via un message
>>
>> *Library
>> RAY_MASTER_MODE_TRIGGER_DETECTION
>> - envoi d'un message (RAY_MPI_TAG_AUTOMATIC_DISTANCE_DETECTION) à tous les ranks
>> - passage en mode DO_NOTHING
>> RAY_SLAVE_MODE_AUTOMATIC_DISTANCE_DETECTION
>> - Si on a des paired reads, on termine tout de suite en envoyant MASTER_RANK,RAY_MPI_TAG_AUTOMATIC_DISTANCE_DETECTION_IS_DONE
>> - Gestion du bug sur Guillimin
>
> Ce code est en commentaire et donc inactif. Le bug était dans Ray, pas causé par guillimin. Le bug arrivait seulement
> sur guillimin.clumeq.ca par contre.
>
>> - Les workers travaillent pour trouver les distances externes moyennes:
>> - Cela commence par les données des seeds dans lesquelles ils prennent un vertex.
>> - Ils obtiennent les reads à partir du vertex.
>> - Pour chacun de ces reads:
>> - Ils trouvent l'autre lecture qui forme les paires de nucleotides en faisant une demande (RAY_MPI_TAG_GET_READ_MATE)
>> - La distance = position read - position autre read + longueur read + position strand gauche - position strand droit
>> - Finalement, la quantité d'une telle distance est incrementée.
>> RAY_MASTER_MODE_ASK_DISTANCES
>> - envoi d'un message (RAY_MPI_TAG_ASK_LIBRARY_DISTANCES) à tous les ranks
>> RAY_SLAVE_MODE_SEND_LIBRARY_DISTANCES
>> - envoi au master la quantité de chaque distance pour chaque librairie
>> RAY_MASTER_MODE_START_UPDATING_DISTANCES
>> - Calcule les nouvelles distances moyennes à partir des résultats des slaves
>> RAY_MASTER_MODE_UPDATE_DISTANCES
>> - Envoi des résultats à tous les ranks
>>
>> SeedExtender
>> RAY_MASTER_MODE_TRIGGER_EXTENSIONS
>> - envoi d'un message (RAY_MPI_TAG_ASK_EXTENSION) à tous les ranks
>> - passage en mode DO_NOTHING
>> RAY_SLAVE_MODE_EXTENSION
>> - vérifier checkPoint, si passé ("extensions")
>> - passage en mode DO_NOTHING
>> - message au rank 0 (RAY_MPI_TAG_EXTENSION_IS_DONE)
>> - si tous les seeds ont été gérés ou 0 seeds -> finalize()
>> - si initialisation pas faite -> initialize()
>> - si le vertex en cours (ou son revcomp) est déjà assemblé, on passe au seed suivant
>> - sinon on le marque comme étant assemblé
>> - on "énumère les choix" puis on "fait un choix" => ?
>
> Ce code contient les heuristiques et la traversée du graphe.
>
>>
>> *FusionData
>> RAY_MASTER_MODE_TRIGGER_FUSIONS
>> - m_cycleNumber = 0;
>> - closeMasterMode()
>> RAY_MASTER_MODE_TRIGGER_FIRST_FUSIONS
>> - (*m_reductionOccured)=true;
>> - closeMasterMode()
>> RAY_MASTER_MODE_START_FUSION_CYCLE
>> - si cycle non démarré : envoi d'un message (RAY_MPI_TAG_CLEAR_DIRECTIONS) à tous les ranks
>> - plusieurs cycles contenant les étapes suivantes :
>> 1 : envoi de RAY_MPI_TAG_DISTRIBUTE_FUSIONS
>> 2 : envoi de RAY_MPI_TAG_FINISH_FUSIONS
>> 3 : envoi de RAY_MPI_TAG_CLEAR_DIRECTIONS
>> 4 : envoi de RAY_MPI_TAG_DISTRIBUTE_FUSIONS
>> 5 : envoi de RAY_MPI_TAG_START_FUSION
>> 6 : reinitialisation pour cycle suivant => ?
>> RAY_SLAVE_MODE_DISTRIBUTE_FUSIONS
>>
>> FusionTaskCreator
>> RAY_SLAVE_MODE_FUSION
>> - TaskCreator -> mainLoop()
>> - initialisation()
>> - si il reste des tâches non assignées -> création de workers & assignation tâche
>> - si plus de tâche non assignée -> noMoreTasksAreComing()
>> - on fait "travailler" un worker, on récupère le résultat de son calcul puis on le détruit
>> - si tâches assignées accomplies & plus de tâche à assigner -> finalize()
>>
>> JoinerTaskCreator
>> RAY_SLAVE_MODE_FINISH_FUSIONS
>> - TaskCreator -> mainLoop() (cf RAY_SLAVE_MODE_FUSION)
>>
>> PathEvaluator
>> (évaluation de la qualité d'un chemin)
>> RAY_MASTER_MODE_EVALUATE_PATHS
>> - openMasterMode() (boucle sur openSlaveMode(), une itération pour chaque rank)
>> - si tous les ranks ont terminé -> closeMasterMode()
>> RAY_SLAVE_MODE_EVALUATE_PATHS
>> - writeCheckpointForContigPaths()
>> - écriture du nombre total de contigs (m_contig.size()) dans le fichier checkpoint ContigPaths
>> - pour chaque contig, écriture dans ce fichier checkpoint de :
>> - "nom" du contig
>> - nombre de K-mers
>> - k-mers
>> - closeSlaveModeLocally() (envoi d'un message (RAY_MPI_TAG_SWITCHMAN_COMPLETION_SIGNAL) au rank 0)
>>
>> MachineHelper.cpp
>> RAY_MASTER_MODE_ASK_EXTENSIONS
>> (demande aux ranks d'envoyer leurs extensions)
>> - étape 1 :
>> - initialisations
>> - envoi d'un message (RAY_MPI_TAG_COMPUTE_REQUIRED_SPACE_FOR_EXTENSIONS) à tous les ranks
>> - étape 2 (quand tous les ranks ont terminé d'écrire leurs contigs) :
>> - si RAY configuré pour utiliser AMOS -> setMasterMode(RAY_MASTER_MODE_AMOS);
>> - sinon -> closeMasterMode();
>> RAY_SLAVE_MODE_SEND_EXTENSION_DATA
>> - si autorisation (rank 0 ou message RAY_MPI_TAG_SEND_AUTHORIZATION reçu) -> pour que deux ranks ne tentent pas d'écrire dans le fichier en même temps
>> - ouverture fichier
>> - écriture de tous les contigs pour le rank en cours
>> - fermeture fichier
>> - passage en mode DO_NOTHING
>> - envoi d'un message (RAY_MPI_TAG_EXTENSION_DATA_END) au rank 0
>> - envoi d'un message (RAY_MPI_TAG_SEND_AUTHORIZATION) au rank suivant
>>
>> *Scaffolder
>> RAY_MASTER_MODE_SCAFFOLDER
>> - envoi d'un message (RAY_MPI_TAG_START_SCAFFOLDER) à tous les ranks
>> - passage en mode DO_NOTHING
>> RAY_SLAVE_MODE_SCAFFOLDER
>> - initialisations
>> - tant que tous les contigs n'ont pas été gérés -> processContig();
>> - envoi d'un message (RAY_MPI_TAG_I_FINISHED_SCAFFOLDING) au rank 0
>> - passage en mode DO_NOTHING
>> RAY_MASTER_MODE_WRITE_SCAFFOLDS
>> - initialisations (ouverture d'un fichier)
>> - tant qu'on a pas géré tous les scaffolds :
>> - tant qu'on a pas géré tous les contigs du scaffold en cours :
>> - getContigSequence();
>> - ecriture des scaffolds dans le fichier
>> - closeMasterMode();
>
>
> Pour votre premier milestone, vous pouvez probablement commencer par le support fastq seulement.
>
>
> Je pense que la partie de construction du graphe se fait sur un GPU ou sur un FPGA. Le reste, je ne suis pas certain du gain.
>
>
> Voir:
>
> Efficient Graph Based Assembly of Short-Read Sequences on Hybrid Core Architecture
> http://www.osti.gov/bridge/servlets/purl/1015333-q62bUB/1015333.pdf
> http://www.conveycomputer.com/files/2313/5095/9539/ConveyGraphConstructor_5172011.pdf
>