非表示:
キーワード:
-
要旨:
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.
