Fangs: High speed sequence mapping for next generation sequencers

Next Generation Sequencing machines are generating mil-lions 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 NextGeneration 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 algo-rithm designed to find all the matches of a query sequence in the reference genome tolerating a large number of mis-matches or insertions/deletions. Using FANGS, we mapped 50000 reads with a total of 25 million nucleotides to the hu-man 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