  Over the past two decades, a series of works have aimed at studying the
problem of genome assembly: the process of reconstructing a genome from
sequence reads. An early formulation of the genome assembly problem showed that
genome reconstruction is NP-hard when framed as finding the shortest sequence
that contains all observed reads. Although this original formulation is very
simplistic and does not allow for mate-pair information, subsequent
formulations have also proven to be NP-hard, and/or may not be guaranteed to
return a correct assembly.
  In this paper, we provide an alternate perspective on the genome assembly
problem by showing genome assembly is easy when provided with sufficient
mate-pair information. Moreover, we quantify the number of mate-pair libraries
necessary and sufficient for accurate genome assembly, in terms of the length
of the longest repetitive region within a genome. In our analysis, we consider
an idealized sequencing model where each mate-pair library generates pairs of
error free reads with a fixed and known insert size at each position in the
genome.
  Even in this idealized model, we show that accurate genome reconstruction
cannot be guaranteed in the worst case unless at least roughly R/2L mate-pair
libraries are produced, where R is the length of the longest repetitive region
in the genome and L is the length of each read. On the other hand, if (R/L)+1
mate-pair libraries are provided, then a simple algorithm can be used to find a
correct genome assembly easily in polynomial time. Although (R/L)+1 mate-pair
libraries can be too much to produce in practice, the previous bounds only hold
in the worst case. In our last result, we show that if additional conditions
hold on a genome, a correct assembly can be guaranteed with only O(log (R/L))
mate-pair libraries.
