@article{Backofen:Will:_local_sequence_structure:JBCB2004,
author = {Backofen, Rolf and Will, Sebastian},
title = {Local Sequence-Structure Motifs in {RNA}},
journal = {Journal of Bioinformatics and Computational Biology
           (JBCB)},
year = {2004},
doi = {https://doi.org/10.1142/s0219720004000818},
url = {http://www.worldscinet.com/jbcb/02/0204/S0219720004000818.html},
volume = {2},
user = {will},
publisher = {Imperial College Press},
pmid = {15617161},
pages = {681-698},
number = {4},
abstract = {Ribonuclic acid (RNA) enjoys increasing interest in
            molecular biology; despite this interest fundamental
            algorithms are lacking, e.g. for identifying local
            motifs. As proteins, RNA molecules have a
            distinctive structure. Therefore, in addition to
            sequence information, structure plays an important
            part in assessing the similarity of
            RNAs. Furthermore, common sequence-structure
            features in two or several RNA molecules are often
            only spatially local, where possibly large parts of
            the molecules are dissimilar. Consequently, we
            address the problem of comparing RNA molecules by
            computing an optimal local alignment with respect to
            sequence and structure information. While local
            alignment is superior to global alignment for
            identifying local similarities, no general local
            sequence-structure alignment algorithms are
            currently known. We suggest a new general definition
            of locality for sequence-structure alignments that
            is biologically motivated and efficiently
            tractable. To show the former, we discuss locality
            of RNA and prove that the defined locality means
            connectivity by atomic and non-atomic bonds. To show
            the latter, we present an efficient algorithm for
            the newly defined pairwise local sequence-structure
            alignment (lssa) problem for RNA. For molecules of
            lengthes n and m, the algorithm has worst-case time
            complexity of $O(n^2m^2max(n,m))$ and a space
            complexity of only $O(nm)$. An implementation of our
            algorithm is available at
            http://www.bio.inf.uni-jena.de. Its runtime is
            competitive with global sequence-structure
            alignment. <p>Keywords: RNA; local alignment; local
            sequence-structure alignment; lssa}
}