Compressed Suffix Trees: Design, Construction, and Applications

• Applicant: Professor Dr. Enno Ohlebusch
• Co-Applicant: Professor Mohamed Abouelhoda, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 206825075

• Final Report Year: 2017

Final Report Abstract

Wenn ein Text (z.B. die DNA-Sequenz eines Chromosoms) oder eine Sammlung von Texten (z.B. mehrere Chromosomen oder Genome) nicht oder nur selten verändert wird, dann lohnt es sich in vielen Anwendungen, den Text in einem Vorverarbeitungsschritt zu indizieren. Die erstellte Index-Datenstrukutur wird dann benutzt, um Anwendungen (z.B. den Vergleich zweier Genome) zu beschleunigen. Ein wesentliches Problem tritt bei der automatischen Verarbeitung von großen Datenmengen auf: Wenn der Index nicht mehr vollständig in den Hauptspeicher des benutzten Rechners passt, müssen Teile in den Sekundärspeicher ausgelagert werden. Da dies zu erheblichen Effizienzverlusten führt, war es das Ziel des Projektes, eine Bibliothek von grundlegenden Algorithmen zur Konstruktion von sehr kleinen Index-Datenstrukturen zu erstellen, die auch bei sehr großen Texten noch im Hauptspeicher gehalten werden können. Diese Software-Bibliothek steht nun öffentlich zur Verfügung. Die verwendete Index-Datenstruktur besteht aus vier Komponenten (einem FM-Index bestehend aus der Burrows-Wheeler Transformierten und deren Wavelet-Baum, einem Suffixarray, einem LCP-Array und einer sehr kleinen Repräsentation der Suffixbaumtopologie), und es wurden im Laufe des Projektes Konstruktionsalgorithmen für alle vier Komponenten entwickelt, die bisherige Algorithmen verbesserten. Als Anwendung dieser Index-Datenstruktur wurden neuartige Algorithmen zur Repeat-Analyse und zur Pangenomanalyse entwickelt, die mit signifikant weniger Hauptspeicher auskommen als bisherige Algorithmen.

Publications

• Space-efficient computation of maximal and supermaximal repeats in genome sequences. In Proc. 19th International Symposium on String Processing and Information Retrieval, volume 7608 of Lecture Notes in Computer Science, pages 99–110. Springer-Verlag, 2012
  T. Beller, K. Berger, and E. Ohlebusch
  
• Computing the longest common prefix array based on the Burrows-Wheeler transform. Journal of Discrete Algorithms, 18:22–31, 2013
  T. Beller, S. Gog, E. Ohlebusch, and T. Schnattinger
  
• Space-efficient construction of the Burrows-Wheeler transform. In Proc. 20th International Symposium on String Processing and Information Retrieval, volume 8214 of Lecture Notes in Computer Science, pages 5–16. Springer-Verlag, 2013
  T. Beller, M. Zwerger, S. Gog, and E. Ohlebusch
  
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel. Journal of Discrete Algorithms, 25:21–33, 2014
  Ohlebusch, Enno; Beller, Timo & Abouelhoda, Mohamed I.
  
• From theory to practice: Plug and play with succinct data structures. In Proc. 13th International Symposium on Experimental Algorithms, volume 8504 of Lecture Notes in Computer Science, pages 326–337. Springer, 2014
  Gog, Simon; Beller, Timo; Moffat, Alistair & Petri, Matthias
  
• Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform. Bioinformatics, 32(4):497–504, 2016
  Baier, Uwe; Beller, Timo & Ohlebusch, Enno
  
• A representation of a compressed de Bruijn graph for pan-genome analysis that enables search. Algorithms for Molecular Biology, 11:20, 2016
  Beller, Timo & Ohlebusch, Enno
  
• Space-efficient parallel construction of succinct representations of suffix tree topologies. Journal of Experimental Algorithmics, 22:1.1, 2017
  Baier, Uwe; Beller, Timo & Ohlebusch, Enno