Patent

Title:

Methods and systems for data analysis using the Burrows-Wheeler Transform.

Inventors:

Markus J. Bauer, Anthony James Cox, Giovanna Rosone, Dirk Evers

Owner:

Illumina Cambridge Limited - Nr Saffron Walden, GB

Pub. No.:

US8798936B2 United States, US application serial no. 13/459,968. Patent No. 8,798,936, 5 August 2014 (Priority claimed from US201161499587P)
AU2012272161B2 Australia, Application granted 14 December 2015 (Priority claimed from US201161499587P)
EP2724278B1 European Patent Office, Application granted 16 September 2020 (Priority claimed from US201161499587P)
CA2839802C Canada Application granted 9 November 2021 (Priority claimed from US201161499587P)

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.

Patent with more than 240 citations on Scopus through the following related publications:

M. J. Bauer, A. J. Cox, G. Rosone: Lightweight BWT Construction for Very Large String Collections. CPM 2011. LNCS 6661 Springer 2011: 219-231. doi: 10.1007/978-3-642-21458-5_20
Markus J. Bauer, Anthony J. Cox, Giovanna Rosone: Lightweight algorithms for constructing and inverting the BWT of string collections. Theor. Comput. Sci. 483: 134-148 (2013), doi: 10.1016/j.tcs.2012.02.002.
A. J. Cox, M. J. Bauer, T. Jakobi, G. Rosone: Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform, Bioinformatics, Volume 28, Issue 11, June 2012, ISSN: 1367-4803, doi: 10.1093/bioinformatics/bts173