@Article{Backofen:Will:_local_sequence_structure:JBCB2004,
  author =	 {Rolf Backofen and Sebastian Will},
  title =	 {Local Sequence-Structure Motifs in {RNA}},
  journal =	 {Journal of Bioinformatics and Computational Biology
                  (JBCB)},
  year =	 2004,
  pages =	 {681-698},
  volume =	 2,
  number =	 4,
  publisher =	 {Imperial College Press},
  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},
  user =	 {will},
  pmid =         {15617161},
  url =
                  {http://www.worldscinet.com/jbcb/02/0204/S0219720004000818.html}
}