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.
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 *