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
