Skip Navigation


Bioinformatics Advance Access originally published online on April 23, 2009
Bioinformatics 2009 25(13):1609-1616; doi:10.1093/bioinformatics/btp275
This Article
Right arrow Full Text
Right arrow Full Text (Print PDF)
Right arrow Supplementary Data
Right arrow All Versions of this Article:
25/13/1609    most recent
btp275v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Khan, Z.
Right arrow Articles by Singh, M.
PubMed
Right arrow PubMed Citation
Right arrow Articles by Khan, Z.
Right arrow Articles by Singh, M.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

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

Zia Khan 1,2,*, Joshua S. Bloom 2,3, Leonid Kruglyak 2,4,5 and Mona Singh 1,2,*

1Department of Computer Science, 2Lewis-Sigler Institute for Integrative Genomics, 3Department of Molecular Biology, 4Department of Ecology and Evoluationary Biology and 5Howard Hughes Medical Institute, Princeton University, Princeton, New Jersey 08544, USA

*To whom correspondence should be addressed.


  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.

Contact: zkhan{at}cs.princeton.edu;mona{at}cs.princeton.edu

Supplementary information: Supplementary data are available at Bioinformatics online.

Associate Editor: John Quackenbush

Received on January 28, 2009; revised on March 3, 2009; accepted on April 19, 2009

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.