HTTPS SSH

Algebraic Dynamic Programming (ADP) as an eDSL in Haskell

This repository contains an implementation of Algebraic Dynamic Programming (ADP) as Domain Specific Language which is embedded into the (general purpose) language Haskell. The implementation is also called Haskell-ADP.

Haskell-ADP uses the technique of parser combinators.

The subdirectory examples contains several Haskell-ADP programs that use different variants of parser combinators.

Literature

Most of the combinators and examples are published in:

Abstract:

Dynamic programming is a classical programming technique, applicable in a wide variety of domains such as stochastic systems analysis, operations research, combinatorics of discrete structures, flow problems, parsing of ambiguous languages, and biosequence analysis. Little methodology has hitherto been available to guide the design of such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are difficult to construct, error-prone to implement, and, in nontrivial applications, almost impossible to debug completely. This article introduces a discipline designed to alleviate this problem. We describe an algebraic style of dynamic programming over sequence data. We define its formal framework, based on a combination of grammars and algebras, and including a formalization of Bellman's Principle. We suggest a language used for algorithm design on a convenient level of abstraction. We outline three ways of implementing this language, including an embedding in a lazy functional language. The workings of the new method are illustrated by a series of examples drawn from diverse areas of computer science.

See also the example source code for additional references.

Bellman's GAP Café also contains a bibliography of ADP related publications.

Files

Combinators

  • ADPCombinators.lhs - Basic set of ADP combinators for single-track programs
  • ADPTriCombinators.lhs - Variation on the tabulation method
  • TTCombinators.lhs - Combinators for a restricted set of two-track programs (i.e. alignment style algorithms)
  • Parser.lhs - Two-track combinators as used by RNAhybrid

Single- or two-track refers to the number of input tracks - i.e. a single- or two-track program works one or two input sequences/strings.

Examples

Use of ADPCombinators.lhs

  • ElMamun.lhs - Optimization of terms regarding the use of parentheses
  • MatrixMult.lhs - Optimal matrix chain multiplication
  • LocSim.lhs - Optimal local alignment (using a similarity score model) while using the trick x$rev(y) to encode two-track input as single-track input
  • AffineLocSim.lhs - Optimal local alignment with affine gap costs
  • AffineGlobSim.lhs - Optimal global alignment with affine gap costs

Use of ADPTriCombinators.lhs

  • Nussinov.lhs - The Nussinov (1978) algorithm for secondary structure prediction
  • ShapeCombinatorics.lhs - Shape analyses of RNA sequences (where shape are classes of RNA secondary structures)
  • Zuker.lhs - RNA secondary structure folding algorithm by Zuker (1981)
  • CanonicalRNA.lhs - Complete suboptimal folding of canonical RNA structures
  • CanonicalRNAnoDangle.lhs - Complete suboptimal folding of canonical RNA structures (no dangling bases)

Use of TTCombinators.lhs

  • NeedlemanWunsch.lhs - The Needleman-Wunsch Algorithm for computing the global sequence alignment
  • Waterman.lhs - Quadratic runtime variant of the above algorithm with a simple cost function
  • SmithWaterman.lhs - Local alignment variant (Smith-Waterman Algorithm)
  • ShortInLong.lhs - Local alignment variant
  • Gotoh.lhs - Variant with affine gap costs (Gotoh 1982)
  • Canon.lhs - Canonical alignments

Use of Parser.lhs

  • RNAhybrid.lhs - Prediction of microRNA/target duplexes as in RNAhybrid

Examples

$ ghci examples/ElMamun.lhs 
*ElMamun> bill seller "1+2*3*4+5"
[81]
*ElMamun> bill (seller***prettyprint) "1+2*3*4+5"
[(81,"((1+2)*(3*(4+5)))"),(81,"(((1+2)*3)*(4+5))")]
*ElMamun> bill (seller***count) "1+2*3*4+5"
[(81,2)]

$ ghc -iexamples examples/RNAhybrid.lhs
$ ghci -iexamples examples/RNAhybrid.lhs
Prelude RNAhybrid> hybridise (mfe***prettyprint) ("gcauggcugauauuaugcaacaauucuaccucagcccugagcugcg", "ugagguaguagguuguauagu")
[(-18.1,(5,"G   GA      G     AU  U"," GCU  UAUUAU CAACA  UC "," UGA  GUAGUA GUUGU  AG ","    G       G     AU  U"))]

Contact

Especially for questions regarding this repository contact:

Georg Sauthoff <gsauthof@techfak.uni-bielefeld.de>

You can also contact the authors of the referenced literature (see the first page of each paper for contact details).