Fast alignment filtering of nanopore sequencing reads using locality-sensitive hashing

摘要

We introduce a novel method to efficiently filter pairwise alignments between long, high-error reads. We demonstrate the efficiency of our method on long read datasets produced by Oxford Nanopore Technologies' MinION sequencer and Pacific Biosciences' RS II. Our method outperforms existing methods by an order of magnitude in both CPU runtime and main memory required. We further show that the performance of our method scales linearly with the total input sequence data, allowing us to perform pairwise read alignments without large cluster or cloud infrastructure for smaller genomes and make the alignment of whole-genome sequence tractable for larger genomes including humans. Our approach helps bridge the gap between sequence production and analysis, enabling both sequencing and assembly on a commodity laptop computer using the MinION system.