Optimizing read reversals for sequence compression (Extended abstract)

New generation sequencing technologies produce massive data sets of millions of reads, making the compression of sequence read files an important problem. The sequential order of the reads in these files typically conveys no biologically significant information, providing the freedom to reorder them so as to facilitate compression. Similarly, for many problems the orientation of the reads (original or reverse complement) are indistinguishable from an information-theoretic perspective, providing the freedom to optimize the orientation of each read. In this paper, we introduce a class of algorithmic problems concerned with optimizing read ordering and orientation for sequence compression. We show that most of the interesting variants are hard, but provide heuristics yielding strong approximation guarantees. In particular, we give a linear time 2-approximation algorithm for the optimal ordering/ orientation under the prefix match criteria. Further, through experiments on a number of data sets, we demonstrate that this heuristic works well in practice. A prototype implementation of this 2-factor approximation is available at https://github.com/LaoZZZZZ/prefixMatching.