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

RSS Feed