Agbeto, Kossi Wilfried
(2024).
« PASIgraph : un ensemble d’algorithmes de sous-isomorphisme maximal en mémoire distribuée met en évidence les variations d’empilement dans les modules structuraux généraux d’ARN » Mémoire.
Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Les structures complexes des ARN sont essentielles à leurs diverses fonctions. Alors que la structure secondaire organise de manière rigide les tiges, les conformations des boucles sont également importantes et parfois cruciales pour l’architecture globale de la molécule, comme c’est le cas avec les motifs en virage (kink-turn) et A-minor. Les boucles sont formées à partir de réseaux d’interactions de paires de bases, et de nombreux modules récurrents ont été décrits au fil des années. Mettre au jour et organiser ces modules est important pour comprendre la relation séquence-structure-fonction. La nature des molécules d’ARN en tant que réseau d’interactions conduit à leur représentation naturelle sous forme de graphe, avec des arêtes étiquetées représentant des interactions canoniques et non canoniques. Les modules peuvent être considérés comme des sous-graphes communs, des sous-isomorphismes maximaux, entre différentes structures. Trouver ces similitudes automatiquement pose un problème notoirement NP-Difficile, nécessitant d’importantes ressources computationnelles et de mémoire pour être résolu exactement. Différentes approches ont été appliquées, mais ont ignoré les empilements en raison de leur nombre et de leur fréquence élevée dans les structures. Dans ce mémoire, je présente une méthode distribuée rapide pour extraire des motifs structuraux récurrents présents dans les structures d’ARN, incluant les interactions canoniques, non-canoniques, et pour la première fois toutes les interactions d’empilement. Je fournis des algorithmes et des implémentations efficaces dans le modèle de mémoire partagée ainsi que dans le modèle de mémoire distribuée, avec différentes stratégies de planification des tâches telles que le vol de travail et le maître/ouvrier. Les résultats montrent l’efficacité de la parallélisation avec une bonne évolutivité. J’ai appliqué ma méthode sur toutes les structures d’ARN non-redondantes deux à deux pour trouver tous les modules structurels dans deux contextes : (1) motifs de boucles locaux en ne comparant que des boucles multiples, des boucles intérieures, des renflements et des épingles à cheveux, et (2) motifs globaux où un ensemble de structures entières d’ARN ont été comparé entre elles. L’ensemble de données local contient 16 431 structures d’ARN, j’ai trouvé 631 RINs pour un total de 182 646 occurrences. Et l’ensemble de données global contient 1 722 structures d’ARN, j’ai trouvé 157 344 RINs pour un total de 209 750 474 occurrences. Ces résultats n’étaient pas réalisables avec les travaux précédents, même avec 4 To de mémoire, alors que ma méthode n’a pris que 186 Go de mémoire. Ma méthode a été implémentée dans un solveur appelé PASIgraph en utilisant le langage de programmation C. J’ai utilisé OpenMP (mémoire partagée) et MPI (mémoire distribuée) pour la parallélisation. Le code source de PASIgraph est accessible via le lien suivant : https://gitlab.info.uqam.ca/agbeto.kossi_wilfried/isomorphisme_graphe
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Reinharz, Vladimir |
| Mots-clés ou Sujets: |
Structure de l'ARN / Motifs structuraux d’ARN / Réseaux d’interaction récurrents / RIN / Théorie des graphes / Algorithmes / Programmation parallèle |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
20 nov. 2024 11:20 |
| Dernière modification: |
20 nov. 2024 11:20 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/18247 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
