title: Computing exact P-values for DNA motifs.
abstract: 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.
authors.affiliation: State Key Laboratory of Intelligent Technology & System, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China.
authors.forename: Jing
authors.initials: J
authors.lastname: Zhang
authors.forename: Bo
authors.initials: B
authors.lastname: Jiang
authors.forename: Ming
authors.initials: M
authors.lastname: Li
authors.forename: John
authors.initials: J
authors.lastname: Tromp
authors.forename: Xuegong
authors.initials: X
authors.lastname: Zhang
authors.forename: Michael Q
authors.initials: MQ
authors.lastname: Zhang
mesh_terms: 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
chemical_list: D014157:Transcription Factors