  De novo genome assembly, i.e., rebuilding the sequence of an unknown genome
from redundant and erroneous short sequences, is a key but computationally
intensive step in many genomics pipelines. The exponential growth of genomic
data is increasing the computational demand and requires scalable,
high-performance approaches. In this work, we present a novel
distributed-memory algorithm that, from a string graph representation of the
genome and using sparse matrices, generates the contig set, i.e., overlapping
sequences that form a map representing a region of a chromosome. Using matrix
abstraction, we mask branches in the string graph and compute the connected
component to group genomic sequences that belong to the same linear chain
(i.e., contig). Then, we perform multiway number partitioning to minimize the
load imbalance in local assembly, i.e., concatenation of sequences from a given
contig. Based on the assignment obtained by partitioning, we compute the induce
subgraph function to redistribute sequences between processes, resulting in a
set of local sparse matrices. Finally, we traverse each matrix using
depth-first search to concatenate sequences. Our algorithm shows good scaling
with parallel efficiency up to 80% on 128 nodes, resulting in uniform genome
coverage and showing promising results in terms of assembly quality. Our contig
generation algorithm localizes the assembly process to significantly reduce the
amount of computation spent on this step. Our work is a step forward for
efficient de novo long read assembly of large genomes in a distributed memory.
