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

ABSTRACT:

Motivation

Read-overlap-based graph data structures play a central role in computing de novo genome assembly. Most long-read assemblers use Myers's string graph model to sparsify overlap graphs. Graph sparsification improves assembly contiguity by removing spurious and redundant connections. However, a graph model must be coverage-preserving, i.e. it must ensure that there exist walks in the graph that spell all chromosomes, 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.

Results

We develop a novel theoretical framework under which the coverage-preserving properties of a graph model can be analyzed. We first prove that de Bru

SUBMITTER: Jain C 

PROVIDER: S-EPMC10132763 | biostudies-literature | 2023 Mar

REPOSITORIES: biostudies-literature