Private Shotgun DNA Sequencing: A Structured Approach

Current techniques in sequencing a genome allow a service provider (e.g. a sequencing company) to have full access to the genome information, and thus the privacy of individuals regarding their lifetime secret is violated. In this paper, we introduce the problem of private DNA sequencing and propose a sequencing scheme to keep the genome information private at the service provider. In this technique, rather than a single sequencer (i.e. sequencing machine), a set of multiple sequencers is used. Then to each sequencer, a set of DNA fragments belonging to a pool of individuals is assigned to be read. However, the assignment is such that each sequencer cannot reconstruct each individuals sequence. Still, when the results of the reads are collected at a data collector, the reconstruction is possible. To increase the ambiguity at the sequencers, we add the fragments of some known DNA molecules, which are still unknown to the sequencers, to the pool. In continue, we show that it is possible to recover the genome with provable privacy guarantees if the parameters are adjusted correctly.