Computing exact P-values for DNA motifs.
BACKGROUND
Many heuristic algorithms have been designed to approximate P-values of DNA motifs described by position weight matrices, for evaluating their statistical significance. They often significantly deviate from the true P-value by orders of magnitude. Exact P-value computation is needed for ranking the motifs. Furthermore, surprisingly, the complexity of the problem is unknown.


RESULTS
We show the problem to be NP-hard, and present MotifRank, software based on dynamic programming, to calculate exact P-values of motifs. We define the exact P-value on a general and more precise model. Asymptotically, MotifRank is faster than the best exact P-value computing algorithm, and is in fact practical. Our experiments clearly demonstrate that MotifRank significantly improves the accuracy of existing approximation algorithms.


BACKGROUND
MotifRank is available from http://bio.dlg.cn.


BACKGROUND
Supplementary data are available at Bioinformatics online.
Zhang
Jing
J
State Key Laboratory of Intelligent Technology & System, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China.
Jiang
Bo
B
Li
Ming
M
Tromp
John
J
Zhang
Xuegong
X
Zhang
Michael Q
MQ
D000465:Algorithms; D001665:Binding Sites; D003198:Computer Simulation; D015233:Models, Statistical; D011401:Promoter Regions, Genetic; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000378:metabolism
D014157:Transcription Factors