Extending the theory of Algebraic Dynamic Programming for applications in bioinformatics

• Applicant: Professor Dr. Rolf Backofen, since 4/2012
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 212686714

Dynamische Programmierung ist die Basis vieler Algorithmen im Bereich der Bioinformatik, wie etwa der Alignment-Methoden der komparativen Genomik oder der Algorithmen zur Vorhersage von RNA-Strukturen. Auf Grund neuer biologischer und informatischer Erkenntnisse werden diese Algorithmen kontinuierlich weiterentwickelt und für einzelne Forschungsvorhaben individuell angepasst. Daraus ergibt sich ein stetig steigender Bedarf diverse Varianten effizient und einfach zu implementieren, was insbesondere dadurch erschwert wird, dass die rekursive Struktur der Algorithmen mit zunehmender Spezialisierung komplexer wird. Algebraische Dynamische Programmierung (ADP) ist ein System, mit dem auf Dynamischer Programmierung basierende Algorithmen schnell, einfach und effizient entwickelt und implementiert werden können. In diesem Projekt wollen wir ADP so erweitern, dass es auf noch mehr Probleme angewendet werden kann, einfacher benutzbar und effizienter wird. Dazu werden wir zunächst Algorithmen zum Alignment von RNA-Pseudoknoten-Strukturen und zur Vorhersage von RNARNA- Interaktionen in ADP formulieren. Darüber hinaus wollen wir verschiedene neue Optimierungstechniken in das ADP-System integrieren. Das wird neben noch effizienteren Implementierungen auch zu einem allgemeineren Verständnis dieser Optimierungen beitragen so dass diese in Zukunft leichter auf neue Anwendungen übertragen werden können. Da probabilistische Modelle in der Bioinformatik immer weitere Verbreitung finden, werden wir ADP auch dahingehend erweitern, dass diese noch besser unterstützt werden.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Dr.-Ing. Mathias Möhl, until 3/2012