Pairwise RNA Structure Comparison with Stochastic Context-Free Grammars
- 1 December 2001
- proceedings article
- Published by World Scientific Pub Co Pte Ltd in Pacific Symposium on Biocomputing
Abstract
Pairwise stochastic context-free grammars ("Pair SCFGs") are powerful tools for finding conserved RNA structures, but unconstrained alignment to Pair SCFGs is prohibitively expensive. We develop versions of the Pair SCFG dynamic programming algorithms that can be conditioned on precomputed structures, significantly reducing the time complexity of alignment. We have implemented these algorithms for general Pair SCFGs in software that is freely available under the GNU Public License.Keywords
This publication has 0 references indexed in Scilit: