Platzsparende Datenstrukturen für Anwendungen in der Bioinformatik: Bäume, Netzwerke und Sequenzen

• Antragsteller: Professor Dr. Johannes Christian Fischer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 162103459

Die in molekularbiologischen Experimenten gewonnenen Daten werden aufgrund neuer, schnellerer Labor-Technologien immer umfangreicher. Wegen ihrer Größe können diese Daten von Biologen und Bioinformatikern nur am Computer analysiert werden. Bestehende Softwaresysteme sind jedoch nicht oder nur unzureichend auf die stetig wachsenden Datenmengen vorbereitet. Ziel dieses Projektes ist es, von Biologen und Bioinformatikern häufig benutzte Algorithmen und Datenstrukturen in Bezug auf Platzeffizienz zu verbessern. Es wird dazu an das sehr aktuelle Forschungsthema der ultra-kleinen Datenstrukturen (engl. succinct data structures) angeknüpft. Hierbei geht es darum, die Daten so klein abzuspeichern, dass das theoretisch erreichbare Minimum an Platz asymptotisch erreicht wird. Trotzdem soll die Datenstruktur eine reichhaltige Auswahl schneller Operationen auf den Daten zur Verfügung stellen, im Falle von Textindizes zum Beispiel die Suche nach Mustern. Neben theoretischen Fortschritten liegt ein Schwerpunkt dieses Projekts auf der effizienten Implementierung der neu entworfenen Datenstrukturen und Algorithmen (algorithm engineering) und der darauf folgenden Integration in bestehende Bibliotheken.

• DFG-Verfahren: Sachbeihilfen