Algebraic Dynamic Programming for Set Data Types

and Automatic Derivation of Outside Grammars from their Inside Progenitors

In our paper on ADP for Set Data Types (Höner zu Siederdissen, Prohaska, and Stadler 2014), we develop a theory of dynamic programming over unordered set data types. This includes algorithms like the travelling salesman problem and finding optimal Hamiltonian paths.

In addition, we lay the groundwork for automatic calculation of Outside grammars from their Inside progenitors. This means that we can now, given any Inside grammar, calculate its Outside version.

Armed with these new tools, we develop an algorithm that calculates the optimal minimum-weight Hamiltonian path for the genes in the Hox gene cluster. In addition, we calculate the full probability matrix for the genes, an determine the maximum accuracy solutions.

Implementation

The machinery for the above problem is implemented in ADPfusion. Thanks to the generic structure of the ADPfusion library, this is possible without having to modify the library itself! Thereby, the ADPfusion-Set extension can also serve as a template on how to extend ADPfusion for other ``more exotic’’ DP problems.

We will, however, release a fully integrated version of ADPfusion in the coming weeks, to simplify usage.

Sources

Paper and Appendix

current devel version of ADPfusion

ADPfusion-Set for set problems

Hox data

local list of references

Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler. 2014. Dynamic programming for set data types. Brazilian sympositum on bioinformatics (BSB 2014). Lecture notes in bioinformatics 8826. Springer, Heidelberg. doi:10.1007/978-3-319-12418-6_8.