Inhalt

•  
   Introduction
•  
  Background
•  
  Algebraic Dynamic Programming
•  
   ADP Formalism
•  
   History of ADP implementations
•  
   Ambiguity
•  
  Lost in folding space?
•  
  Background
•  
   Motivation
•  
   Goals of the evaluation
•  
   Methods
•  
   Free energy and partition function
•  
   Implementing the energy model
•  
   Model NoDangle
•  
   Model OverDangle
•  
   Model MicroState
•  
   Model MacroState
•  
   Signature and evaluation algebras
•  
  Results & Discussion
•  
   Data set
•  
   Technical Environment
•  
   Evaluation of models for MFE structure prediction
•  
   Evaluating models for partition function and related computations
•  
  Conclusion
•  
   Model comparison
•  
   Evaluation of further models
•  
   A new strategy for level-2 shape probabilities?
•  
   A word on longer sequences
•  
   Acknowledgments
•  
  RapidShapes
•  
  Introduction
•  
   Computational cost of probabilistic shape analysis
•  
   Outline of ideas
•  
  A method for faster shape probability computation
•  
   Basic problem: Shapes with a least T% probability
•  
   Analysis of the folding space partitioned by shape
•  
   Heuristic Shape selection
•  
   Asymptotics
•  
  Evaluation
•  
   Evaluation setup
•  
   Results on random data
•  
   Results on real data
•  
  Discussion
•  
   Speed-ups and brake-even points achieved
•  
   Problem variants
•  
   Implementation alternatives
•  
   Open problems
•  
   Acknowledgments
•  
  pKiss
•  
  Introduction
•  
   Biological relevance of pseudoknots in RNA structure
•  
   Folding pseudoknots
•  
   Typology of structures
•  
  Three strategies for kissing hairpin prediction
•  
   The combined power of canonization rules and non-ambiguous dynamic programming
•  
   Decomposition alternatives of the kissing hairpin motif
•  
   Strategy A – an O(n to the power of 4) time, quadratic space algorithm
•  
   Strategy B – an O(n to the power of 4) time, cubic space algorithm
•  
   Strategy C – an O(n to the power of 5) time, quadratic space algorithm
•  
  Algorithms
•  
   Algorithmic subtleties
•  
   Pseudoknot-recurrence of pknotsRG – csrPK
•  
   Recurrences of Strategy A – csrKH-A
•  
   Recurrences of Strategy B – csrKH-B
•  
   Recurrences of Strategy C – csrKH-C
•  
   Recurrences of Strategy D – csrKH-D
•  
  Implementation via Bellman's GAP
•  
   Signature
•  
   Grammar
•  
   Algebras
•  
  Evaluation
•  
   A piece of anecdotal evidence
•  
   Test set ``knot''
•  
   Comparing pKiss strategies to other prediction tools
•  
   Conclusion
•  
   Acknowledgments
•  
   Computation of McCaskill base-pair probabilities: an outside algorithm
•  
   Traditional algorithmic idea
•  
   A general scheme for ADP
•  
   Outside-in emulation
•  
   McCaskill base-pair probability computation
•  
   Extension 1: dangling bases
•  
   Extension 2: folding alignments
•  
   Evaluation
•  
   Correctness check
•  
   Comparing model variants
•  
   Run-time analysis
•  
   Conclusion
•  
   Covariance Models
•  
   Three contributions to Covariance Models
•  
  Faithful CM re-implementation in Bellman's GAP
•  
   Upward compilation in Bellman's GAP
•  
   Approving faithful re-implementation
•  
   Determine Infernal's guide-tree to construct identical state architecture.
•  
   Conclusion
•  
  Alternative semantics
•  
   Trace semantics
•  
   Structure semantics
•  
   Ambiguity compensation
•  
   Evaluation
•  
   Conclusion on the new semantics
•  
   Two Track Counting
•  
   Ambivalent Covariance Models
•  
   Evaluation
•  
   Conclusion
•  
   Bibliography
•  
  Appendices
•  
  Appendix A: Complete set of all 20 TDM generators.
•  
   Common Signature
•  
   TDM grammars
•  
   TDM algebras
•  
   Appendix B: Source code for pKiss pseudoknot non-terminals.