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é.
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.

Flux RSS