Clustering Billions of Reads for DNA Data Storage
Storing data in synthetic DNA offers the possibility of improving information density and durability by several orders of magnitude compared to current storage technologies. However, DNA data storage requires a computationally intensive process to retrieve the data. In particular, a crucial step in the data retrieval pipeline involves clustering billions of strings with respect to edit distance. Datasets in this domain have many notable properties, such as containing a very large number of small clusters that are well-separated in the edit distance metric space. In this regime, existing algorithms are unsuitable because of either their long running time or low accuracy. To address this issue, we present a novel distributed algorithm for approximately computing the underlying clusters. Our algorithm converges efficiently on any dataset that satisfies certain separability properties, such as those coming from DNA data storage systems. We also prove that, under these assumptions, our algorithm is robust to outliers and high levels of noise. We provide empirical justification of the accuracy, scalability, and convergence of our algorithm on real and synthetic data. Compared to the state-of-the-art algorithm for clustering DNA sequences, our algorithm simultaneously achieves higher accuracy and a 1000x speedup on three real datasets.
The paper presents a solution to a new type of clustering problem that has emerged from studies of DNA-based storage. Information is encoded within DNA sequences and retrieved using short-read sequencing technology. The short-read sequencer will create multiple short overlapping sequence reads and these have to be clustered to establish whether they are from the same place in the original sequence. The characteristics of the clustering problem is that the clusters are pretty tight in terms of edit distance (25 max diameter here - that seems quite broad given current sequencing error rates) but well separated from each other (much larger distance between them than diameter).
I thought this was an interesting and timely application. DNA storage is a hot topic and this kind of clustering is one of the computational bottlenecks to applying the method. I guess the methods presented will also be of general interest to the NIPS audience as an example of a massive data inference problem. 
The methods look appropriate for the task and the clustering speed achieved looks very impressive. 
The paper is well written and the problem, methods and results were easy to follow. 
My main concern with the work centred around how realistic is the generative model of the data. The substitution error rate and the insertion/deletion error rates are set to be the same parameter p/3. I think that current Illumina high-throughput sequencing is associated with much higher substitution error rates than insertion/deletion rates, I think  perhaps 100-fold less insertion/deletion than substitution for some illumina technologies. If insertion/deletion rates are much lower than substitution errors then perhaps the problem is less challenging than stated here since there would be less requirement for dealing with edit distances in the case insertions/deletions are rare. Also, for most technologies the error rates from sequencing are can be well established and therefore methods can be fine-tuned given knowledge of these parameters.