Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de

Doctorat
Equipe : Bioinformatique

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

Début le 01/10/2003
Direction : DENISE, Alain

Ecole doctorale : ED IPS 427
Etablissement d'inscription : Université Paris-Saclay

Lieu de déroulement : Orsay

Soutenue le 29/11/2006 devant le jury composé de :
DENISE Alain BEAUQUIER Joffroy, DENISE Alain, FLAJOLET Philippe, GAUTHERET Daniel, NEBEL Markus, NICOLAS Jacques, RIVALS Eric

Activités de recherche :

Résumé :
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 rejet linéaires
dans de nombreux cas.