DFG-Projekt:Extending the theory of Algebraic Dynamic Programming for applications in bioinformatics

Dynamic programming techniques are the basis of many algorithms used in bioinformatics, as for example the alignment methods used in comparative genomics or algorithms for RNA structure prediction. New insights lead to a continuous improvement of those algorithms and the development of many specialized variants. As a consequence, there is a growing demand to implement efficient prototypes of these algorithms quickly. This is in particular hard since for specialized problems the recursive structure of the corresponding dynamic programming algorithm becomes more and more complex. Algebraic Dynamic Programming (ADP) has been proven to be a suitable framework for the rapid development and efficient implementation of dynamic programming algorithms in bioinformatics. In this project we want to extend the theory of ADP to make it applicable to a larger class of problems, make it more efficient and more convenient to use. In particular, we want to formulate the problems of RNA pseudoknot alignment and RNA-RNA interactioin in ADP. Furthermore, we investigate how various optimization techniques that have been applied to dynamic programming algorithms recently, can be integrated in the ADP framework. This does not only lead to more efficient implementations, but also to a more precise and fundamental understanding of the optimizations and the circumstances under which they can be applied. Finally, we want to extend ADP with better support for probabilistic models which is essential for many applications.

Additional information: http://www.bioinf.uni-freiburg.de
contact person: Prof. Dr. Rolf Backofen
Phone: 0761 203 7461
Email: backofen@informatik.uni-freiburg.de

Start of project: 01.08.2015
End of project: 31.07.2018

Albert-Ludwigs-University Freiburg
Prof. Dr. Rolf Backofen
Bioinformatik
Prof. Dr. Rolf Backofen
Georges-Köhler-Allee 106
79110 Freiburg
Germany

Phone: +49 (0) 761-203-7461
Fax: +49 (0) 761-203-7462
Email: backofen@informatik.uni-freiburg.de
http://www.bioinf.uni-freiburg.de
Actual Research Report