COMPUTER SCIENCE COLLOQUIUM

A solution of the RNA-RNA Interaction Problem .

Jing Qin MPI for Mathematics in the Sciences, Leipzig, Germany

Thursday, 16 June, 2011 at 14:15 IMADA's Seminar Room

ABSTRACT

The RNA-RNA interaction problems deals with the energetically optimal structure of two RNA molecules that bind to each other. The standard model introduced by Alkan et al. (J. Comput. Biol. 13: 267-282, 2006) allows secondary structures in both partners as well as additional basepairs between the two RNAs subjects to certain restrictions that allow a polynomial-time dynamic programming solution.

The software rip is a O(N^6) time and O(N^4) space dynamic programming algorithm which enables the calculation of the partition function of RNA-RNA interaction complexes “from the inside to the outside” (IO). Thereby the base-pairing probabilities and the hybrid probabilities are obtained “from the outside to the inside". Furthermore, the scheme for the computation of a partition function implies a corresponding stochastic backtracing procedure that can be used to sample structures from the ensemble according to the Boltzmann distribution.

Recently, we develop the a priori folding algorithm ripalign as a generalization of rip from pair of single RNA to a pair of interacting multiple sequence alignments (MSA), which takes care of both thermodynamic stability as well as sequence/structure covariation. The algorithm described above is implemented in C as part of the rip package. The supplemental material, source code and input/output files can freely be downloaded from

http://www.combinatorics.cn/cbpc/ripalign.html.

Host: Christian Reidys

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle