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

If a text (e.g. the DNA sequence of a chromosome) or a collection of texts (e.g. multiple chromosomes or genomes) does not or rarely change, then in many applications it is worthwhile to index the text in a preprocessing step. The constructed index data structure is then used to accelerate applications (e.g. the comparison of two genomes). A fundamental problem arises when a huge amount of data is processed automatically: If the index does not completely fit into the main memory of the computer, then parts of it must be swapped back into secondary storage. Since this results in a considerable loss in efficiency, it is the goal of the project to develop a library of basic algorithms to construct succinct index data structures that can be kept in main memory even if the text is very large. The library shall also provide application algorithms on these index data structures. Furthermore, in a cooperation project the algorithms and data structures shall be integrated into the software system CoCoNUT.

• DFG Programme: Research Grants
• International Connection: Australia, Egypt
• Participating Person: Dr. Simon Gog