Anincreasingnumberofstructuralhomologysearchtools,mostlybasedonprofilestochasticcontext-freegrammars(SCFGs)havebeenrecentlydevelopedforthenon-codingRNAgeneidentification.SCFGscanincludestatisticalbiasesthatoftenoccurinRNAsequences,necessarytoprofilespecificRNAstructuresforstructuralhomologysearch.Inthispaper,asuccinctstochasticgrammarmodelisintroducedforRNAthathascompetitivesearcheffectiveness.Moreimportantly,theprofilingmodelcanbeeasilyextendedtoincludepseudoknots,structuresthatarebeyondthecapabilityofprofileSCFGs.Inaddition,themodelallowsheuristicstobeexploited,resultinginasignificantspeed-upfortheCYKalgorithm-basedsearch.
