RNA SECONDARY STRUCTURE PREDICTION
The discovery of new families of non-coding RNA (ncRNA) demands dedicated tools to predict their structure. Programs that compute secondary structure naturally organize themselves along several noticeable directions that implicitly depend on their context of use. When a large family of not too divergent homologous sequences is available, a multiple alignment of high quality can be obtained and covariation analysis has proven to be very accurate in guessing the structure in that context. When only a small family of poorly conserved RNA sequences are available, a good starting alignment can hardly be constructed, resulting usually in the inapplicability of the methods based on pre-alignment. In that second context, another option is to search for the alignment and the structure at the same time. The outcome is then both a common structure and an alignement of the sequences respecting this structure (this formulation of the question is usually termed structural alignment).
When only a few, sometimes putative, RNA homologs are available, one
of the most famous approach is based on a set of recursions proposed by
Sankoff in 1985, who pionneered the field of RNA structural alignment.
The algorithmic complexity of this recursion set, although polynomial
in the size of the sequences
( 0(n3p) in time and 0(n2p)
in space for p sequences with sizes in the order of magnitude
n ), remains prohibitive for real case applications without
good heuristics.
Diverse ideas were applied to turn the Sankoff recursions usable but
although the heuristics found by others turn the algorithm of Sankoff
usable on natural RNA sequences, still these adaptations stay
inapplicable once the sequences show too much divergence.
We try to develop alternative heuristics to reduce that complexity.
SLIDES OF SOME PRESENTATIONS
Overview of treewidth and some applications (CENTRIA Seminar 2008) -
[ SLIDES ]
RNA secondary structure prediction with a few homologs (Duke University Friday Forum 2009) -
[ SLIDES ]
PROTEIN STRUCTURE PREDICTION FROM NMR DATA
