Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction.
BACKGROUND
The well-known Sankoff algorithm for simultaneous RNA sequence alignment and folding is currently considered an ideal, but computationally over-expensive method. Available tools implement this algorithm under various pragmatic restrictions. They are still expensive to use, and it is difficult to judge if the moderate quality of results is because of the underlying model or to its imperfect implementation.


RESULTS
We propose to redefine the consensus structure prediction problem in a way that does not imply a multiple sequence alignment step. For a family of RNA sequences, our method explicitly and independently enumerates the near-optimal abstract shape space, and predicts as the consensus an abstract shape common to all sequences. For each sequence, it delivers the thermodynamically best structure which has this common shape. Since the shape space is much smaller than the structure space, and identification of common shapes can be done in linear time (in the number of shapes considered), the method is essentially linear in the number of sequences. Our evaluation shows that the new method compares favorably with available alternatives.


BACKGROUND
The new method has been implemented in the program RNAcast and is available on the Bielefeld Bioinformatics Server.


BACKGROUND
jreeder@TechFak.Uni-Bielefeld.DE, robert@TechFak.Uni-Bielefeld.DE SUPPLEMENTARY INFORMATION: Available at http://bibiserv.techfak.uni-bielefeld.de/rnacast/supplementary.html
Reeder
Jens
J
Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany. jreeder@TechFak.Uni-Bielefeld.DE
Giegerich
Robert
R
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D016384:Consensus Sequence; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000032:analysis / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid; D012984:Software
D012313:RNA