Neue Entwicklungen in der RNA-Strukturvorhersage
Vorlesung
Neue Entwicklungen in der RNA-Strukturvorhersage (Spezialvorlesung, Modul 10-202-2208):
Folien
Regular (non-sparsified) RNA Prediction [pdf slides]
Literatur
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.