Parallel Implementation of Predicting RNA using LR Parsing in MPI

RNA secondary structure prediction is a core task to find out the relationship between it's structure and function. Methods based on grammars, dynamic programming, matching and evolutionary algorithms have been developed for modeling and analysis of RNA secondary structure. Particularly, a Stochastic Context Free Grammar (SCFG) for parsing can be used to drive a 2-D RNA secondary structure from a 1-D RNA sequence avoiding ambiguous grammars with multithreading model by distributing the conflicts among multiple threads. This intuitive multithreaded model for RNA prediction is not scalable to a longer RNA sequence. Currently, it only supports sequences up to 20 characters due to extensive use of memory to store intermediate parse trees, parsing actions, and states for handling large number of parsing conflicts. This paper presents a parallel implementation of LR parsing for predicting RNA secondary structure using Message Passing Interface (MPI) to be executed on large computing cluster to enhance the scalability and performance of finding a valid parse tree with maximum probability.