  Some recent results have introduced external-memory algorithms to compute
self-indexes of a set of strings, mainly via computing the Burrows-Wheeler
Transform (BWT) of the input strings. The motivations for those results stem
from Bioinformatics, where a large number of short strings (called reads) are
routinely produced and analyzed. In that field, a fundamental problem is to
assemble a genome from a large set of much shorter samples extracted from the
unknown genome. The approaches that are currently used to tackle this problem
are memory-intensive. This fact does not bode well with the ongoing increase in
the availability of genomic data. A data structure that is used in genome
assembly is the string graph, where vertices correspond to samples and arcs
represent two overlapping samples. In this paper we address an open problem: to
design an external-memory algorithm to compute the string graph.
