Recherche de motifs probabilistes : le cas des Matrices Poids Position dinucléotidiques (di-PWM) - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2021

Algorithms for probabilistic motif search: the case of dinucleotidic Position Weight Matrices (di-PWM)

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

Marie Mille
  • Function : Author
  • PersonId : 1117720

Abstract

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.
Fichier principal
Vignette du fichier
Mille_Marie_Rapport_Stage_M1_hal.pdf (1.78 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03326344 , version 1 (25-08-2021)

Identifiers

  • HAL Id : lirmm-03326344 , version 1

Cite

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⟩
175 View
136 Download

Share

Gmail Mastodon Facebook X LinkedIn More