From H&M to Gap for Lightweight BWT Merging

2016/09/15 by Manzini, Giovanni
#Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1609.04618

Abstract

Recently, Holt and McMillan [Bionformatics 2014, ACM-BCB 2014] have proposed a simple and elegant algorithm to merge the Burrows-Wheeler transforms of a family of strings. In this paper we show that the H&M algorithm can be improved so that, in addition to merging the BWTs, it can also merge the Longest Common Prefix (LCP) arrays. The new algorithm, called Gap because of how it operates, has the same asymptotic cost as the H&M algorithm and requires additional space only for storing the LCP values.

Related

• Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
• A New Lightweight Algorithm to compute the BWT and the LCP array of a Set of Strings
• Merging RLBWTs adaptively
• Computing the optimal BWT of very large string collections
• Lightweight merging of compressed indices based on BWT variants