Reducing storage requirements for biological sequence comparison

Motivation: Comparison of nucleic acid and protein sequences is a fundamental tool of modern bioinformatics. A dominant method of such string matching is the \seed-and-extend" approach, in which occurrences of short subsequences called \seeds " are used to search for potentially longer matches in a large database of sequences. Each such potential match is then checked to see if it extends beyond the seed. To be eective, the seed-and-extend approach needs to catalogue seeds from virtually every substring in the database of search strings. Projects such as mammalian genome assemblies and large-scale protein matching, however, have such large sequence databases that the resulting list of seeds cannot be stored in RAM on a single computer. This signicantly slows the matching process. Results: We present a simple and elegant method in which only a small fraction of seeds, called \minimizers", needs to be stored. Using minimizers can speed up string-matching com-putations by a large factor while missing only a small fraction of the matches found using all seeds