A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays.

TitleA practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays.
Publication TypeJournal Articles
Year of Publication2009
AuthorsKhan Z, Bloom JS, Kruglyak L, Singh M
JournalBioinformatics
Volume25
Issue13
Pagination1609-16
Date Published2009 Jul 1
ISSN1367-4811
Keywordsalgorithms, Base Sequence, Genomics, sequence alignment, Sequence Analysis, DNA
Abstract

MOTIVATION: High-throughput sequencing technologies place ever increasing demands on existing algorithms for sequence analysis. Algorithms for computing maximal exact matches (MEMs) between sequences appear in two contexts where high-throughput sequencing will vastly increase the volume of sequence data: (i) seeding alignments of high-throughput reads for genome assembly and (ii) designating anchor points for genome-genome comparisons.

RESULTS: We introduce a new algorithm for finding MEMs. The algorithm leverages a sparse suffix array (SA), a text index that stores every K-th position of the text. In contrast to a full text index that stores every position of the text, a sparse SA occupies much less memory. Even though we use a sparse index, the output of our algorithm is the same as a full text index algorithm as long as the space between the indexed suffixes is not greater than a minimum length of a MEM. By relying on partial matches and additional text scanning between indexed positions, the algorithm trades memory for extra computation. The reduced memory usage makes it possible to determine MEMs between significantly longer sequences.

AVAILABILITY: Source code for the algorithm is available under a BSD open source license at http://compbio.cs.princeton.edu/mems. The implementation can serve as a drop-in replacement for the MEMs algorithm in MUMmer 3.

DOI10.1093/bioinformatics/btp275
Alternate JournalBioinformatics
PubMed ID19389736
PubMed Central IDPMC2732316
Grant ListGM 076275 / GM / NIGMS NIH HHS / United States
P50 GM 071508 / GM / NIGMS NIH HHS / United States
R37 MH 059520 / MH / NIMH NIH HHS / United States
T32 HG 003284 / HG / NHGRI NIH HHS / United States