Efficient Search of Position Weight Matrices with a Truncated Suffix Tree

摘要

The Position Weight Matrix (PWM) is a widely used model of choice for several kind of biological signals in both DNA and protein contexts. Recently, several algorithms have been proposed to speed up the time required by the basic operation of matching a matrix with a sequence. In this paper we present TruSTsearch, an offline algorithm based on the truncated suffix trees data structure. We provide experimental comparison between our algorithm and the best known offline algorithm PoSSuMsearch, based on enhanced suffix array, showing that, thanks to the specifically designed TruSTcoding, our solution requires less space, and allows better performances.