Classical indexes
Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, Alexandru I. Tomescu · Cambridge University Press eBooks · 2023
A full-text index for a string T is a data structure that is built once and that is kept in memory for answering an arbitrarily large number of queries on the position and frequency of substrings of T. Such queries can be used for speeding-up dynamic programming algorithms tailored for mapping reads to a reference genome – a fundamental task in the analysis of high-throughput sequencing data. This chapter covers the classical full-text indexes and the like, including k -mer indexes, suffix arrays, and suffix trees. Linear-time algorithms for suffix sorting and for basic genome analysis tasks, such as finding maximal exact matches, are also presented.