Neue Entwicklungen in der RNA-Strukturvorhersage


Neue Entwicklungen in der RNA-Strukturvorhersage (Spezialvorlesung, Modul 10-202-2208):


Regular (non-sparsified) RNA Prediction [pdf slides]


Ydo Wexler, Chaya Zilberstein, and Michal Ziv-Ukelson. A study of accessible motifs and RNA folding complexity. J Comput Biol, 14 no. 6 pp. 856-72, 2007.

Candidate list approach for sparsification of RNA secondary structure prediction. In the class, we have discussed this method for base pair maximization and energy minimization; the latter as transfer of the former, rather shortly.

Rolf Backofen, Dekel Tsur, Shay Zakov, and Michal Ziv-Ukelson. Sparse RNA folding: Time and space efficient algorithms. J. Discrete Algorithms, 9 no. 1 pp. 12-31, 2011.

Based on this paper, we discussed sparsification based on OCT property of subsequences S_i..j; time efficient as well as time and space efficient variants; furthermore, sparsification based on OCT and STEP properties. The latter requires forward dynamic programming. Similar sparsification is applied to simultaneous alignment and folding. Finally (going beyond this paper), we have seen how similar methods can be applied to speed up other prediction problems like prediction with pseudoknots and prediction of RNA-RNA-interaction.