Overview
The Reinert lab worked already on multiple RNA sequence-structure alignments based on ILPs [1] and other RNA related analyses [1].
We proposed a graph based model for pairwise and multiple sequence-structure alignment. The computational problem was phrased in form of an Integer Linear Program (ILP), which in turn was solved using a lagrangian relaxation Ansatz. The resulting program, LARA, was and still is very competitive with current methods (see Figure).
The model has three distinctive advantages we want to exploit in our current work with Annalisa Marsico. The first is that it allows for arbitrary pseudoknots in aligning two RNA sequences, the second is, that the model can naturally incorporate various sources of information, such as basepair probability matrices for normal and pseudoknotted structures, fixed optimal or suboptimal structures from structure prediction routines, or experimentally derived constraints. Thirdly, the algorithm for solving the Lagrangian relaxation basically boils down to iteratively compute many (local or global) standard sequence alignments, a step we are about to significantly speed up using vectorisation and multi-core techniques (work performed with Intel in an IPCC (Intel Parallel Compute Center) project, see also under the data structure and parallelisation theme).
People currently working mainly on this
Jörg Winkler: Fast structural alignment and lncRNA analysis. Read here more about the project.
Relevant publications