de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A polyhedral approach to RNA sequence structure alignment

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44909

Lenhof,  Hans-Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45277

Reinert,  Knut
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Lenhof, H.-P., Reinert, K., & Vingron, M. (1998). A polyhedral approach to RNA sequence structure alignment. In S. Istrail, P. Pevzner, & M. Waterman (Eds.), Proceedings of the 2nd Annual International Conference on Computational Molecular Biology (RECOMB-98) (pp. 153-162). New York, USA: ACM Press.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3761-4
Abstract
Ribonucleic acid (RNA) is a polymer composed of four bases denoted A, C, G, and U. It is a generally single-stranded molecule where the bases form hydrogen bonds within the same molecule leading to structure formation. In comparing different homologous RNA molecules it is important to consider both the base sequence and the structure of the molecules. Traditional alignment algorithms can only account for the sequence of bases, but not for the base pairings. Considering the structure leads to significant computational problems because of the dependencies introduced by the base pairings. In this paper we address the problem of optimally aligning a given RNA sequence of unknown structure to one of known sequence and structure. We phrase the problem as an integer linear program and then solve it using methods from polyhedral combinatorics. In our computational experiments we could solve large problem instances -- 23S ribosomal RNA with more than $1400$ bases -- a size intractable for former algorithms.