  Genome sequencing is the basis for many modern biological and medicinal
studies. With recent technological advances, metagenomics has become a problem
of interest. This problem entails the analysis and reconstruction of multiple
DNA sequences from different sources. Shotgun genome sequencing works by
breaking up long DNA sequences into shorter segments called reads. Given this
collection of reads, one would like to reconstruct the original collection of
DNA sequences. For experimental design in metagenomics, it is important to
understand how the minimal read length necessary for reliable reconstruction
depends on the number and characteristics of the genomes involved. Utilizing
simple probabilistic models for each DNA sequence, we analyze the
identifiability of collections of M genomes of length N in an asymptotic regime
in which N tends to infinity and M may grow with N. Our first main result
provides a threshold in terms of M and N so that if the read length exceeds the
threshold, then a simple greedy algorithm successfully reconstructs the full
collection of genomes with probability tending to one. Our second main result
establishes a lower threshold in terms of M and N such that if the read length
is shorter than the threshold, then reconstruction of the full collection of
genomes is impossible with probability tending to one.
