(A) Distribution of a lower-bound estimate for the length of all 1311 patterns in the Prosite DB. A vertical mark is shown at 6 (the k-mer length used for benchmarking). (B) The average runtime of the different stages of TetRex over the 116 Prosite patterns used in benchmarking for a variety of values of k. The leftmost bar makes no use of the index and therefore the entire runtime is devoted to linear scanning.