Algebraic Dynamic Programming over general data structures.

Area of Science:

• Computational Biology
• Algorithm Theory
• Bioinformatics

Background:

• Dynamic programming (DP) algorithms are crucial for computational biology problems like sequence alignment, RNA folding, and Hidden Markov Models (HMMs).
• Classical Algebraic Dynamic Programming (ADP) theory separates state space traversal, scoring, and choice rules, utilizing yield parsers for ordered data.
• Traditional ADP covers only inside recursions, limiting its scope for ensemble property computations (e.g., HMM a posteriori probabilities, RNA partition functions).

Purpose of the Study:

• To generalize Algebraic Dynamic Programming (ADP) to a wider range of data structures by relaxing parsing constraints.
• To formalize the relationship between inside and outside variables within a unified framework.
• To demonstrate the derivation of outside recursions from inside decomposition schemes.

Main Methods:

• Relaxing the concept of parsing in ADP to accommodate broader data structures.
• Developing a generalized ADP framework that naturally integrates inside and outside recursions.
• Rephrasing existing algorithms for HMMs, sequence alignment, and RNA folding within the extended ADP.

Main Results:

• Demonstrated that outside recursions are generically derivable from inside decomposition schemes.
• Successfully rephrased algorithms for HMMs, pairwise sequence alignment, and RNA folding in the generalized ADP framework.
• Showcased the implementation of the Traveling Salesperson Problem (TSP) and shortest Hamiltonian path problem within the extended ADP, with an application to HOX gene cluster evolution.

Conclusions:

• The generalized ADP framework significantly enhances the ease of development and implementation of DP algorithms.
• This extended approach broadens the applicability of ADP to a diverse spectrum of computational problems.
• Facilitates the computation of ensemble properties by naturally incorporating outside recursions.