# Publication details

##
Fast RNA Structure Alignment for Crossing Input Structures

Rolf Backofen, Gad Landau, Mathias Möhl, Dekel Tsur, Oren Weimann

Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), pp. 236-248, Springer Berlin / Heidelberg, 2009

The complexity of pairwise RNA structure alignment
depends on the structural restrictions assumed for
both the input structures and the computed consensus
structure. For arbitrarily crossing input and
consensus structures, the problem is NP-hard. For
non-crossing consensus structures, Jiang et al's
algorithm [1] computes the alignment in O(n^2 m^2 ) time
where n and m denote the lengths of the two input
sequences. If also the input structures are
non-crossing, the problem n corresponds to tree
editing which can be solved in O(m^2 n(1 + log n/m ))
time [2]. We present a new algorithm that solves the
problem for dcrossing structures in O(dm^2 n log n)
time, where d is a parameter that is one for
non-crossing structures, bounded by n for crossing
structures, and much smaller than n on most practical
examples. Crossing input structures allow for
applications where the input is not a fixed structure
but is given as base-pair probability
matrices.

Keywords : RNA, sequence structure alignment, simultaneous alignment and folding

Download PDF
Show BibTeX

@INPROCEEDINGS{BackofenEtAl:2009:Fast,
title = {Fast RNA Structure Alignment for Crossing Input Structures},
author = {Rolf Backofen and Gad Landau and Mathias M{\"o}hl and Dekel Tsur and Oren Weimann},
year = {2009},
editor = {Gregory Kucherov and Esko Ukkonen},
publisher = {Springer Berlin / Heidelberg},
booktitle = {Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009)},
series = {Lecture Notes in Computer Science},
pages = {236-248},
}

Login to edit

Webmaster,
Wed Sep 16 10:47:00 2009