Home Home Uni Bielefeld BiBiServ Practical Computer Science Technische Fakultaet Home Applications Education Advanced Compiler HMM Literature Team

Algebraic Dynamic Programming - Literature

  • ADP compiler:

    • P. Steffen. Compiling a Domain Specific Language for Dynamic Programming. PhD Thesis. University of Bielefeld, Germany. 145 pages. 2006. Download

    • P. Steffen and R. Giegerich. Table Design in Dynamic Programming. Information and Computation, 204(9), 2006. Download

    • R. Giegerich and P. Steffen. Challenges in the Compilation of a Domain Specific Language for Dynamic Programming. Proceedings SAC'06, 2006. Download


    • P. Steffen and R. Giegerich. Versatile and declarative dynamic programming using pair algebras. In BMC Bioinformatics, Vol 6, Number 224, 2005.
      [ download here ]

    • R. Giegerich, C. Meyer and P. Steffen. A Discipline of Dynamic Programming over Sequence Data. In Science of Computer Programming, Vol 51, 3:215-263, 2004
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich, C. Meyer, and P. Steffen. Towards a discipline of dynamic programming. In S. Schubert, B. Reusch, and N. Jesse, editors, Informatik bewegt, GI-Edition - Lecture Notes in Informatics, pages 3-44. Bonner Köllen Verlag, 2002.
      This is an almost tutorial style article, which thoroughly introduces the principles of ADP and illustrates their application with a series of examples from diverse areas.
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich and C. Meyer. Algebraic Dynamic Programming. In H. Kirchner and C. Ringeissen, editors, Algebraic Methodology And Software Technology, pages 349-364. LNCS 2422, 2002, © Springer-Verlag.
      This article gives a terse but complete introduction to ADP and then concentrates on formal aspects of program development with ADP. It shows how the ``tricks of the trade'' in dynamic programming can be described as formal transformations of ADP programs.
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich and P. Steffen. Implementing algebraic dynamic programming in the functional and the imperative programming paradigm. In E.A. Boiten and B. Möller, editors, Mathematics of Program Construction, pages 1-20. LNCS 2386, 2002, © Springer-Verlag.
      This article describes (some, but by no means all) essential translation techniques required to transform an ADP algorithm into an efficient functional or imperative program.
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich. A Systematic Approach to Dynamic Programming in Bioinformatics. Bioinformatics, 16:665-667, 2000.
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich. Explaining and Controlling Ambiguity in Dynamic Programming. In Proc. Combinatorial Pattern Matching (CPM), pages 46-59. Springer LNCS 1848, 2000.
      [ .ps.gz ] [ .pdf ]

    • R. Giegerich. A Declarative Approach to the Development of Dynamic Programming Algorithms, Applied to RNA Folding. Technical Report, Bielefeld University, 1998.
      [ .ps.gz ] [ .pdf ]

    • D. Evers and R. Giegerich. Systematic Dynamic Programming in Bioinformatics. presented as a tutorial at ISMB2000.

  • Applications:

    • S. Janssen, J. Reeder and R. Giegerich. Shape based indexing for faster search of RNA family databases. BMC Bioinformatics, 9, Pages:131, 2008
      [ download here ]

    • C. Theis, J. Reeder and R. Giegerich. KnotInFrame: prediction of -1 ribosomal frameshift events. Nucl. Acids Res., 36(18) , Pages:6013-20, 2008
      [ download article ]    [ try KnotInFrame ]

    • Reeder, Janina and Reeder, Jens and Giegerich, Robert: Locomotif: from graphical motif description to RNA motif search. Bioinformatics, 23(13) , Pages:i392, 2007
      [ download article ]    [ try Locomotif ]

    • J. Reeder, P. Steffen and R. Giegerich. pknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows. Nucleic Acids Res, 35(Web Server issue) , Pages:W320-4., 2007.
      [ download article ]    [ try pknotsRG ]

    • J. Krueger and M. Rehmsmeier. RNAhybrid: microRNA target prediction easy, fast, and flexible. Nucl. Acids. Res., 34(suppl_2) , Pages:W451-454, 2006
      [ download article ]    [ try RNAhybrid ]

    • B. Voss, R. Giegerich and M. Rehmsmeier. Complete probabilistic analysis of RNA shapes. BMC Biol, 4(1) , Pages:5, 2006
      [ download article ]

    • P. Steffen, B. Voss, M. Rehmsmeier, J. Reeder, and R. Giegerich. RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics, 22(4), 2006.
      [ download article ]    [ download RNAshapes ]

    • Janina Reeder, Peter Steffen, and Robert Giegerich. Effective ambiguity checking in biosequence analysis. In BMC Bioinformatics, Vol 6, Number 153, 2005.
      [ download here ]    [ supplementary material ]

    • Jens Reeder and Robert Giegerich. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. In BMC Bioinformatics, 5:104, 2004.
      [ download article ]    [ download pknotsRG ]

    • M. Rehmsmeier, P. Steffen, M. Höchsmann and R. Giegerich. Fast and effective prediction of micro{RNA}/target duplexes. In RNA, 10:1507-1517, 2004.
      [ download article ]    [ download RNAhybrid ]

    • R. Giegerich, B. Voss and M. Rehmsmeier. Abstract Shapes of RNA. In Nucleic Acids Research (NAR), Vol 32, 16:4843-4851, 2004.
      [ download here ]

    • C. Meyer and R. Giegerich. Matching and Significance Evaluation of Combined Sequence-Structure Motifs in RNA. Z.Phys.Chem., 216:193-216, 2002.
      This article describes an application of ADP in the domain of pattern matching in biological sequence data. The technique itself, however, is quite general. It includes nontrivial extensions to the ADP method, for example, parameterized tree patterns. The particular clue is that the pattern matcher can also be used to derive significance scores, which in turn allows to tune the pattern specificity on the high level of abstraction provided by ADP.
      [ .ps.gz ] [ .pdf ]

The documents contained in this page are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit written permission of the copyright holder.

| Author: psteffen | Date: 2009/06/30 11:23:56 |