Patent ID: 6714874
Filing Date: 2004-03-30
Classification: G16B,Y10S

Abstract:
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.