Introduction
Basics
Context-free grammars
Earley-Parsing
RNA
Stochastic context-free grammars
SCFGs for secondary structure prediction
Semiring Parsing
RNA-RNA Interaction
Multiple context-free grammars
Stochastic multiple context-free grammars
Parsing of multiple context-free grammars
Approach
m-dimensional context-free grammars
Derivations and language
Effective dimension
Subgrammars
Rule Templates
Rule Templates in the Context of Secondary Structure Prediction
Inside and Outside Probabilities
A Grammar for RIP
Handling two molecules
GRIP
Secondary Structure Subgrammars
GSecStr—secondary structures in r
GSecStr—secondary structures in s
Earley-Parser for 2D-CFGs
Item-related definitions
One-dimensional preprocessing featuring an SCFG Earley parser
Outside probabilities in split grammars
Utilizing item values
Inside and outside probabilities
Rule probability estimates
Viterbi parses
Training with known structures
Implementation Design
Motivating observations
Item order
Choice of rule indices
Definition of
Correctness of
Item representation
Optimistic Prediction
Completion
Immediate Scanning
Getting rid of pre-scan items
Jumping over terminals
Late item value computation
Keeping probabilities in range—the 4-times-trick
Prediction
Scanning
Completion
Finalization
Reverse parsing
Item order
Item representation
Computation of reverse values
Scanning
Completion—first type
Completion—second type
4-times-trick
Results
jackRIP—our C++ implementation of a 2D-CFG parser
Target Machine
Runtime efficiency tests
RNA-RNA-interaction
Comparison with classical Earley parsing
Prediction quality tests
Test Data
Prediction method
Quality measures
Prediction results
Data from kato2009grammatical
Data from andronescu2005secondary
Summary
Conclusion
Future Work
Statistical Sampling based on trained models
Length-Dependency
Appendices
Pseudocode
Collected definitions
Invariants
1D-Earley-Forward
1D-Earley-Reverse
2D-Earley-Forward
2D-Earley-Reverse
Bibliography