Genomic RNA research

Overview

The Reinert lab worked already on multiple RNA sequence-structure alignments based on ILPs [1, 2] and other RNA related analyses [3].

 

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

[1] M. Bauer, G. W. Klau, and K. Reinert, “An Exact Mathematical Programming Approach to Multiple RNA Sequence-Structure Alignment.,” Algorithmic Operations Research, 2008.
[Bibtex]
@article{fu_mi_publications331,
note = {to appear},
title = {An Exact Mathematical Programming Approach to Multiple RNA Sequence-Structure  Alignment.},
year = {2008},
journal = {Algorithmic Operations Research},
author = {M. Bauer and G. W. Klau and K. Reinert},
url = {http://publications.imp.fu-berlin.de/331/}
}
[2] M. Bauer, G. W. Klau, and K. Reinert, “Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization.,” BMC Bioinformatics, vol. 8, iss. 1, p. 271, 2007.
[Bibtex]
@article{fu_mi_publications332,
volume = {8},
journal = {BMC Bioinformatics},
author = {M. Bauer and G. W. Klau and K. Reinert},
number = {1},
title = {Accurate multiple sequence-structure alignment of RNA sequences using  combinatorial optimization.},
year = {2007},
pages = {271},
month = {July},
url = {http://publications.imp.fu-berlin.de/332/}
}
[3] A. -K. Emde, M. Grunert, D. Weese, K. Reinert, and S. R. Sperling, “MicroRazerS: Rapid alignment of small RNA reads,” Bioinformatics, vol. 26, iss. 1, p. 123–124, 2010.
[Bibtex]
@article{fu_mi_publications792,
volume = {26},
publisher = {Oxford University Press},
journal = {Bioinformatics},
author = {A.-K. Emde and M. Grunert and D. Weese and K. Reinert and S. R. Sperling},
number = {1},
title = {MicroRazerS: Rapid alignment of small RNA reads},
year = {2010},
pages = {123--124},
month = {January},
url = {http://publications.imp.fu-berlin.de/792/},
abstract = {Motivation: Deep sequencing has become the method of choice for determining the small RNA content of a cell. Mapping the sequenced reads onto their reference genome serves as the basis for all further analyses, namely for identification and quantification. A method frequently used is Mega BLAST followed by several filtering steps, even though it is slow and inefficient for this task. Also, none of the currently available short read aligners has established itself for the particular task of small RNA mapping. Results: We present MicroRazerS, a tool optimized for mapping small RNAs onto a reference genome. It is an order of magnitude faster than Mega BLAST and comparable in speed to other short read mapping tools. In addition, it is more sensitive and easy to handle and adjust. Availability: MicroRazerS is part of the SeqAn C++ library and can be downloaded from http://www.seqan.de/projects/MicroRazerS.html. Contact: emde@inf.fu-berlin.de, grunert@molgen.mpg.de}
}