FANGS: High speed sequence mapping for next generation sequencers

Sanchit Misra*, Ramanathan Narayanan, Simon Lin, Alok Nidhi Choudhary

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Next Generation Sequencing machines are generating millions of short DNA sequences (reads) everyday. There is a need for efficient algorithms to map these sequences to the reference genome to identify SNPs or rare transcripts and to fulfill the dream of personalized medicine. We present a Fast Algorithm for Next Generation Sequencers (FANGS), which dynamically reduces the search space by using q-gram filtering and pigeon hole principle to rapidly map 454-Roche reads onto a reference genome. FANGS is a sequential algorithm designed to find all the matches of a query sequence in the reference genome tolerating a large number of mismatches or insertions/deletions. Using FANGS, we mapped 50000 reads with a total of 25 million nucleotides to the human genome in as little as 23.3 minutes on a typical desktop computer. Through our experiments, we found that FANGS is upto an order of magnitude faster than the state-of-the-art techniques for queries of length 500 allowing 5 mismatches or insertion/deletions.

Original languageEnglish (US)
Title of host publicationAPPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing
Pages1539-1546
Number of pages8
DOIs
StatePublished - Jul 23 2010
Event25th Annual ACM Symposium on Applied Computing, SAC 2010 - Sierre, Switzerland
Duration: Mar 22 2010Mar 26 2010

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Other

Other25th Annual ACM Symposium on Applied Computing, SAC 2010
Country/TerritorySwitzerland
CitySierre
Period3/22/103/26/10

Keywords

  • 454 sequencers
  • next generation sequencers
  • sequence mapping

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'FANGS: High speed sequence mapping for next generation sequencers'. Together they form a unique fingerprint.

Cite this