Detailseite
Projekt Druckansicht

Extending the theory of Algebraic Dynamic Programming for applications in bioinformatics

Antragsteller Professor Dr. Rolf Backofen, seit 4/2012
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2012 bis 2020
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 212686714
 
Erstellungsjahr 2019

Zusammenfassung der Projektergebnisse

In the course of the project we investigated how algebraic dynamic programming can be extended for tool building in the field of RNA bioinformatics. Addressing research questions in biology frequently makes it necessary to develop error-free, high-performance bioinformatic applications within a short time-frame. The Algebraic Dynamic Programming framework saves developer time by enabling a precise formulation of the algorithm and avoiding the implementation of repetitive code. We have added several new contributions in the area of ADP with Bellman’s GAP and with introducing sparsity in ADP. Moreover we published multiple novel tools in the field of RNA bioinformatics. CARNA uses information about the whole secondary structure ensemble, instead of a single thermodynamically stable secondary structure to compute high-quality sequence-structure alignments. ExpaRNA-P uses a data-driven sparsification approach to enable matching of secondary structure motifs for the whole structure ensemble of two RNAs. SPARSE is a sequence-structure alignment tool, based on LocARNA, that provides a substantial speed-up by using the sparsification approach of ExpaRNA-P. RNAscclust identifies homologous sequences in a set of input orthologs by clustering them with a graph-kernel approach. It can leverage the speedup introduced in SPARSE to align and cluster hundreds of potentially homologous sequences, allowing to annotate large transcriptomic datasets. We plan to use the novel extensions in the ADPfusion framework for future projects together with our collaboration partners in Leipzig Bioinformatics group. The availability of ADP-framework aids the development of novel tools in the field of bioinformatics. We learned that for gaining the best performance in practical scenarios, the DP improvements need to be combined with efficient algorithms at the top level of the analysis. For example, in the case of RNAscclust where we opted for a graph-kernel machine learning based approach to decide where to apply dynamic programming algorithms.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung