Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints.
BACKGROUND
We are interested in the problem of predicting secondary structure for small sets of homologous RNAs, by incorporating limited comparative sequence information into an RNA folding model. The Sankoff algorithm for simultaneous RNA folding and alignment is a basis for approaches to this problem. There are two open problems in applying a Sankoff algorithm: development of a good unified scoring system for alignment and folding and development of practical heuristics for dealing with the computational complexity of the algorithm.


RESULTS
We use probabilistic models (pair stochastic context-free grammars, pairSCFGs) as a unifying framework for scoring pairwise alignment and folding. A constrained version of the pairSCFG structural alignment algorithm was developed which assumes knowledge of a few confidently aligned positions (pins). These pins are selected based on the posterior probabilities of a probabilistic pairwise sequence alignment.


CONCLUSIONS
Pairwise RNA structural alignment improves on structure prediction accuracy relative to single sequence folding. Constraining on alignment is a straightforward method of reducing the runtime and memory requirements of the algorithm. Five practical implementations of the pairwise Sankoff algorithm - this work (Consan), David Mathews' Dynalign, Ian Holmes' Stemloc, Ivo Hofacker's PMcomp, and Jan Gorodkin's FOLDALIGN - have comparable overall performance with different strengths and weaknesses.
Dowell
Robin D
RD
Howard Hughes Medical Institute and Department of Genetics, Washington University School of Medicine, 4444 Forest Park Blvd, Box 8510, St. Louis, MO 63108, USA. rdd@mit.edu
Eddy
Sean R
SR
D000465:Algorithms; D020029:Base Pairing; D003198:Computer Simulation; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA; D013269:Stochastic Processes
D012313:RNA