Parallel RNA secondary structure prediction using stochastic context-free grammars

摘要

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 a RNA sequence to a SCFG are highly compute-intensive. This has so far limited applications of SCFGs to relatively small problem sizes. In this paper we present the design of a parallel RNA sequence-structure alignment algorithm. Its implementation on parallel systems leads to significant runtime savings. This makes it possible to compute sequence-structure alignments of even the largest RNAs such as small subunit ribosomal rRNAs and long subunit ribosomal rRNAs in reasonable time.