A max-margin model for efficient simultaneous alignment and folding of RNA sequences.

@article{citeulike:2966909, abstract = {MOTIVATION: 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. AVAILABILITY: Source code for RAF is available at:http://contra.stanford.edu/contrafold/.}, address = {Computer Science Department, Stanford University, Stanford, CA 94305, USA. chuongdo@cs.stanford.edu}, author = {Do, C. B. and Foo, C. S. and Batzoglou, S. }, citeulike-article-id = {2966909}, issn = {1460-2059}, journal = {Bioinformatics (Oxford, England)}, keywords = {rna, tool}, month = {July}, number = {13}, posted-at = {2008-07-06 07:33:45}, priority = {2}, title = {A max-margin model for efficient simultaneous alignment and folding of RNA sequences.}, url = {http://view.ncbi.nlm.nih.gov/pubmed/18586747}, volume = {24}, year = {2008} }

TY - JOUR ID - citeulike:2966909 L3 - citeulike-article-id:2966909 N2 - MOTIVATION: 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. AVAILABILITY: Source code for RAF is available at:http://contra.stanford.edu/contrafold/. IS - 13 JF - Bioinformatics (Oxford, England) SN - 1460-2059 AD - Computer Science Department, Stanford University, Stanford, CA 94305, USA. chuongdo@cs.stanford.edu TI - A max-margin model for efficient simultaneous alignment and folding of RNA sequences. VL - 24 KW - rna KW - tool AU - Do, CB AU - Foo, CS AU - Batzoglou, S PY - 2008/07/01/ UR - http://view.ncbi.nlm.nih.gov/pubmed/18586747 ER -