  In order to overcome the limitations imposed by DNA barcoding when
multiplexing a large number of samples in the current generation of
high-throughput sequencing instruments, we have recently proposed a new
protocol that leverages advances in combinatorial pooling design (group
testing) doi:10.1371/journal.pcbi.1003010. We have also demonstrated how this
new protocol would enable de novo selective sequencing and assembly of large,
highly-repetitive genomes. Here we address the problem of decoding pooled
sequenced data obtained from such a protocol. Our algorithm employs a
synergistic combination of ideas from compressed sensing and the decoding of
error-correcting codes. Experimental results on synthetic data for the rice
genome and real data for the barley genome show that our novel decoding
algorithm enables significantly higher quality assemblies than the previous
approach.
