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 meilleure 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énombrons les structures composant l'espace de prédiction des algorithmes exacts 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 existant et la taille de 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 Lyngsø et Pedersen et des cartes planaires ainsi qu'une bijection entre la classe des pseudonoeuds indifférenciés, que nous avons introduite, et les arbres ternaires. Nous montrons alors que les différences de compléxité 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.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00788467 |
| Date | 17 December 2011 |
| Creators | Saule, Cédric |
| Publisher | Université Paris Sud - Paris XI |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds