|
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
Methodology:
-
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.
|
|
|