Les ARN et la bio-informatique de l’ARN

Les ARN et la bio-informatique de l’ARN 

Le premier chapitre (introduction mise à part) du mémoire est consacré aux ARN non-codants. Après une rapide description des molécules d’ARN, nous présenterons leur modélisation classique en bio-informatique. En conséquence de cette modélisation, nous commencerons à entrevoir pourquoi les différentes problématiques associées aux ARN sont très proches de problématiques de graphes. Nous détaillerons ensuite deux des problèmes principaux de la bio informatique des ARN : la recherche d’ARN non-codant et la prédiction de structure, en listant les principales approches tentant de les résoudre.

L’alignement structure-séquence en détail 

Nous focaliserons ensuite notre attention sur l’une de ces approches : l’alignement structure-séquence d’ARN. Le problème d’alignement structure-séquence consiste comme son nom l’indique à aligner une structure connue d’un premier ARN (nous verrons plus tard ce que nous entendons par “structure”) avec la séquence d’un deuxième ARN. Pour résoudre ce problème, nous cherchons à optimiser l’alignement selon une fonction de coût. C’est donc un problème d’optimisation, qui malheureusement se révèle NP-Difficile (en général). En conséquence différents travaux définissent des classes d’instances réduites pour lesquelles ils proposent des algorithmes à complexités polynomiales.  Après l’introduction de notions qui seront reprises tout au long du mémoire, nous aborderons l’état de l’art du problème par une présentation générale de la programmation dynamique, qui est au cœur de toutes les méthodes que nous décrirons, et nous l’illustrerons par le célèbre algorithme de Smith et Waterman. Puis nous détaillerons les deux algorithmes principaux d’alignement structure-séquence : l’algorithme de Jiang et l’algorithme de Han. Enfin, mais de façon moins détaillée, nous présenterons les algorithmes de Wong, clôturant ainsi l’état de l’art du problème.

Les différents détails et réflexions apportés tout au long de l’état de l’art nous permettront de dresser un bilan positif : même si toutes ces approches résolvent l’alignement structure-séquence, de façon différentes, sur des familles d’instances différentes, nous pouvons entrevoir comment unifier tous ces travaux, et plus important encore, comment les généraliser.

La contribution : unification et généralisation par une approche à complexité paramétrée 

C’est aussi la contribution principale du travail présenté dans ce mémoire. Nous montrerons comment, en utilisant un unique algorithme à complexité paramétrée et non spécifique à une classe d’instances, nous pouvons résoudre le problème d’alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Pour réaliser ceci, nous utiliserons une technique empruntée à la théorie des graphes : la décomposition arborescente. Au final, nous obtiendrons un algorithme paramétré, dont le paramètre (entièrement lié à la décomposition arborescente) est raisonnablement petit pour les instances existantes dans des bases de données biologiques.

Les ARN et la bio-informatique de l’ARN

Composition et structures 3D des ARN noncodants

Composition
L’ARN est un polymère, c’est-à-dire un enchainement de briques de base : les nucléotides. Sa représentation primaire capture cette conception selon laquelle l’ARN est comme un collier de perles où chaque perle représente un nucléotide.

Un nucléotide est constitué de trois sous-groupes d’atomes : la base (qui peut être une adénine (A), une cytosine (C), une guanine (G) ou un uracile (U)), le ribose et le groupement phosphate . L’enchainement de deux nucléotides consécutifs est assuré par une liaison phosphodiester, interaction covalente entre le groupement phosphate du premier nucléotide et le ribose du deuxième .

Obtenir la succession des nucléotides formant un ARN, c’est-à-dire sa séquence, est aujourd’hui quelque chose d’accessible. On parle de séquençage d’ARN, et les dernière techniques mises au point (comme par exemple la RNAseq) permettent de séquencer avec un haut débit les ARN. En revanche, il est très difficile de reconnaitre un ARN à partir de sa séquence, c’est-à-dire de savoir si il est codant ou non-codant, et dans le dernier cas, à quelle famille il appartient.

Structures des ARN non-codants 

Une fois transcrit (et même pendant la transcription) l’ARN ne reste pas à l’état d’un brin sans forme. Il se replie sur lui même pour adopter une conformation tridimensionnelle propre . C’est cette forme qui va conférer en grande partie la fonction à la molécule. Le repliement est la conséquence de la formation d’interactions de différentes natures s’effectuant entre les atomes des nucléotides. Les plus représentées et les plus importantes sont les interactions hydrogène entre les bases .

Schématiquement, nous pouvons représenter une base comme un triangle, dont chaque côté porte un nom [36] : Hoogsteen (H), Watson-Crick (W), Sugar (S) . Les bases peuvent s’apparier deux à deux par ces côtés en formant des liaisons hydrogène. Il existe douze combinaisons possibles car chaque combinaison de côtés se décline en deux versions (cis et trans) selon l’orientation .

Il existe néanmoins des incompatibilités d’appariements en fonction de la nature des bases et des côtés considérés [35, 57]. Nous reviendrons plus précisément sur ce point à la fin de ce mémoire.

Table des matières

1 Introduction
2 Les ARN et la bio-informatique de l’ARN
2.1 Composition et structures 3D des ARN non-codants
2.2 Modélisation bioinformatique de l’ARN
2.2.1 La structure primaire
2.2.2 Les niveaux de structures intermédiaires
2.2.3 La structure 3D
2.3 Évolution et homologie
2.4 Recherche d’ARN non-codants
2.5 Prédiction de structures
2.5.1 Les méthodes ab initio
2.5.2 Les méthodes comparatives
3 L’alignement structure-séquence d’ARN
3.1 Motivations et Enjeux
3.2 Définition du problème
3.3 État de l’art
3.3.1 Principe algorithmique et notions importantes
3.3.2 L’algorithme de Jiang
3.3.3 L’algorithme de Han
3.3.4 Les algorithmes de Wong
3.3.5 Combinaison des classes de structures
4 Unification et généralisation
4.1 Décomposition arborescente
4.2 Aligner avec les décompositions arborescentes
4.2.1 Définitions et notations
4.2.2 Équation de récurrence
4.2.3 Nouvelle définition et équation de récurrence
4.2.4 Étude de complexité
4.3 Décompositions arborescentes lissées
4.3.1 Définitions
4.3.2 Équation de récurrence
4.3.3 Étude de complexité
4.4 Construire des décompositions arborescentes d’ARN
4.4.1 Division en structures primitives
4.4.2 Les plongements en vagues
4.4.3 Construire les plongements en vagues
4.4.4 Assemblage des décompositions des structures primitives
4.5 Résultats finals de complexité
4.6 Comparatifs
4.6.1 Comparatifs avec les méthodes existantes
4.6.2 Comparatifs avec les heuristiques classiques de décompositions arborescentes
4.7 Nouvelles classes de structures
5 Perfectionnement pour l’application
5.1 Sous-optimaux
5.2 Heuristiques
5.3 Les fonctions de coûts
5.3.1 Les matrices RIBOSUM
5.3.2 Les matrices d’isostérie
5.3.3 Raffinement par apprentissage
6 Conclusion

Télécharger le rapport complet