A Polyhedral Approach to RNA Sequence Structure Alignment

Lenhof, Hans-Peter; Reinert, Knut; Vingron, Martin

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. Journal of Computational Biology, 5(3), 517-530.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3763-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3764-D

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Lenhof, Hans-Peter¹, Author
Reinert, Knut¹, 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 generally is a single-stranded molecule where the bases form hydrogen bonds w ithin 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: Modified: 2010-03-02Date issued: 1998

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 517953
Other: Local-ID: C1256428004B93B8-7F38667AAEF78462412567000049A3CA-LenReiVin1998

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Journal of Computational Biology

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 5 (3) Sequence Number: - Start / End Page: 517 - 530 Identifier: -