README.md

Freiburg RNA algorithms for teaching

This repository contains the Javascript and Html sources for various algorithms related to RNA structure and RNA-RNA interaction prediction. Furthermore, we provide interactive implementations for general sequence alignment approaches.

All approaches are available in the Freiburg RNA Teaching webserver.

We are currently supporting:

• Nested RNA structure prediction
  • Counting nested structures (see NussinovDPAlgorithm_structuresCount)
  • Nussinov's maximal base pair structure prediction algorithm using different recursions (see NussinovDPAlgorithm_Unique, ..Ambiguous, ..Ambiguous2, ..MostAmbiguous)
  • McCaskill's base pair probability and unpaired probability computation (see NussinovDPAlgorithm_McCaskill)
  • MEA: maximum expected accuracy structure prediction (see DPAlgorithm_MEA)
• RNA-RNA interaction prediction
  • co-folding approach via Nussinov-variant (see DPAlgorithm_coFold)
  • hybrid-only intermolecular base pair maximization (see DPAlgorithm_hybrid)
  • accessibility-incorporating interaction prediction (see DPAlgorithm_rnaup)
• General sequence alignment approaches
  • pairwise alignment
    • Needleman-Wunsch (global, linear gap costs, quadratic space) (see js)
    • Hirschberg (global, linear gap costs, linear space) (see js)
    • Gotoh (global, affine gap costs) (see js)
    • Waterman-Smith-Beyer (global, arbitrary gap costs) (see js)
    • Smith-Waterman (local, linear gap costs) (see js)
    • Arslan-Egecioglu-Pevzner (local, linear gap costs, normalized score) (see js)
    • Gotoh (Local) (local, affine gap costs) (see js)
  • multiple alignment
    • Feng-Doolittle (Gotoh-based) (progressive, affine gap costs) (see js)
    • Iterative Refinement (Feng-Doolittle-based) (progressive, affine gap costs, iterative refinement) (see js)
    • Notredame-Higgins-Heringa (t-coffee) (progressive, data-derived scoring) (see js)
• Agglomerative Clustering (see js)
  • Complete Linkage (Furthest Neighbour)
  • Neighbour-Joining (Nearest Neighbour on clusters)
  • Single Linkage (Nearest Neighbour on elements between two different clusters)
  • Unweighted Pair Group Method with Arithmetic Mean (UPGMA) (Group Average or Average Linkage)
  • Weighted Pair Group Method with Arithmetic Mean (WPGMA) (Simple Average)

Each algorithm comes with a short introduction with links to related literature, the according dynamic programming recursions and a short explanation of the algorithms.

The algorithms were developed in order to enable an example-driven learning and teaching of RNA structure related algorithms. To reduce the level of complexity, all algorithms use a simple Nussinov-like energy scoring scheme, i.e. the energy of an RNA structure is directly related to its number of base pairs without further distinction.

For all approaches an exhaustive enumeration of optimal solutions is provided. Some interfaces also allow for suboptimal solution enumeration. Predicted structures/interactions are graphically visualized and where possible an interactive traceback visualization is enabled.

For local usage, just download or clone the repository content and open the index.html (structure/interaction prediction) or alignment.html (sequence alignment approaches) in a recent browser.