Title: Multithreaded parsing for predicting RNA secondary structures

Authors: Muhammed S. Al-Mulhem

Addresses: Information and Computer Science Department, King Fahd University of Petroleum and Minerals (KFUPM), Dhahran 31261, Saudi Arabia

Abstract: Many computational approaches have been developed for modelling and analysing the RNA secondary structure. These approaches are based on diverse methods such as grammars, dynamic programming, matching and evolutionary algorithms. This paper proposes a new parsing algorithm for the prediction of RNA secondary structures. The proposed algorithm is based on the shift-reduce LR parsing algorithm for programming languages. It has two main contributions: it extends the LR parsing algorithm by using a Stochastic Context-Free Grammar (SCFG) instead of Context-Free Grammar (CFG) for parsing RNA secondary structures; it extends the LR parsing algorithm by using a multithreaded approach to handle the LR parsing conflicts resulting from the use of ambiguous grammars.

Keywords: SCFG; stochastic CFG; context-free grammar; multithreaded parsing; RNA secondary structure; bioinformatics; structure prediction.

DOI: 10.1504/IJBRA.2010.038741

International Journal of Bioinformatics Research and Applications, 2010 Vol.6 No.6, pp.609 - 621

Received: 17 Mar 2010
Accepted: 23 Jun 2010

Published online: 24 Feb 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article