e-journal

Local Exact Pattern Matching for Non-Fixed RNA Structures

---

Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming algorithms for finding common structure-sequence patterns between two RNAs. The RNAs are given by their sequence and a set of potential base pairs with associated probabilities. In contrast to prior work on local pattern matching of RNAs, we support the breaking
of arcs. This allows us to add flexibility over matching only fixed structures; potentially matching only a similar subset of specified base pairs. We present an Oðn3Þ algorithm for local exact pattern matching between two nested RNAs, and an Oðn3 log nÞ algorithm for one nested RNA and one bounded-unlimited RNA. In addition, an algorithm for approximate pattern matching is introduced that for two given nested RNAs and a number k, finds the maximal local pattern matching score between the two RNAs with at most k mismatches in Oðn3k2Þ time. Finally, we present an Oðn3Þ algorithm for finding the most similar subforest between two nested RNAs.
Index Terms—Pattern matching, RNA local similarity, tree local similarity, sequence-structure matching

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS

No. Panggil

-

Penerbit

New York : IEEE., 2014

Deskripsi Fisik

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, VOL. 11, NO. 1, JANUARY/FEBRUARY 2014

Bahasa

English

ISBN/ISSN

1545-5963

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 11, NO. 1, JANUARY/FEBRUARY 2014

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Yuli/Agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar