English
Français

Info

Algorithm Details

Comparison algorithm

The algorithm used to compare secondary structures on this site is the one described in the 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." with some modifications described later on in this page. This algorithm can align a stem or a stem-loop with another stem or stem-loop. As secondary structures usually contains several stems and stem-loops. The algorithm to compaire a pair of secondary structures split both structures into stems and stem-loops and compare each pair of stems and/or stem-loops. From these comparisons, the algorithm builds a global of the two secondary structures using a Smith-Waterman algorithm where each structure is represented by a sequence of its stems and stem-loops (see 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." for a precise description). Note however that due to the fact that we use a sequence alignment program for the second step, if the resulting alignment does not follw the tree-like structure of the two considered structures, which can happen for very different structures, it is discarded.
Note: Such cases will be handled in the next release of the website.

The first modification of the algorithm takes in account bases that do not belong to stems or stem-loops: external bases and bases of multiple-branch loops. Theses bases are distributed between and integrated into stems and stem-loops of each structure. This way, 5' free bases will be connected to the first stem or stem-loop, those of the 3' end to the preceding stem or stem-loop. An array of free bases between 2 stems/stem-loops will be split in its middle; the first half will be connected to the previous stem/stem-loop and the second half to the next stem/stem-loop.

The second modification deals with score scheme. The algorithm introduced in our paper enables to compute a distance by searching the minimal (positive) editing cost. To compute a similaritry measure, the algorithm does not try to minimize a cost anymore but tries to maximize a score (to make it simple, we replace in functions "min()" by "max()"). Basically, distance or score computation lead to the same result: computing a score between 2 structures returns the same value of a distance computation between these structures if we use the same score scheme with inverted signs for each cost. However, from a semantic point of view, a distance should never be negative. In contrary, a score can be either positive or negative.
Note: if you try to retrieve the same alignement between a structure A and a structure B by computing a distance and a score (with inverted signs for each cost), the returned alignements may not match (even if scores do). That is not surprising and comes from the fact that several optimal alignements can exist and at this time, only the first one found is returned and it can be a different one for each method (distance or score). The same situation can occur when using the same method and inverting order or structures.

Search algorithms

Similar structures and stems or stem-loops search algorithms work the same way. First, the query structure or stem/stem-loop is analysed to extract its structural characteristics. For a full secondary structure: its sequence length, its number of stems and its number of stem-loops. For a stem or a stem-loop: its sequence length, its number of paired bases and its number of bases in the hairpin loop (for a stem-loop). Then the algorithm seeks database for structures with the same characteristics. As long as the number of candidates is below 100 for structures and below 500 for stems/stem-loops, the range of each characteristic is increased. Thus, for similar structures, the length range is increased by plus or minus 5 units before a new search and plus or minus 1 stem and 1 stem-loop each 4 search. For stems/stem-loops, for each search, the algorithm increase alternatively either the number of paired bases and the number of bases in the hairpin loop, or the sequence length. Once the minimum number of candidates is reached, comparisons start.
Note: the number of structures in the database, the number of candidates used for comparisons and the used range of each characteristic are indicated in the raw output by the following fields:

EXTERNALDBCOUNT
total number of structures in database (for similar structures search)
EXTERNALDBSOSLCOUNT
total number of stems/stem-loops in database (for stems/stem-loops search)
DBCOUNT
counts of candidates used in comparisons (for similar structures and stems/stem-loops search)
LENGTHRANGE
value added or substracted to the sequence length to set a range (for similar structures and stems/stem-loops search)
STEMSRANGE
value added or substracted to the count of stems to set a range (for similar structures search)
STEMLOOPSRANGE
value added or substracted to the count of stem-loops to set a range (for similar structures search)
PAIREDBASESRANGE
value added or substracted to the paired bases count to set a range (for stems/stem-loops search)
HAIRPINBASESRANGE
value added or substracted to the hairpin bases count to set a range (for stems/stem-loops search)

Structure importation

The importation of secondary structures starting from a multiple alignment and a concensus structure is carried out in the following way:
1) initially the sequence of interest is extracted with the consensus structure;
2) holes are then withdrawn simultaneously in the sequence and the structure while taking into account that it can break certain pairs of the consensus (alteration);
3) pairs that are neither Watson-Crick nor Wobble are broken;
4) finally, a procedure tries to lengthen the stems by detecting and adding new possible pairings between bases. The algorithm seeks the possible pairs at each end of a pair stacking (ie. from terminal pairs of both ends of uninterrupted series of base-pairs including newly detected pairs) up to a maximum of 5 bases (arbitrary distance1) but does not pair the bases of a terminal loop containing less than 3 free bases (smallest hairpin loop for secondary structures).

Note: by using the structures of our database, keep in mind that the importation method introduced an artefact on the structures which can be different from reality.

Example:
Source Multiple Alignment:

--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 (altered paired bases are displayed in red):

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


Phase 3 (broken base pairs are displayed in red):

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


Phase 4 (created base pairs are displayed in red):

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


As one can see, this example shows the unaligned structure enhancement process can work well like on the first stem-loop but can also retrieve a sub-optimal structure like on the second stem-loop.
Note: the routine used to improve alignments will be replaced by an RNA folding tool applied to each stem/stem-loop in the next version of the site to fix the structural artefact shown here is the second stem-loop of the example.


You can try out the tool used to recompose RNA secondary structure starting from a multiple alignment and a consensus structure here.