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

• Applicant: Professor Dr. Johannes Christian Fischer
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants