title: Merging of multi-string BWTs with applications.
abstract: BACKGROUND
  The throughput of genomic sequencing has increased to the point that is overrunning the rate of downstream analysis. This, along with the desire to revisit old data, has led to a situation where large quantities of raw, and nearly impenetrable, sequence data are rapidly filling the hard drives of modern biology labs. These datasets can be compressed via a multi-string variant of the Burrows-Wheeler Transform (BWT), which provides the side benefit of searches for arbitrary k-mers within the raw data as well as the ability to reconstitute arbitrary reads as needed. We propose a method for merging such datasets for both increased compression and downstream analysis.
  
  
  RESULTS
  We present a novel algorithm that merges multi-string BWTs in [Formula: see text] time where LCS is the length of their longest common substring between any of the inputs, and N is the total length of all inputs combined (number of symbols) using [Formula: see text] bits where F is the number of multi-string BWTs merged. This merged multi-string BWT is also shown to have a higher compressibility compared with the input multi-string BWTs separately. Additionally, we explore some uses of a merged multi-string BWT for bioinformatics applications.
authors.affiliation: Department of Computer Science, 201 S. Columbia St. UNC-CH, Chapel Hill, NC 27599, USA.
authors.forename: James
authors.initials: J
authors.lastname: Holt
authors.affiliation: Department of Computer Science, 201 S. Columbia St. UNC-CH, Chapel Hill, NC 27599, USA.
authors.forename: Leonard
authors.initials: L
authors.lastname: McMillan
mesh_terms: D000465:Algorithms; D000818:Animals; D044962:Data Compression; D023281:Genomics / Q000379:methods; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D051379:Mice; D016415:Sequence Alignment