Optical Local Alignment in RNA Secondary Structure

T. Liu and B. Schmidt (Singapore)


local alignment, Stochastic Context-free Grammar


Though not as abundant as proteins, RNA plays a crucial role in a wide variety of biological processes. Local similarity in the two dimensional shape of RNA molecules, rather than primary sequence represents the evolutionarily conserved feature. This article introduces a dynamic programming solution to the problem of local structural alignment of RNA sequences. It is based on Stochastic Context-free Grammars (SCFGs). An extended version of the Cocke-Younger-Kasami (CYK) algorithm for optimal local alignment is presented by introducing the entrance and exiting states. A comparison to other methods shows that our method achieves a higher accuracy than HMM-based and primary sequence based methods.

Important Links:

Go Back