@inproceedings{backofen06:_local_align_rna_sequen_arbit_scorin_schem,
author = {Backofen, Rolf and
          Hermelin, Danny and
          Landau, Gad M.  and
          Weimann, Oren},
title = {Local Alignment of {RNA} Sequences with Arbitrary Scoring
         Schemes},
booktitle = {CPM06},
year = {2006},
doi = {10.1007/11780441_23},
volume = {4009},
user = {backofen},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
pages = {246-257},
editor = {Moshe Lewenstein and
          Gabriel Valiente},
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.}
}