Logo du LIFL

Depuis le 1er janvier 2015 le LIFL et le LAGIS forment le laboratoire CRIStAL

  1. Actualités

Séminaire de

Robert Giegerich

17 novembre 2011
Amphi Turing, Bât M3

Enjoy Dynamic Programming in Bellman's GAP

(Joint work with Georg Sauthoff.)

Applications of the dynamic programming paradigm are ubiquitous computer science, and especially so in bioinformatics. The discipline of algebraic dynamic programming liberates programmers from cumbersome coding and debugging, as algorithms can be described on a declarative level of abstraction. Teaching DP algorithms becomes more rewarding, as crucial ideas are better exhibited in a more abstract representation. The algebraic discipline underlies a good number of bioinformatics tools, such as RNAshapes, RNAlishapes, RNAhybrid, PknotsRG, KnotInFrame, Locomotif and pKiss, some which are used widely.

Quite in contrast to this success, the proliferation of algebraic dynamic programming as a method remains marginal. It has been hindered by the fact that its original implementation was based on a Haskell-derived syntax and provided only marginal compiler optimizations.

The recent Bellman's GAP programming system provides a declarative language GAP-L with a Java-style syntax, designed to create dynamic programming algorithms over sequence data in algebraic style. The Bellman's GAP compiler generates code which is competitive to hand-coded DP recurrences, and arguably more reliable. It provides numerous features that would require considerable skill and effort in hand-coding, such as k-best analysis, full or stochastic backtracing, classified dynamic programming and algebra products, code generation for parallel hardware, and analysis of asymptotic space and runtime efficiency, including the consideration of space-time trade-offs. Several bioinformatics tools have been re-implemented in Bellman's GAP by a mere change of syntax, with a considerable gain in efficiency.

If you have been a hard-coding dynamic programmer, try Bellman's GAP. It may bring joy into your life.


UMR 8022 - Laboratoire d'Informatique Fondamentale de Lille - Copyright © 2012 Sophie TISON - Crédits & Mentions légales

Page respectant XHTML et CSS.

Pour tout commentaire / Comments and remarks : webmaster