Page suivante: 4.1.3 Détermination de structures tertiaires Niveau précédent: 4.1 Détermination et visualisation de Page précédente: 4.1.1 Détermination de structures secondaires

4.1.2 Visualisation de structures secondaires d'ARN

Une fois la structure secondaire calculée, les biologistes souhaitent la visualiser sous forme d'un graphe planaire tel que celui de la Figure 4. Un problème lié à la production automatique d'un tel dessin est que certains des éléments structuraux peuvent se chevaucher, nuisant à la clarté souhaitée pour une telle représentation. Une approche originale est proposée dans [ Mul 93] pour obtenir de manière automatique des dessins de structures secondaires sans chevauchement.

La structure secondaire est d'abord représentée sous forme d'un arbre où chaque sommet représente une boucle et chaque arc une hélice. La formulation dans le cadre CSP s'appuie sur la structure de cet arbre :

variables :

à chaque sommet correspond une variable représentant le dessin de la boucle associée et des hélices immédiatement rattachées ;

valeurs :

à chaque variable est associé un nombre fini (fixé par l'utilisateur) de valeurs qui sont des descripteurs de ces dessins ;

contraintes :

elles expriment l'absence de chevauchements entre éléments structuraux.

L'ensemble ordonné et fini de descripteurs est calculé dynamiquement au cours de la recherche. Les dessins générés à partir de ces descripteurs diffèrent essentiellement du fait de distorsions plus ou moins importantes exercées sur les arcs de cercles formant les boucles. Initialement, à chaque variable est associée une valeur donnant un descripteur correspondant à un cercle parfait. Lorsqu'un chevauchement est détecté, l'algorithme recherche la variable responsable du chevauchement et calcule un autre descripteur pour cette variable. Lorsque la variable n'a plus de valeur possible (aucun des descripteurs calculés ne permet de produire un dessin partiel sans chevauchement), la responsabilité du chevauchement est reportée à la variable associée au nud parent dans l'arbre représentant la structure secondaire et l'algorithme réalise un retour-arrière sur cette variable.

L'originalité de l'approche proposée s'appuie sur la construction d'un estimateur calculant l'espace nécessaire au dessin d'un sous-arbre. Cet estimateur tient compte du diamètre des cercles (fonction du nombre de bases dans la boucle qu'ils représentent), de la densité du sous-arbre (le nombre de nuds dans le sous-arbre) et de la compacité souhaitée. À partir de cet estimateur les idées suivantes sont développées :

• récupération de l'espace laissé disponible dans le cas de boucles terminales pour optimiser l'occupation spatiale du dessin ;
• test en continu des chevauchements et modification dynamique du dessin en conséquence pour répondre à l'objectif d'absence de chevauchement.

Le programme est paramétré pour explorer des espaces conformationnels de taille variable et autoriser des distorsions des arcs de cercles plus ou moins importantes.

La possibilité de se retrouver en situation d'échec, c'est-à-dire de ne pas pouvoir attribuer à chaque nud de l'arbre une configuration géométrique, pour un jeu de paramètres donné, représente l'inconvénient majeur de cet algorithme. Une possibilité serait de permettre la génération d'une structure minimisant le nombre de recouvrements.

Page suivante: 4.1.3 Détermination de structures tertiaires Niveau précédent: 4.1 Détermination et visualisation de Page précédente: 4.1.1 Détermination de structures secondaires