RNA Algorithms 1000-2M25RNA
1. Introduction
About RNA, about this course, what to expect, how to pass.
2. Algorithms vs. computational problems
Classes of algorithms, classes of problems, complexity, what makes a well-defined computational problem, know your data
3. RNA structure
1D-2D-3D, interactions, motifs, pseudoknots, modular hierarchy, data formats, representations, visualizations, databases (Rfam, RNAcentral, PDB).
4. Computational problems in RNA structural studies
Types of experimental data (sequencing, chemical probing, 3D structure determination) and how they direct the computational problems
5. RNA sequence alignment
Needleman-Wunsch, Smith–Waterman, multiple sequence alignment, structural alignment, HMM, SCFG
6. RNA 2D structure prediction, single-sequence input
Nussinov algorithm, MFE and Turner algorithm, MEA and McCaskill algorithm
7. RNA 2D structure prediction with pseudoknots
Classes of pseudoknots, P vs. NP, units of prediction, greedy algorithms, the assignment problem and the Hungarian algorithm, MWM and Edmonds algorithm
8. RNA 2D structure prediction from homologous sequences
Align then fold, covariation analysis, fold then align, align & fold, Sankoff algorithm
9. Extra topics on RNA 2D structure prediction
Kinetics vs. thermodynamics, chemical probing and soft restraints, co-transcriptional folding, multi-sequence folding
10. RNA 3D structure annotation
Interactions, motifs, superposition, RMSD, Kabsch algorithm
11. RNA 3D motif search
Motif-motif comparison, motif-structure search
12. RNA 3D structure alignment
TM-score, rigid vs. flexible alignment
13. RNA 3D structure prediction I
Homology search, template-based modeling
14. RNA 3D structure prediction II
De novo prediction, MD and MC simulations, deep learning methods
15. Extra topics on RNA 3D structure prediction
MDS, knots, clashscore, energy, sampling and scoring
Type of course
Prerequisites (description)
Learning outcomes
Knowledge:
- knowledge of computational problems in RNA structural studies
- knowledge of algorithms used in RNA structural studies
- knowledge of state-of-the-art in RNA computational biology
Skills:
- ability to choose the proper algorithm for a given computational problem
- ability to implement selected algorithms
- ability to formulate, analyze, and solve computational problems
Competences:
- ability to critically assess computational approaches in RNA structural biology
- readiness to independently pursue research problems in RNA structure analysis
- capacity to integrate theoretical knowledge and practical skills in new contexts
- awareness of current challenges in RNA computational biology
Assessment criteria
Semester project and oral exam.
The project consists of an RNA 3D structure prediction task and an implementation of a selected algorithm. The exam serves to present the project.
Bibliography
Phillip Compeau & Pavel Pevzner (2018) Bioinformatics Algorithms. An Active Learning Approach.
Gorodkin, J., & Ruzzo, W. L. (Eds.). (2014). RNA sequence, structure, and function: computational and bioinformatic methods. New York, NY: Humana Press.
W. Saenger (1984). Principles of Nucleic Acid Structure
S. Neidle, M. Sanderson (2021). Principles of Nucleic Acid Structure
Vicens, Q., & Kieft, J. S. (2022). Thoughts on how to think (and talk) about RNA structure. Proceedings of the National Academy of Sciences, 119(17), e2112677119
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Bioinformatics and Systems Biology
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: