The GrammarProducts package

[Tags:gpl, library]

generalized Algebraic Dynamic Programming

An algebra of liner and context-free grammars.

This library provides the implementation of our theory of algebraic operations over linear and context-free grammars. Using algebraic operations, it is possible to construct complex dynamic programming algorithms from simpler atomic grammars.

Our most important contribution is the definition of a product of grammars which naturally leads to alignment-like algorithms on multiple tapes.

An efficient implementation of the resulting grammars is possible via the ADPfusion framework. The FormalGrammars library provides the required Template Haskell machinery. GramarProducts can be integrated as a plugin into the existing transformation from DSL to ADPfusion. Haskell users can just use the QQ function provided in the .QQ module.

Alternatively, the resulting grammars can also be pretty-printed in various ways (LaTeX, ANSI, Haskell module with signature and grammar).

The formal background can be found in two papers given in the README. The gADP homepage has further details, tutorials, examples.


[Skip to Readme]

Properties

Versions 0.0.0.2, 0.0.0.3, 0.0.0.4, 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.1.1.2
Change log changelog.md
Dependencies ADPfusion (==0.5.1.*), ansi-wl-pprint (==0.6.*), base (>=4.7 && <4.9), bytestring (==0.10.*), containers (==0.5.*), data-default (==0.5.*), FormalGrammars (>=0.2.1 && <0.3.1), lens (==4.*), newtype (==0.2.*), parsers (==0.12.*), PrimitiveArray (>=0.6.0.1 && <0.7.1), semigroups (>=0.15 && <0.19), template-haskell (==2.*), transformers (==0.4.*), trifecta (==1.5.*) [details]
License GPL-3
Copyright Christian Hoener zu Siederdissen, 2013-2016
Author Christian Hoener zu Siederdissen, 2013-2016
Maintainer choener@bioinf.uni-leipzig.de
Stability experimental
Category Formal Languages, Bioinformatics
Home page https://github.com/choener/GrammarProducts
Bug tracker https://github.com/choener/GrammarProducts/issues
Source repository head: git clone git://github.com/choener/GrammarProducts
Uploaded Mon Mar 14 00:36:40 UTC 2016 by ChristianHoener
Distributions NixOS:0.1.1.2
Downloads 1035 total (27 in the last 30 days)
Votes
0 []
Status Docs available [build log]
Last success reported on 2016-03-14 [all 1 reports]

Modules

[Index]

Flags

NameDescriptionDefaultType
examplesbuild the examples (only Needleman-Wunsch for now)DisabledManual

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Readme for GrammarProducts

Readme for GrammarProducts-0.1.1.2

GrammarProducts: Products of formal languages

Build Status

generalized Algebraic Dynamic Programming Homepage

An abstract algebra for linear and context-free grammars.

  1. Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
    Product Grammars for Alignment and Folding
    2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
    paper
  2. Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
    How to Multiply Dynamic Programming Algorithms
    2013, Brazilian Symposium on Bioinformatics (BSB 2013)
    Lecture Notes in Bioinformatics 8213. Springer, Heidelberg.
    paper preprint

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
http://www.bioinf.uni-leipzig.de/~choener/