Modèles à 3 états
L’idée de combiner les prédictions en une structure génique complète est que les contraintes « grammaticales » peuvent exclure certains assemblages d’exon erronés. La structure grammaticale du problème a été soulignée par David Searls (Searls, 1992 ; Dong et Searls, 1994), qui a également proposé d’utiliser les méthodes des grammaires formelles de l’informatique et de la linguistique. La programmation dynamique peut souvent être décrite de manière pratique par une sorte d’automate à états finis (Searls et Murphy, 1995 ; Durbin et al., 1998). Un modèle peut avoir un état pour le début de la traduction (S), un pour les sites donneurs (D), un pour les sites accepteurs (A) et un pour la fin de la traduction (T). Chaque fois qu’une transition est effectuée d’un état à un autre, un score (ou une pénalité) est ajouté. Pour la transition de l’état donneur à l’état accepteur, le score de l’intron est ajouté au score total, et ainsi de suite. La Figure 11.2 présente le diagramme d’état de l’algorithme de programmation dynamique simple ci-dessus. Pour chaque variable de l’algorithme, il y a un état correspondant avec le même nom, et il faut également un état de début et de fin.
Figure 11.2. Un automate à états finis correspondant à l’algorithme DP simple.
L’avantage d’une telle formulation est que la programmation dynamique pour trouver le score maximum (ou la pénalité minimum) est d’un type plus général, et donc l’ajout de nouveaux états ou de nouvelles transitions est facile. Par exemple, il est facile de dessiner le diagramme d’état d’un algorithme de programmation dynamique plus général qui autorise un nombre quelconque de gènes et également des gènes partiels (Figure 11.3), alors qu’il est compliqué de l’écrire. De même, le diagramme d’état de l’algorithme tenant compte de la trame esquissé ci-dessus est présenté à la figure 11.4.
Figure 11.3. Le modèle de la figure 11.2 avec des transitions ajoutées qui permettent de prédire un nombre quelconque de gènes et de gènes partiels où la séquence commence ou se termine au milieu d’un exon ou d’un intron.
Figure 11.4. Un modèle qui assure la cohérence des trames tout au long d’un gène. Comme dans les deux figures précédentes, les lignes pointillées correspondent aux régions intergéniques, les pointillés aux introns et les lignes pleines aux régions codantes (exons).
Si les scores utilisés sont des probabilités logarithmiques ou des probabilités logarithmiques, alors un automate à états finis est essentiellement un modèle de Markov caché (HMM), et ceux-ci ont été introduits récemment dans la recherche de gènes par plusieurs groupes. La seule différence fondamentale avec les schémas de programmation dynamique évoqués ci-dessus est que ces modèles sont entièrement probabilistes, ce qui présente certains avantages. L’un de ces avantages est que le problème de la pondération est plus facile.
VEIL (Henderson et al., 1997) est une application d’un HMM au problème de la recherche de gènes. Dans ce modèle, tous les capteurs sont des HMMs. Le module exon est essentiellement une chaîne de Markov inhomogène de premier ordre, qui est décrite ci-dessus. C’est l’ordre naturel de mise en œuvre dans un HMM, car chacune des probabilités conditionnelles de la chaîne de Markov inhomogène correspond alors à la probabilité d’une transition d’un état à l’autre dans le HMM. Il n’est pas possible d’éviter les codons stop dans le cadre de lecture lorsqu’on utilise un modèle de premier ordre, mais dans VEIL, quelques états supplémentaires sont ajoutés de manière astucieuse, ce qui rend la probabilité d’un codon stop nulle. Les détecteurs de sites d’épissage sont réalisés de manière similaire. Les modules individuels sont ensuite combinés essentiellement comme dans la figure 11.2 (c’est-à-dire que la cohérence des trames n’est pas imposée). Le modèle combiné est un grand HMM, et toutes les transitions ont des probabilités associées. Ces probabilités peuvent être estimées à partir d’un ensemble de données d’apprentissage par une méthode de maximum de vraisemblance. Pour combiner les modèles, cela revient essentiellement à compter les occurrences des différents types de transitions dans l’ensemble de données. Par conséquent, la pondération implicite des capteurs individuels n’est pas vraiment un problème.
Bien que la façon dont la structure optimale du gène est trouvée soit similaire dans l’esprit à la programmation dynamique ci-dessus, elle semble très différente dans la pratique. Cela est dû au fait que la programmation dynamique est effectuée au niveau des états individuels dans tous les sous-modèles ; il y a plus de 200 états de ce type dans VEIL. Le modèle étant entièrement probabiliste, on peut calculer la probabilité de toute séquence d’états pour une séquence d’ADN donnée. Cette séquence d’états (appelée chemin) détermine l’affectation des exons et des introns. Si le chemin passe par le modèle exon, cette partie de la séquence est étiquetée comme exon ; s’il passe par le modèle intron, elle est étiquetée intron, et ainsi de suite. L’algorithme de programmation dynamique, appelé algorithme de Viterbi, trouve le chemin le plus probable à travers le modèle pour une séquence donnée, et à partir de là, la structure génétique prédite est dérivée (voir Rabiner (1989) pour une introduction générale aux HMM).
Ce modèle probabiliste a l’avantage de résoudre le problème de la pondération des capteurs individuels. On peut montrer que l’estimation par maximum de vraisemblance des paramètres est optimale si les données d’entraînement sont suffisantes et si la nature statistique des gènes peut être décrite par un tel modèle. Une partie faible de VEIL est le modèle d’exon de premier ordre, qui n’est probablement pas capable de capturer les statistiques des régions codantes, et la plupart des autres méthodes utilisent des modèles de quatrième ou cinquième ordre.
Un chercheur de gènes basé sur les HMM, appelé HMMgene, est actuellement en cours de développement. La méthode de base est la même que VEIL, mais elle comprend plusieurs extensions à la méthodologie HMM standard, qui sont décrites par Krogh (1997). L’une des plus importantes est que les régions de codage sont modélisées par une chaîne de Markov inhomogène du quatrième ordre au lieu d’une chaîne du premier ordre. Ceci est réalisé par une extension presque triviale du formalisme HMM standard, qui permet une chaîne de Markov de n’importe quel ordre dans un état du modèle, alors que le HMM standard a une simple distribution de probabilité inconditionnelle sur les quatre bases (correspondant au 0e ordre). Le modèle tient compte des cadres et peut prédire n’importe quel nombre de gènes et de gènes partiels, de sorte que la structure globale du modèle est celle de la figure 11.4, avec des transitions ajoutées pour permettre le début et la fin dans les introns, comme dans la figure 11.3.
Comme nous l’avons déjà mentionné, la méthode d’estimation du maximum de vraisemblance fonctionne bien si la structure du modèle peut décrire les véritables statistiques des gènes. Il s’agit d’une hypothèse très idéalisée, et c’est pourquoi HMMgene utilise une autre méthode d’estimation des paramètres appelée maximum de vraisemblance conditionnelle (Juang et Rabiner, 1991 ; Krogh, 1994). En gros, le maximum de vraisemblance maximise la probabilité des séquences d’ADN dans l’ensemble d’apprentissage, tandis que le maximum de vraisemblance conditionnel maximise la probabilité des structures génétiques de ces séquences, ce qui, après tout, est ce qui nous intéresse. Ce type d’optimisation est conceptuellement similaire à celui utilisé dans GeneParser, où la précision de la prédiction est également optimisée. HMMgene utilise également un algorithme de programmation dynamique différent de l’algorithme de Viterbi pour la prédiction de la structure du gène. Toutes ces méthodes ont contribué à une haute performance de HMMgene.
Genie est un autre exemple de modèle d’état probabiliste qui est appelé un HMM généralisé (Kulp et al., 1996 ; Reese et al., 1997). La figure 11.4 est en fait la structure d’état de Genie, et tant cette figure que la figure 11.2 sont essentiellement copiées de Kulp et al. (1996). Dans Genie, les capteurs de signaux (sites d’épissure) et les capteurs de contenu (potentiel de codage) sont des réseaux neuronaux, et la sortie de ces réseaux est interprétée comme des probabilités. Cette interprétation nécessite l’estimation de paramètres de probabilité supplémentaires qui fonctionnent comme des poids sur les capteurs. Ainsi, bien qu’il soit formulé comme un modèle probabiliste, le problème de la pondération apparaît toujours de manière déguisée. L’algorithme de prédiction est presque identique à l’algorithme de programmation dynamique de la dernière section. Une version de Genie inclut également les similarités des bases de données comme partie du capteur d’exon (Kulp et al., 1997).
Les HMM généralisés présentent deux avantages principaux par rapport aux HMM standard. Premièrement, les capteurs individuels peuvent être de n’importe quel type, comme les réseaux neuronaux, alors que dans un HMM standard, ils sont limités par le cadre HMM. Deuxièmement, la distribution de la longueur (des régions de codage, par exemple) peut être prise en compte explicitement, alors que la distribution naturelle de la longueur pour un HMM est une distribution géométrique, qui décroît exponentiellement avec la longueur. Cependant, il est possible d’avoir une modélisation assez avancée de la longueur dans un HMM si plusieurs états sont utilisés (Durbin et al., 1998). L’avantage d’un système comme HMMgene, d’autre part, est qu’il s’agit d’un modèle intégré, qui peut être optimisé en une seule fois pour une précision de prédiction maximale.
Un autre chercheur de gènes basé sur un HMM généralisé est GENSCAN (Burge et Karlin, 1997). Les principales différences entre la structure d’état de GENSCAN et celle de Genie ou HMMgene est que GENSCAN modélise la séquence dans les deux sens simultanément. Dans de nombreux outils de recherche de gènes, tels que ceux décrits ci-dessus, les gènes sont d’abord prédits sur un brin, puis sur l’autre. La modélisation simultanée des deux brins a été réalisée avec beaucoup de succès dans GeneMark, et une méthode similaire est mise en œuvre dans GENSCAN. Un avantage (et peut-être le principal) est que cette construction évite les prédictions de gènes se chevauchant sur les deux brins, qui sont vraisemblablement très rares dans le génome humain. GENSCAN modélise un nombre quelconque de gènes et de gènes partiels comme HMMgene. Les capteurs de GENSCAN sont similaires à ceux utilisés dans HMMgene. Par exemple, le capteur de codage est une chaîne de Markov inhomogène d’ordre 5. Les capteurs de signaux sont essentiellement des matrices de poids dépendant de la position, et sont donc également très similaires à ceux de HMMgene, mais il y a des fonctionnalités plus avancées dans les modèles de sites d’épissage. GENSCAN modélise également les promoteurs et les UTR 5′ et 3′.