Method and system for the assembly of a whole genome using a shot-gun data set

A method for generating a consensus nucleotide sequence corresponding to a nucleotide sequence in a genome from a shot-gun data set comprising a plurality of fragments comprising nucleotide sequence data selected at random from a genome that corresponds to nucleotide sequences of the genome, said shot-gun data set further comprising mate pair data, wherein a mate pair comprises a pair of end reads collected from both ends of an insert and a distance measure indicating the distance between said pair of end reads, such that said consensus nucleotide sequence comprises a nucleotide sequence of said genome in machine-readable form, said method comprising the steps of:

• (a) identifying a first set of fragments from said shot-gun data set, wherein each fragment in said first set contains a screen item;
• (b) generating a second set of fragments by excluding said first set from said shot-gun data set;
• (c) generating an overlap data set by performing a plurality of pair-wise comparisons between said fragments of said second set to determine the presence of similar nucleotide sequences in each pair, wherein said second set does not contain said screen items;
• (d) performing a graph reduction on said overlap data set, thereby producing a minimal subgraph;
• (e) designating a plurality of non-branching portions of said minimal subgraph as a plurality of unitigs;
• (f) generating a scaffold, wherein said scaffold comprises the relative order of said plurality of unitigs with respect to one another calculated from said mate pair data;
• (g) generating at least one multi-alignment calculated from said scaffold;
• and
• (h) generating a consensus sequence calculated from said multi-alignment.