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

Doctorat
Equipe : Bioinformatique

Modèles combinatoires des structures d’ARN avec ou sans pseudonoeuds, application à la comparaison de structures.

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

Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay

Lieu de déroulement : LRI

Soutenue le 17/12/2010 devant le jury composé de :
Julien Allali, maître de conférence, Université Bordeaux I
Alain Denise, professeur, Université Paris-Sud XI
Serge Dulucq, professeur, Université Bordeaux I
Christine Gaspin, directrice de recherche, INRA Toulouse
Christine Paulin, professeur, Université Paris-Sud XI
Jérôme Waldispühll, Assistant profesor, McGill University

Activités de recherche :

Résumé :
Ces travaux de thèse proposent une modélisation des structures
secondaires d'ARN avec ou sans pseudonoeuds. Selon une approche
combinatoire, nous concevons différents modèles de ces structures
que nous étudions sous deux aspects. D'une part, nous définissons
des modèles de génération aléatoire qui nous permettent de définir
une mesure permettant une meilleur reconnaissance des structures
biologiques. D'autre part, grâce à des codages appropriés et
des bijections vers des langages représentés par des grammaires
non-contextuelles, nous démombrons les structures composant l'espace
de prédiction des algorithmes exact de prédiction de structures
secondaires avec pseudonoeuds.

La première partie concerne des modèles aléatoires de structures d'ARN
sans pseudonoeuds. Nous montrons que ces structures aléatoires constituent
une source de bruit pertinente lorsqu'il s'agit de déterminer si les
logiciels de comparaison de structures attribuent un meilleur score à des
comparaisons entre structures issues de la même famille d'ARN qu'à des
alignements entre structures réelles et aléatoires. Nous comparons
ensuite la sensibilité et la spécificité de RNAdistance, un programme de
comparaison de structures, selon l'usage du score "brut" ou bien de la
Z-valeur de ce score. Nous calculons plusieurs Z-valeurs selon différents
modèles de structures aléatoires. Nous montrons que la Z-valeur calculée
à partir d'un modèle de Markov améliore la détection des ARN de grande
taille tandis que la Z-valeur calculée à partir d'un modèle basé sur des
grammaires pondérées améliore la détection des ARN de petite taille.

Nous nous intéressons ensuite, dans une deuxième partie, aux algorithmes
de prédiction de structure secondaire avec pseudonoeuds. Nous complétons
tout d'abord la classification de Condon et al en décrivant les structures
par leur graphe de cohérence et nous caractérisons également la restriction
planaire de la classe de Rivas et Eddy. Nous étudions ensuite le compromis
entre complexité des algorithmes existants et leur espace de prédiction.
Nous dénombrons les structures en les codant par des mots de
langages algébriques. Nous en déduisons alors des formules asymptotiques
de dénombrement. Nous mettons aussi en évidence une bijection entre la
classe de Lyngso et Pedersen et des cartes planaires ainsi qu'une
bijection entre la classe des pseudonoeuds indifférenciés, que nous avons
introduit, et les arbres ternaires. Nous montrons alors que les
différences de complexité observées des algorithmes de prédiction ne sont
pas toujours justifiées par la taille de l'espace de prédiction. A partir
de ces grammaires, nous concevons des algorithmes efficaces de génération
aléatoire, uniforme ou non uniforme contrôlée, de structures d'ARN avec
pseudonoeuds.