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

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

SUBMITTER: Khan Z 

PROVIDER: S-EPMC2732316 | biostudies-literature | 2009 Jul

REPOSITORIES: biostudies-literature