title: Using sequence compression to speedup probabilistic profile matching.
abstract: BACKGROUND
  Matching a biological sequence against a probabilistic pattern (or profile) is a common task in computational biology. A probabilistic profile, represented as a scoring matrix, is more suitable than a deterministic pattern to retain the peculiarities of a given segment of a family of biological sequences. Brute-force algorithms take O(NP) to match a sequence of N characters against a profile of length P << N.
  
  
  RESULTS
  In this work, we exploit string compression techniques to speedup brute-force profile matching. We present two algorithms, based on run-length and LZ78 encodings, that reduce computational complexity by the compression factor of the encoding.
authors.affiliation: Information Science and Technology Institute, University of Urbino, 61029 Urbino, Italy.
authors.forename: Valerio
authors.initials: V
authors.lastname: Freschi
authors.forename: Alessandro
authors.initials: A
authors.lastname: Bogliolo
mesh_terms: D000465:Algorithms; D044962:Data Compression / Q000379:methods*; D020869:Gene Expression Profiling / Q000379:methods*; D008956:Models, Chemical; D015233:Models, Statistical; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology