bioRxiv2019
The rise of whole-genome shotgun sequencing (WGS) has enabled numerous breakthroughs in large-scale comparative genomics research. However, the size of genomic datasets has grown exponentially over the last few years, leading to new challenges for traditional streaming algorithms. Modern petabyte-sized genomic datasets are difficult to process because they are delivered by high-throughput data streams and are difficult to store. As a result, many traditional streaming problems are becoming increasingly relevant. One such problem is the task of constructing a maximally diverse sample over a data stream. In this regime, complex sampling procedures are not possible due to the overwhelming data generation rate. In theory, the best diversity sampling methods are based on a simple greedy algorithm that compares the current sequence with a large pool of sampled sequences and decides whether to accept or reject the sequence. While these methods are elegant and optimal, they are largely confined to the theoretical realm because the greedy procedure is too slow in practice. While there are many methods to identify common elements in data streams efficiently, fast and memory-efficient diversity sampling remains a challenging and fundamental data streaming problem with few satisfactory solutions. In this work, we bridge the gap with RACE sampling, an online algorithm for diversified sampling. Unlike random sampling, which samples uniformly, RACE selectively accepts samples from streams that lead to higher sequence diversity. At the same time, RACE is as computationally efficient as random sampling and avoids pairwise similarity comparisons between sequences. At the heart of RACE lies an efficient lookup array constructed using locality-sensitive hashing (LSH). Our theory indicates that an accept/reject procedure based on LSH lookups is sufficient to obtain a highly diverse subsample. We provide rigorous theoretical guarantees for well-known biodiversity indices and show that RACE can nearly double the Shannon and Simpson indices of a genetic sample in practice, all while using the same resources as random sampling. We also compare RACE against Diginorm and coreset-based diversity sampling methods and find that RACE is faster and more memory efficient. Our algorithm is straightforward to implement, easy to parallelize, and fast enough to keep pace with the overwhelming data generation rates. We expect that as DNA sequence data streams become more mainstream and faster, RACE will become an essential component for many applications.1