An Exact Mathematical Programming Approach to Multiple RNA Sequence-Structure Alignment

Authors

  • Markus Bauer International Max Planck Research School & Free University Berlin, Department of Mathematics and Computer Science, Arnimallee 3, 14195 Berlin, Germany
  • Gunnar W. Klau CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
  • Knut Reinert Free University Berlin, Department of Mathematics and Computer Science, Takustr. 9, 14195 Berlin, Germany

Abstract

One of the main tasks in computational biology is the computation of alignments of genomic sequences to reveal their commonalities. In case of DNA or protein sequences, sequence information alone is usually sufficient to compute reliable alignments. RNA molecules, however, build spatial conformations, which can be represented by graph-like secondary structures. Often, secondary structures are more conserved than the actual sequence. Hence, computing reliable alignments of RNA molecules should take this additional information into account. We present a novel framework for the computation of exact multiple sequence-structure alignments. We give a graph-theoretic representation of the sequence-structure alignment problem and phrase it as an integer linear program. We identify a class of constraints that make the problem easier to solve and relax the original integer linear program in a Lagrangian manner. We run experiments on data from the RFAM database and compare the performance of our model to heuristically inferred multiple structural alignments. Finally, experiments on a recently published benchmark show that in the pairwise case our algorithm achieves results comparable to those obtained by more costly dynamic programming algorithms while needing less computation time.

Downloads

How to Cite

Bauer, M., Klau, G. W., & Reinert, K. (2008). An Exact Mathematical Programming Approach to Multiple RNA Sequence-Structure Alignment. Algorithmic Operations Research, 3(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/9700

Issue

Vol. 3 No. 2 (2008)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.