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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Massively Parallel Computation of Matching Statistics

  • Anastasia C. Diseth,
  • Keijo Heljanko,
  • Simon J. Puglisi

摘要

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.