PWM matching alogrithm

Question

[zhenyisong]

I want to optimize the PWM algorithm. My original approach is brute force strategy which each position PWM score is calculated and compared with the threshold.Thus the running time is exponential dependent on the length of input string (DNA fragment). Is there some kind of speeding method to improve the performance the PWM string matching? If available, please provide some papers related to this problem so that I can implemented in my task. Thanks in advance.

Answer 1

[ibarra.ignacio]

I would suggest MOODS. It implements an algorithmic improvement to the classic PWM scanning, to find motif matches in linear time. http://www.cs.helsinki.fi/group/pssmfind

HTH!