Modélisation de séquences génomiques, génération aléatoire et applications

Informations générales
Nom
Ponty
Prénom
Yann
Diplôme
Thèse
Année
2006
Détails de la thèse/HDR
Université
Jury
Philippe Flajolet
Eric Rivals
Geoffroy Beauquier
Daniel Gautheret
Markus Nebel
Jacques Nicolas
Directeur (pour les thèses)
Alain Denise
Résumé en français
La mise en évidence des mécanismes de sélection agissant sur les données génomiques structurées (ARN, Protéines, ADN…) nécessite l’élaboration de modèles de séquences. Une fois un tel modèle élaboré, il est possible, au prix d’une analyse mathématique parfois complexe ou par le biais de la génération aléatoire, d’évaluer la significativité d’un phénomène observé.
 
Tout d’abord, nous nous intéressons aux propriétés des grammaires pondérées, un formalisme particulièrement adapté à la modélisation de la structure des ARN, dérivant des algorithmes de génération aléatoire efficaces implémentés au sein du prototype GenRGenS. Nous abordons le calcul automatique des pondérations réalisant des valeurs observées pour les paramètres du modèle, ainsi qu’une implémentation basée sur une approche optimisation.
 
Dans un second temps, nous abordons la modélisation de la structure secondaire d’ARN. Après quelques rappels de biologie moléculaire, nous proposons plusieurs modèles basés sur des grammaires pondérées permettant la génération de structures d’ARN réalistes. L’utilisation d’un algorithme d’optimisation permet le calculer des pondérations correspondant à certaines familles d’ARN. Nous proposons enfin un algorithme d’extraction de structure secondaire maximale dans une structure générale, qui permet de profiter des données récentes issues de la cristallographie.
 
Le dernier chapitre de cette thèse s’intéresse à l’analyse d’un algorithme de recherche de similarité heuristique, dont la sensibilité s’avère étroitement liée à la probabilité de présence d’un motif au sein de marches aléatoires particulières, les chemins culminants. Ces marches restent positives, et atteignent une altitude maximale en leur dernier pas. Nous proposons un algorithme récursif de génération aléatoire pour ces chemins. En combinant des techniques issues de la combinatoire énumérative, l’analyse asymptotique et la théorie des langages, nous dérivons des algorithmes de génération aléatoire par rejets linéaires dans de nombreux cas.