English
Français

Info

Détails algorithmiques

Algorithme de comparaison

L'algorithme de comparaison de structures secondaires utilisé est celui décrit dans l'article "V.Guignon, C.Chauve and S.Hamel, An edit distance between RNA stem-loops , Lecture Notes in Computer Science 3772 (String Processing and Information REtrival), pp. 335-347, 2005." avec quelques modifications décrites plus loin sur cette page. Cet algorithme permet d'aligner une tige ou une tige-boucle avec une autre tige ou tige-boucle. Comme les structures secondaires comportent souvent plusieurs tiges et tiges-boucles, l'algorithme décompose les structures en tiges et tiges-boucles et compare celles-ci entre elles. À partir de ces comparaisons, l'algorithme va ensuite essayer de reconstituer un alignement global. Cependant, la décomposition et le raccord des tiges et tiges-boucles se fait en suivant la séquence et non une représentation de la structure sous forme d'arbre de tiges et tiges-boucles ce qui, dans certains cas, ne permet pas de construire un alignement global. Dans de tels cas, qui arrivent avec des structures relativement différentes, la distance ou le score trouvé ne sont alors pas retenus comme résultats de la comparaison.
Note: La prochaine version de ce site proposera une meéthode permettant de prendre en compte ce genre de cas.

La première modification de l'algorithme concerne la prise en compte des bases n'appartenant pas à des tiges ou des tiges-boucles: les bases externes et les bases libres des boucles multiples. Ces dernières sont réparties et intégrées aux tiges ou tiges-boucles de chaque structure. Ainsi, les bases libres en 5' seront rattachées à la première tige ou tige-boucle, celles en 3' à la tige ou tige-boucle les précédant. Un segment de bases libres situé entre 2 tiges/tiges-boucles sera coupé en son milieu; la première moitié du segment sera rattachée à la tige/tige-boucle précédente et la seconde moitié à la tige/tige-boucle suivante.

La seconde modification concerne le calcul de scores. L'algorithme présenté dans l'article permet de calculer des distances en recherchant un coût minimal (positif) d'édition. Pour calculer un score, l'algorithme ne cherche plus à minimiser un coût mais à maximiser un score (pour faire simple, on remplace dans les fonctions "min()" par "max()"). Fondamentalement, le calcul d'une distance ou d'un score reviennent au même: le calcul d'un score entre 2 structures retourne la même valeur que le calcul de la distance entre ces deux structures si on emploie le même schéma de score en inversant simplement le signe de chaque coût. Cependant, d'un point de vue sémantique, une distance ne devrait pouvoir être que positive ou nulle. En revanche, un score peut être aussi bien positif que négatif.
Note: si vous tentez de retrouver le même alignement entre une structure A et une structure B en calculant une distance et un score (avec des coûts dont les signes ont été inversés), il est possible que les alignements retournés ne soient pas identiques (même si les scores correspondent). Cela n'a rien de surprenant et vient du fait que plusieurs alignements optimaux sont possibles et qu'actuellement, seul le premier trouvé est retourné et ce dernier diffère suivant la méthode (distance ou score) employée. Il peut en être de même en utilisant la même méthode mais en inversant l'ordre des structures.

Algorithmes de recherche

Les algorithmes de recherche de structures similaires et de tiges ou tiges-boucles fonctionnent suivant le même principe. La structure ou la tige/tige-boucle de la requête est dans un premier temps analysée pour en extraire des caractéristiques structurelles. Pour une structure, il s'agit de sa longueur de séquence, de son nombre de tiges et de son nombre de tiges-boucles. Pour une tige ou une tige-boucle, il s'agit de sa longueur de séquence, de son nombre de bases appariées et de son nombre de bases dans la boucle terminale (dans le cas d'une tige-boucle). Ensuite, l'algorithme cherche dans la base de données toutes les structures possédant ces mêmes caractéristiques. Tant que leur nombre est inférieur à 100 pour les structures et 500 pour les tiges/tiges-boucles, un intervalle est augmenté pour chaque caractéristique. Ainsi, pour les structures similaires, l'intervalle de longueur est augmenté de plus ou moins 5 unités avant une nouvelle recherche et de plus ou moins une tige et une tige-boucle toutes les 4 recherches. Pour les tiges/tiges-boucles, l'algorithme augmente à chaque recherche, de façon alternative, soit le nombre de bases appariées et celui des bases de la boucle terminale, soit la longueur de la séquence. Une fois que le nombre minimal de structures ou de tiges/tiges-boucles similaires est atteint, les comparaisons commencent.
Note: le nombre total de structures sur lequel s'est effectuée la recherche, le nombre de structures candidates qui ont été retenues pour comparaison et les intervalles de recherche pour chaque paramètre sont indiqués dans la sortie brute par les champs suivants:

EXTERNALDBCOUNT
nombre total de structures dans la base de données (recherche de structures similaires)
EXTERNALDBSOSLCOUNT
nombre total de tiges/tiges-boucles dans la base de données (recherche de tiges/tiges-boucles)
DBCOUNT
nombre de structures ou de tiges/tiges-boucles candidates retenues pour les comparaisons (recherche de structures similaires et tiges/tiges-boucles)
LENGTHRANGE
valeur ajoutée ou soustraite à la longueur pour définir un intervalle de longueur de séquence (recherche de structures similaires et tiges/tiges-boucles)
STEMSRANGE
valeur ajoutée ou soustraite au nombre de tiges pour définir un intervalle (recherche de structures similaires)
STEMLOOPSRANGE
valeur ajoutée ou soustraite au nombre de tiges-boucles pour définir un intervalle (recherche de structures similaires)
PAIREDBASESRANGE
valeur ajoutée ou soustraite au nombre de bases appariées pour définir un intervalle (recherche de tiges/tiges-boucles)
HAIRPINBASESRANGE
valeur ajoutée ou soustraite au nombre de bases dans la boucle terminale pour définir un intervalle (recherche de tiges/tiges-boucles)

Algorithme d'importation de structures

L'importation de structures secondaires à partir d'un alignement multiple et d'une structure consensus s'effectue de la façon suivante:
1) dans un premier temps la séquence d'intérêt est isolée avec la structure consensus;
2) les trous sont ensuite retirés simultanément sur la séquence et la structure tout en tenant compte que cela peut occasionner la disparition de certaines paires du consensus (altération);
3) les paires qui ne sont ni Watson-Crick ni Wobble sont brisées;
4) enfin, une procédure essaie d'allonger les tiges en détectant et en ajoutant des appariements là où les bases s'y prêtent. L'algorithme recherche les paires possibles à chaque extrémité d'un empilement de bases (ie. depuis les paires terminales des 2 extrémités d'une série ininterrompue de paires de bases en incluant les nouvelles paires détectées) jusqu'à une distance de 5 bases1 mais n'apparient pas les bases des boucles terminales comportant moins de 3 bases (taille la plus petite pour une boucle terminale de structure secondaire).

Note: en utilisant les structures de notre base de données, il faut garder à l'esprit que la méthode d'importation employée introduit un biais sur sur les structures les rendant possiblement différentes de la réalité.

Exemple:
Alignement multiple d'origine:

--ACCCGGC-CAUA---GUGGCCG-GGCAA-CAC-CCGG-U-C--UCGUUUCGAACCCG-GA-AGUUAA-GCCGG-CCACGUCAGAACG-GCC-G-UGAGGUCCGAGAGG-CCUCGCAGCCGUUCUGA----GCU-GGGAU--
--ACCCGGC-CAUA---GCGGCCG-GGCAA-CAC-CCGG-A-C--UCAUGUCGAACCCG-GA-AGUUAA-GCCGG-CCGCGUUGGGGGA-UGCUG-UGGGGUCCGCGAGG-CCCCGCAGCGCCCCCAA----GCC-GGGAU--
--ACCCGGU-CACA---GUGAGCG-GGCAA-CAC-CCGG-A-C--UCAUUUCGAACCCG-GA-AGUUAA-GCCGC-UCACGUUAGUGGG-GCC-G-UGGAUACCGUGAGG-AUCCGCAGCCCCACUAA----GCU-GGGAU--
etc.
<<<<<<<<<........<<.<<<<.<...<.<...<<<<.<.<.........>>..>>>.>...>>.....>>>>.>..>><.<<.<<.....<.<<.....<<....>>......>>.>..>>.>>...>.>>>.>>>>>>.


Phase 1:

--ACCCGGC-CAUA---GUGGCCG-GGCAA-CAC-CCGG-U-C--UCGUUUCGAACCCG-GA-AGUUAA-GCCGG-CCACGUCAGAACG-GCC-G-UGAGGUCCGAGAGG-CCUCGCAGCCGUUCUGA----GCU-GGGAU--
<<<<<<<<<........<<.<<<<.<...<.<...<<<<.<.<.........>>..>>>.>...>>.....>>>>.>..>><.<<.<<.....<.<<.....<<....>>......>>.>..>>.>>...>.>>>.>>>>>>.


Phase 2 (les bases de paires altérées sont indiquées en rouge):

ACCCGGCCAUAGUGGCCGGGCAACACCCGGUCUCGUUUCGAACCCGGAAGUUAAGCCGGCCACGUCAGAACGGCCGUGAGGUCCGAGAGGCCUCGCAGCCGUUCUGAGCUGGGAU
<<<<<<<....<<.<<<<<...<<..<<<<<<.......>>..>>>>..>>....>>>>>..>>*.<<.<<.....<.....<<....>>.....>*.*..>>.>>.>>>>>>>*


Phase 3 (les paires brisées sont indiquées en rouge):

ACCCGGCCAUAGUGGCCGGGCAACACCCGGUCUCGUUUCGAACCCGGAAGUUAAGCCGGCCACGUCAGAACGGCCGUGAGGUCCGAGAGGCCUCGCAGCCGUUCUGAGCUGGGAU
*((((((....**.(((((...((..((((((.......))..))))..))....)))))..**..**.(*.....*.....((....)).....*.....*).**.))))))*.


Phase 4 (les paires créées sont indiquées en rouge):

ACCCGGCCAUAGUGGCCGGGCAACACCCGGUCUCGUUUCGAACCCGGAAGUUAAGCCGGCCACGUCAGAACGGCCGUGAGGUCCGAGAGGCCUCGCAGCCGUUCUGAGCUGGGAU
(((((((..(.((((((((.((((..((((((.......))..))))..)))..)))))))))).(.(.((.(.(.((.((.((....)).)))..)).)).).)).)))))).)


Comme on peut le voir, le processus d'amélioration des structures désalignées peut bien fonctionner comme c'est le cas pour la première tige-boucle, mais il peut également trouver des résultats sous-optimaux comme dans le cas de la seconde tige-boucle.
Note: il est prévu de remplacer la routine actuelle servant à améliorer les structures importées par un outil de calcul de repliement optimal appliqué à chaque tige/tige-boucle dans la prochaine version du site pour corriger le biais structurel présenté ici dans l'amélioration de la seconde tige-boucle de l'exemple.


Vous pouvez expérimenter l'outil servant à recomposer une structure secondaire d'ARN à partir d'un alignement multiple et d'une structure consensus ici.