5 - Indexing, Search, and Retrieval of Sequences

Summary

Sequences, such as text documents or DNA sequences, can be indexed for searching and analysis in different ways depending on whether patterns that the user may want to search for (such as words in a document) are known in advance and on whether exact or approximate matches are needed.

When the sequence data and queries are composed of words (i.e., nonoverlapping subsequences that come from a fixed vocabulary), inverted files built using B+-trees or tries (Section 5.4.1) or signature files (Section 5.2) are often used for indexing. When, on the other hand, the sequence data do not have easily identifiable word boundaries, other index structures, such as suffix trees (Section 5.4.2), or filtering schemes, such as ρ-grams (Section 5.5.4), may be more applicable.

In this section, we first discuss inverted files and signature files that are commonly used for text document retrieval. We then discuss data structures and algorithms for more general exact and approximate sequence matching.

INVERTED FILES

An inverted file index [Harman et al., 1992] is a search structure containing all the distinct words (subpatterns) that one can use for searching. Figure 5.1(a) shows the outline of the inverted file index structure:

▪ A word (or term) directory keeps track of the words that occur in the database. For each term, a pointer to the corresponding inverted list is maintained. In addition, the directory records the length of the corresponding inverted list. This length is the number of documents containing the term.