Skip Navigation



Bioinformatics Advance Access published online on April 23, 2009
Bioinformatics, doi:10.1093/bioinformatics/btp275
This Article
Right arrow Advance Access manuscript (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.
Right arrow Search for Related Content
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 Data Sets Using Sparse Suffix Arrays

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

Department of Computer Science1, Department of Molecular Biology2, Department of Ecology and Evoluationary Biology3, Lewis-Sigler Institute for Integrative Genomics4, and Howard Hughes Medical Institute5, Princeton University, Princeton, New Jersey 08544, USA

*To whom correspondence should be addressed. Zia Khan and Mona Singh, E-mail: zkhan{at}princeton.edu, zkhan{at}cs.princeton.edu, mona{at}cs.princeton.edu


  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: (1) seeding alignments of high-throughput reads for genome assembly and (2) designating anchor points for genome-genome comparisons.

Results: We introduce a new algorithm for finding MEMs. The algorithm leverages a sparse suffix array, a text index that stores every Kth position of the text. In contrast to a full text index that stores every position of the text, a sparse suffix array 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 larger 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

Associate Editor: Prof. John Quackenbush

Received on January 28, 2009; revised on March 31, 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.