@Article{Moehl:Will:Backofen:PKalign:JCB2010,
  author =	 {M{\"o}hl, Mathias and Will, Sebastian and Backofen, Rolf},
  title =	 {Lifting prediction to alignment of {RNA} pseudoknots},
  journal =	 JCB,
  issn = 	 {1066-5277},
  year =	 {2010},
  volume =	 {17},
  number =	 {3},
  pages =	 {429-42},
  user =	 {arichter},
  pmid =	 {20377455},
  doi = 	 {10.1089/cmb.2009.0168},
  abstract =	 {Prediction and alignment of RNA pseudoknot structures are 
                  NP-hard. Nevertheless, several efficient prediction 
                  algorithms by dynamic programming have been proposed for 
                  restricted classes of pseudoknots. We present a general 
                  scheme that yields an efficient alignment algorithm for 
                  arbitrary such classes. Moreover, we show that such an 
                  alignment algorithm benefits from the class restriction in 
                  the same way as the corresponding structure prediction 
                  algorithm does. We look at six of these classes in greater 
                  detail. The time and space complexity of the alignment 
                  algorithm is increased by only a linear factor over the 
                  respective prediction algorithm. For five of the classes, no 
                  efficient alignment algorithms were known. For the sixth, 
                  most general class, we improve the previously best 
                  complexity of O(n(5)m(5)) time to O(nm(6)), where n and m 
                  denote sequence lengths. Finally, we apply our fastest 
                  algorithm with O(nm(4)) time and O(nm(2)) space to 
                  comparative de-novo pseudoknot prediction.}
}