Using sequence compression to speedup probabilistic profile matching.
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.
Freschi
Valerio
V
Information Science and Technology Institute, University of Urbino, 61029 Urbino, Italy.
Bogliolo
Alessandro
A
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