Methods and systems for data analysis using the Burrows Wheeler transform
AssigneeIllumina, Inc.
InventorsMarkus J. Bauer, Anthony James Cox, Giovanna Rosone, Dirk Evers
Life of this patent
Estimating the term…
Abstract
The present disclosure provides computer implemented methods and systems for analyzing datasets, such as large data sets output from nucleic acid sequencing technologies. In particular, the present disclosure provides for data analysis comprising computing the BWT of a collection of strings in an incremental, character by character, manner. The present disclosure also provides compression boosting strategies resulting in a BWT of a reordered collection of data that is more compressible by second stage compression methods compared to non-reordered computational analysis.
Claims80
A computer implemented method for determining the sequence of a nucleic acid comprising:
- a) receiving, using a processor, a collection of data strings of nucleic acid sequence data from a nucleic acid sequence dataset wherein said data strings comprise a plurality of characters,
- b) generating, using the processor, a first Burrows Wheeler transform on a first collection of characters of nucleic acid sequence data from the nucleic acid sequence dataset, wherein the first collection of characters comprises a first character from each of said data strings,
- c) merging, using the processor, an untransformed second collection of characters of nucleic acid sequence data from the nucleic acid sequence data set with the first Burrows Wheeler transformed characters to form a merged collection of characters, wherein the untransformed second collection of characters comprises a second character from each of said data strings,
- d) incrementally building, using the processor, a second Burrows Wheeler transform from the merged first Burrows Wheeler transformed characters and the untransformed second collection of characters, and
- e) determining, using the processor, the sequence of the nucleic acid based on the incrementally built Burrows Wheeler transform of the nucleic acid.
A computer implemented method for maximizing compression of a data set from the Burrows Wheeler transform comprising:
- a) receiving, using a processor, a collection of data strings from a dataset, wherein said data strings comprise a plurality of characters, wherein said dataset is a biopolymer sequence dataset, and wherein said biopolymer sequence data set comprises nucleic acid sequence data,
- b) generating, using the processor, a first Burrows Wheeler transform on a first collection of characters of nucleic acid sequence data from the dataset, wherein the first collection of characters comprises a first character from each of said data strings,
- c) adding, using the processor, a second collection of untransformed characters of nucleic acid sequence data from dataset to said first Burrows Wheeler transformed characters by incrementally merging the untransformed characters from the nucleic acid sequence data with the first Burrows Wheeler transformed characters, thereby generating a second Burrows Wheeler transform, wherein the second collection of characters comprises a second character from each of said data strings.
Dependencies are inferred from the claim text.