Versatile and declarative dynamic programming using pair algebras
Related Experiment Video
Updated: Aug 16, 2026

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
Published on: March 18, 2019
Peter Steffen1, Robert Giegerich
1Faculty of Technology, Bielefeld University, Postfach 10 01 31, 33501 Bielefeld, Germany. psteffen@techfak.uni-bielefeld.de
Background:
Dynamic programming is a widely used programming technique in bioinformatics. In sharp contrast to the simplicity of textbook examples, implementing a dynamic programming algorithm for a novel and non-trivial application is a tedious and error prone task. The algebraic dynamic programming approach seeks to alleviate this situation by clearly separating the dynamic programming recurrences and scoring schemes.
Results:
Based on this programming style, we introduce a generic product operation of scoring schemes. This leads to a remarkable variety of applications, allowing us to achieve optimizations under multiple objective functions, alternative solutions and backtracing, holistic search space analysis, ambiguity checking, and more, without additional programming effort. We demonstrate the method on several applications for RNA secondary structure prediction.
Conclusion:
The product operation as introduced here adds a significant amount of flexibility to dynamic programming. It provides a versatile testbed for the development of new algorithmic ideas, which can immediately be put to practice.
Related Concept Videos
Statically Indeterminate Problem Solving
Algebraic Expressions
Castigliano's Theorem: Problem Solving
Lagrange Multipliers: Problem Solving
SFG Algebra
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
Synthetic Disvision of Polynomials
