Compressed Suffix Trees: Design, Construction, and Applications

压缩后缀树：设计、构造和应用

• 批准号: 206825075
• 负责人: Professor Dr. Enno Ohlebusch
• 金额: --
• 依托单位: Institut für Theoretische Informatik (ITI)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2012
• 资助国家: 德国
• 起止时间: 2011-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/206825075?language=en
• 关键词: Compressed; Suffix; Trees; Design; Construction

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.

如果文本（例如染色体的DNA序列）或文本集合（例如多个染色体或基因组）不改变或很少改变，则在许多应用中，值得在预处理步骤中索引文本。然后使用构建的索引数据结构来加速应用程序（例如，两个基因组的比较）。当自动处理大量数据时，会出现一个基本问题：如果索引不完全适合计算机的主内存，则必须将其部分交换回辅助存储。由于这会导致相当大的效率损失，因此该项目的目标是开发一个基本算法库，以构建简洁的索引数据结构，即使文本非常大，也可以保存在主存中。该库还应提供这些索引数据结构的应用算法。此外，在合作项目中，算法和数据结构应集成到软件系统CoCoNUT中。

项目成果

Computing the Burrows-Wheeler transform of a string and its reverse in parallel

并行计算字符串的 Burrows-Wheeler 变换及其逆变换

• DOI: 10.1016/j.jda.2013.06.002
• 发表时间: 2014
• 期刊: J. Discrete Algorithms
• 作者: E. Ohlebusch;T. Beller;M. Abouelhoda
• 通讯作者: M. Abouelhoda

Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies

后缀树拓扑简洁表示的空间高效并行构建

• DOI: 10.1145/3035540
• 发表时间: 2017
• 期刊: Journal of Experimental Algorithmics (JEA)
• 作者: U. Baier;T. Beller;E. Ohlebusch
• 通讯作者: E. Ohlebusch

Graphical pan-genome analysis with compressed suffix trees and the Burrows-Wheeler transform

• DOI: 10.1093/bioinformatics/btv603
• 发表时间: 2016-02-15
• 期刊: BIOINFORMATICS
• 影响因子: 5.8
• 作者: Baier, Uwe;Beller, Timo;Ohlebusch, Enno
• 通讯作者: Ohlebusch, Enno