title: A max-margin model for efficient simultaneous alignment and folding of RNA sequences.
abstract: BACKGROUND
  The need for accurate and efficient tools for computational RNA structure analysis has become increasingly apparent over the last several years: RNA folding algorithms underlie numerous applications in bioinformatics, ranging from microarray probe selection to de novo non-coding RNA gene prediction. In this work, we present RAF (RNA Alignment and Folding), an efficient algorithm for simultaneous alignment and consensus folding of unaligned RNA sequences. Algorithmically, RAF exploits sparsity in the set of likely pairing and alignment candidates for each nucleotide (as identified by the CONTRAfold or CONTRAlign programs) to achieve an effectively quadratic running time for simultaneous pairwise alignment and folding. RAF's fast sparse dynamic programming, in turn, serves as the inference engine within a discriminative machine learning algorithm for parameter estimation.
  
  
  RESULTS
  In cross-validated benchmark tests, RAF achieves accuracies equaling or surpassing the current best approaches for RNA multiple sequence secondary structure prediction. However, RAF requires nearly an order of magnitude less time than other simultaneous folding and alignment methods, thus making it especially appropriate for high-throughput studies.
  
  
  BACKGROUND
  Source code for RAF is available at:http://contra.stanford.edu/contrafold/.
authors.affiliation: Computer Science Department, Stanford University, Stanford, CA 94305, USA. chuongdo@cs.stanford.edu
authors.forename: Chuong B
authors.initials: CB
authors.lastname: Do
authors.forename: Chuan-Sheng
authors.initials: CS
authors.lastname: Foo
authors.forename: Serafim
authors.initials: S
authors.lastname: Batzoglou
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D016384:Consensus Sequence / Q000235:genetics*; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000235:genetics* / Q000648:ultrastructure*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*
chemical_list: D012313:RNA