@Article{Backofen:Chen:Hermelin:Local_and_gaps:JCB2007,
  author =	 {Backofen, Rolf and Chen, Shihyen and Hermelin, Danny and 
                  Landau, Gad M. and Roytberg, Mikhail A. and Weimann, Oren 
                  and Zhang, Kaizhong},
  title =	 {Locality and gaps in {RNA} comparison},
  journal =	 JCB,
  year =	 {2007},
  volume =	 {14},
  number =	 {8},
  pages =	 {1074-87},
  user =	 {backofen},
  pmid =	 {17985988},
  doi = 	 {10.1089/cmb.2007.0062},
  abstract =	 {Locality is an important and well-studied notion in 
                  comparative analysis of biological sequences. Similarly, 
                  taking into account affine gap penalties when calculating 
                  biological sequence alignments is a well-accepted technique 
                  for obtaining better alignments. When dealing with RNA, one 
                  has to take into consideration not only sequential features, 
                  but also structural features of the inspected molecule. This 
                  makes the computation more challenging, and usually 
                  prohibits the comparison only to small RNAs. In this paper 
                  we introduce two local metrics for comparing RNAs that 
                  extend the Smith-Waterman metric and its normalized version 
                  used for string comparison. We also present a global RNA 
                  alignment algorithm which handles affine gap penalties. Our 
                  global algorithm runs in O(m(2)n(1 + lg n/m)) time, while 
                  our local algorithms run in O(m(2)n(1 + lg n/m)) and 
                  O(n(2)m) time, respectively, where m <or= n are the lengths 
                  of the two given RNAs. These time complexities are 
                  comparable to the time complexity of any known RNA alignment 
                  algorithm. Furthermore, both our global and local algorithms 
                  are robust to selections of arbitrary scoring schemes.}
}