English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  A polyhedral approach to RNA sequence structure alignment

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3761-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3762-2
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Lenhof, Hans-Peter1, Author           
Reinert, Knut1, Author           
Vingron, Martin, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021998
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM Press
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 517921
Other: Local-ID: C1256428004B93B8-D9EBAC8904160ABEC12565D90043268B-LenReiVin98
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: New York, USA
Start-/End Date: 1998

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 2nd Annual International Conference on Computational Molecular Biology (RECOMB-98)
Source Genre: Proceedings
 Creator(s):
Istrail, Sorin, Editor
Pevzner, Pavel, Editor
Waterman, Michael, Editor
Affiliations:
-
Publ. Info: New York, USA : ACM Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 153 - 162 Identifier: ISBN: 0-89791-976-9