Sequence Indexing
Thierry Lecroq, Mikaël Salson · 2022
The development of computer science and its computational capacities have caused for decades an exponential growth in the amount of data produced on a daily basis by fields ranging from climatology to geography and including medicine and sociology. For biological sequences, indexes are also used which, unlike the indexes at the end of the books, generally allow access to all the sequences and to all their occurrences. An intuitive solution to access all the suffixes of a text consists of storing each one of them in a tree, more precisely in a trie . Some structures can only be used to find out if a given sequence exists, whereas others make it possible to know the number of occurrences as well as the position of each of them. Theoretical time complexities provide less direct information than space complexities on practical effectiveness.