Neighbourhood Thresholding for Projection-Based Motif Discovery
James A. King, Warren Cheung, Holger H. Hoos · 2005
The PROJECTION algorithm by Buhler and Tompa is one of the best existing methods for solving hard motif discovery problems for monad motifs of fixed length l. In this paper we introduce the AGGREGATION algorithm, which like PROJECTION projects all l-mers from the given input sequences into buckets, but uses a different scheme for selecting buckets for subsequent refinement search. This new neighbourhood-based thresholding scheme allows AGGREGATION to discover motifs in biased background sequences that cannot be found by PROJECTION. In other cases, AGGREGATION finds motifs of the same quality as PROJECTION substantially more efficiently.