Skip to Main content Skip to Navigation
Reports

Recherche de motifs probabilistes : le cas des Matrices Poids Position dinucléotidiques (di-PWM) : Rappport de stage de Master 1

Marie Mille 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Chaque facteur de transcription se lie à diverses séquences d'ADN ressemblantes, mais pas identiques, entre elles. Cet ensemble de séquences cibles peut être représenté par un motif probabiliste tel qu'une Matrice Poids Position (Position Weight Matrix en anglais -- PWM). Une PWM comporte un nombre de colonnes égal à la longueur des motifs identifiés par des méthodes expérimentales, et un nombre de lignes égal à 4 (pour A, T, G ou C). Chaque colonne stocke la probabilité d'apparition de chacun des 4 nucléotides possibles pour chaque position des séquences cibles. Dans une PWM, les colonnes sont indépendantes les unes des autres : ce modèle ne peut transcrire entre positions voisines. Pour dépasser cette limitation, Kulakovskiy et al. ont proposé les dinucleotidic PWM, où chaque colonne stocke la probabilité de tous les di-nucléotides possibles (AA, AC, AG, etc.). Dans ce travail de Master, nous proposons différents algorithmes génériques pour rechercher les occurrences de di-PWM dans un texte qui représente une longue séquence d'ADN ou d'ARN. En particulier, nous proposons des accélérations pour une stratégie dite de fenêtre glissante, où l'on scanne le texte afin de trouver une fenêtre dont le score selon la matrice est supérieur à un seuil donnée. Ensuite, nous exhibons un algorithme en deux étapes : d'abord, l'énumération des mots valides (mots dont le score et suffisant) avec une approche par séparation et évaluation, puis la recherche simultanée et exacte de ces mots valides dans le texte. Nous comparons nos implémentations de ces algorithmes entre elles et montrons qu'elles sont utilisables en pratique. En particulier, l'algorithme par énumération s'avère rapidement le plus efficace, même en comparaison à un outil existant, puisque sa complexité est proportionnelle aux nombre d'occurrences produit en sortie. Les fonctions de recherche de di-PWM sont implantées dans un module en langage Python, d'installation et d'utilisation faciles, qui sera prochainement mis à disposition de la communauté sous licence libre.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03326344
Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Wednesday, August 25, 2021 - 6:58:19 PM
Last modification on : Friday, October 22, 2021 - 3:07:28 PM
Long-term archiving on: : Friday, November 26, 2021 - 8:08:29 PM

File

Mille_Marie_Rapport_Stage_M1_h...
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-03326344, version 1

Collections

Citation

Marie Mille. Recherche de motifs probabilistes : le cas des Matrices Poids Position dinucléotidiques (di-PWM) : Rappport de stage de Master 1. [Rapport de recherche] Université de Montpellier. 2021. ⟨lirmm-03326344⟩

Share

Metrics

Record views

29

Files downloads

14