Compressed Suffix Trees: Design, Construction, and Applications

点击翻译按钮获取中文摘要

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.