# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

# 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:

- Robert Giegerich, Carsten Meyer, and Peter Steffen. A discipline of dynamic programming over sequence data. Science of Computer Programming, 51(3):215-263, June 2004.

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).