@inproceedings{backofen06:_local_align_rna_sequen_arbit_scorin_schem,
  author    = {Rolf Backofen and
               Danny Hermelin and
               Gad M. Landau and
               Oren Weimann},
  title     = {Local Alignment of {RNA} Sequences with Arbitrary Scoring
               Schemes},
  editor    = {Moshe Lewenstein and
               Gabriel Valiente},
  booktitle   = CPM06,
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = 4009,
  year      = 2006,
  pages     = {246-257},
  abstract  = {Local similarity is an important tool in comparative
                  analysis of biological sequences, and is therefore
                  well studied. In particular, the Smith-Waterman
                  technique and its normalized version are two
                  established metrics for measuring local similarity in
                  strings. In RNA sequences however, where one must
                  consider not only sequential but also structural
                  features of the inspected molecules, the concept of
                  local similarity becomes more complicated. First, even
                  in global similarity, computing global
                  sequence-structure alignments is more difficult than
                  computing standard sequence alignments due to the
                  bi-dimensionality of information. Second, one can view
                  locality in two different ways, in the sequential or
                  structural sense, leading to different problem
                  formulations. In this paper we introduce two
                  sequentially-local similarity metrics for comparing
                  RNA sequences. These metrics combine the global RNA
                  alignment metric of Shasha and Zhang [16] with the
                  Smith-Waterman metric [17] and its normalized version
                  [2] used in strings. We generalize the familiar
                  alignment graph used in string comparison to apply
                  also for RNA sequences, and then utilize this
                  generalization to devise two algorithms for computing
                  local similarity according to our two suggested
                  metrics. Our algorithms run in O(m2n lg n) and O(m2n
                  lg n+n2m) time respectively, where m  n are the
                  lengths of the two given RNAs. Both algorithms can
                  work with any arbitrary scoring scheme.},
  user =	 {backofen}
}