Bioinfo/Programming languages seminar - Christian Höner zu Siederdissen
The next speaker of the bioinfo seminar will be Christian Höner zu Siederdissen, visiting us form the notorious BeerInformatics(!) group (PI: Peter Stadler) at Leipzig University (Germany). His presentation (see abstract below) will be at LIX (bat Turing, Ecole Polytechnique), at 2:30 PM in Salle Philippe Flajolet.
Title: Generalized Algebraic Dynamic Programming: Theory and Applications in Bioinformatics, Linguistics, and Medieval History.
Abstract: Dynamic programming (DP) algorithms are pervasive in bioinformatics and linguistics (and more exotic domains) but typically implemented as ``one-shot’’ solutions.
In addition to just a growing number of applications, there seems to be a trend towards more complex algorithms as well. We recognize at least these degrees of increasing complexity and certain desiderata to control this complexity:
More refined search spaces which require larger sets of rules to describe. Less ad-hoc ways to design these improve confidence in construction.
The desire to calculate more than just a single optimal result, be it ensemble-style posterior probabilities or classified dynamic programming benefit from automatic code generation.
Many DP algorithms operate on sets, trees, or other non-string data structures. For these more complex structures, both theory and support for implementations are required.
On a more basic level, developers have to deal with writing code that should be free of bugs, maintainable, and sufficiently efficient.
In this talk I will provide a gentle introduction to generalized Algebraic Dynamic Programming, which simplifies design and implementation of dynamic programming algorithms considerably. Users of our system can combine individual algorithms like building blocks, have outside algorithms be derived fully automatically, design algorithms on a multitude of input structures (we currently provide implementations for strings, trees, and sets), and even go beyond context-free grammars.
During the talk I will draw examples from bioinformatics (RNA structure prediction with pseudoknots), linguistics (alignment of parse trees), and computational history (a peek into currently ongoing work).