Coverage-preserving sparsification of overlap graphs for long-read assembly

Read-overlap-based graph data structures play a central role in computing de novo genome assembly using long reads. Many assembly tools use the string graph model [Myers, Bioinformatics 2005] to sparsify overlap graphs. Graph sparsification improves accuracy by removing spurious and redundant connections. However, a graph model must be coverage-preserving, i.e., it must ensure that each chromosome can be spelled as a walk in the graph, given sufficient sequencing coverage. This property becomes even more important for diploid genomes, polyploid genomes and metagenomes where there is a risk of losing haplotype-specific information. We develop a novel theoretical framework under which the coverage-preserving properties of a graph model can be analysed. We first prove that de Bruijn graph and overlap graph models are guaranteed to be coverage-preserving. We also show that the standard string graph model lacks this guarantee. The latter result is consistent with the observation made in [Hui et al. ISIT16] that removal of contained reads during string graph construction can lead to coverage gaps. To remedy this, we propose practical heuristics that are well-supported by our theoretical results to sparsify overlap graphs. In our experiments conducted by using simulated long reads from HG002 human diploid genome, we find that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets. We tested the proposed heuristics for deciding which contained reads should be retained to avoid the coverage gaps. The proposed method retains a small fraction of contained reads (1 - 2%) and closes majority of the coverage gaps.