An Earley-style Parser for Solving the RNA-RNA Interaction Problem

In my bachelor’s thesis I extended an RNA secondary-structure prediction method based on stochastic context-free grammars to predicting the joint structure of pairs of interacting RNA molecules.

Technically, I wrote an efficient stochastic parser jackRIP in C++ that takes an arbitrary (stochastic) context-free grammar and determines the most likely derivation tree for a word, or the inside and outside probabilities. (The latter are a generalization of forward and backward probabilities know from hidden Markov models.)

I also worked through parsing and formal-language literature, in particular mildly context-sensitive formalisms. My alternative definition of multiple context-free grammars (see Section 2.8) makes this formalism more convenient to use to describe combinatorial classes.