Parallel RNA sequence-structure alignment

Summary form only given. With the growing number of known RNA genes efficient and accurate computational analysis of RNA sequences is becoming increasingly important. Stochastic context-free grammars (SCFGs) are used as a popular tool to model RNA secondary structures. However, algorithms for aligning an RNA sequence to an SCFG are highly compute-intensive. This has so far limited applications of SCFGs to relatively small problem sizes. We present the design of a parallel RNA sequence-structure alignment algorithm. Its implementation on a PC cluster leads to significant runtime savings. This makes it possible to compute sequence-structure alignments of even the largest RNAs such as SSU rRNAs and LSU rRNAs in reasonable time.