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

• Erstellungsjahr: 2016

Zusammenfassung der Projektergebnisse

Die in molekularbiologischen Experimenten gewonnenen Daten (hauptsächlich genomische Sequenzen) sowie die daraus berechneten Daten (z.B. phylogenetische Netzwerke) 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 war es, häufig benutzte Algorithmen und Datenstrukturen in Bezug auf Platzeffizienz zu verbessern. Es wurde dazu u.a. an aktuelle Forschungsthemen wie ultra-kleine Datenstrukturen (engl. succinct data structures) und Externspeicher-Datenstrukturen angeknüpft. Bei ultra-kleine Datenstrukturen geht es darum, die Daten so abzuspeichern, dass das theoretisch erreichbare Minimum an Platz asymptotisch erreicht wird. Trotzdem sollen die Datenstrukturen eine reichhaltige Auswahl schneller Operationen auf den Daten zur Verfügung stellen, im Falle von Textindizes zum Beispiel die Suche nach Mustern. Externspeicher-Datenstrukturen versuchen hingegen, die Anzahl der Speichertransfers zwischen dem Hauptspeicher und der Festplatte zu minimieren. In beiden Bereichen konnten neue Ergebnisse erzielt werden. Neben diesen theoretischen Fortschritten lag ein Schwerpunkt dieses Projekts auf der effizienten Implementierung der neu entworfenen Datenstrukturen und Algorithmen (algorithm engineering) und der darauf folgenden Integration in bestehende Algorithmen-Bibliotheken.

Projektbezogene Publikationen (Auswahl)

• CST++. In: E. Chavez, S. Lonardi (Hrsg.): Proceedings of the 17th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS 6393, 322–333. Springer, 2010
  E. Ohlebusch, J. Fischer, S. Gog
  
• Compact Representation of Posets. In: T. Asano, S. Nakano, O. Watanabe (Hrsg.): Proceedings of the 22nd International Symposium on Algorithm and Computation (ISAAC), LNCS 7074, 302–311. Springer, 2011
  A. Farzan, J. Fischer
  
• LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations. Theoretical Computer Science 459(1), 26–41, 2012
  J. Barbay, J. Fischer, G. Navarro
  (Siehe online unter https://doi.org/10.1016/j.tcs.2012.08.010)
• Inducing Suffix and LCP Arrays in External Memory. In: Proc. ALENEX, 88–102. SIAM, 2013
  T. Bingmann, J. Fischer, V. Osipov
  
• Sparse Suffix Tree Construction in Small Space. In: F.V. Fomin et al. (Hrsg.): Proceedings of the 40th International Symposium on Automata, Languages and Programming (ICALP, Part I), LNCS 7965, 148–159. Springer, 2013
  . Bille, J. Fischer, I. L. Gørtz, T. Kopelowitz, B. Sach, H. W. Vildhøj
  
• GLOUDS: Representing Tree-Like Graphs. Journal of Discrete Algorithms
  J. Fischer, D. Peters
  (Siehe online unter https://doi.org/10.1016/j.jda.2015.10.004)