Massively Parallel Computation of Matching Statistics
摘要
The matching statistics of a string S relative to another string R is a sequence of |S| integer pairs, \((p_i,\ell _i)\) , one for each position in S, such that \(S[i..i+\ell _i] = R[p_i..p_i+\ell _i]\) and \(\ell _i\) is the length of the longest substring starting at position i in S that also occurs in R. Matching statistics have a variety of applications in sequence processing, such as approximate pattern matching, suffix sorting, compressed indexing, data compression, and multiple sequence alignment. Often the strings involved are large, making efficient computation paramount. In this paper we describe algorithms for matching statistics computation on massively parallel architectures, namely, graphics processing units (GPUs). We show that when implemented carefully these methods are much faster than CPU-based algorithms.