Computing exact p-values for DNA motifs (Part I). Export

@article{citeulike:1082904, abstract = {MOTIVATION: 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. AVAILABILITY: MotifRank is available from http://bio.dlg.cn.}, address = {State Key Laboratory of Intelligent Technology \& System, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China.}, author = {Zhang, Jing and Jiang, Bo and Li, Ming and Tromp, John and Zhang, Xuegong and Zhang, Michael Q Q.}, citeulike-article-id = {1082904}, citeulike-linkout-0 = {http://view.ncbi.nlm.nih.gov/pubmed/17237046}, citeulike-linkout-1 = {http://www.hubmed.org/display.cgi?uids=17237046}, day = {19}, issn = {1460-2059}, journal = {Bioinformatics}, keywords = {background}, month = {January}, posted-at = {2007-02-02 05:40:14}, priority = {2}, title = {Computing exact p-values for DNA motifs (Part I).}, url = {http://view.ncbi.nlm.nih.gov/pubmed/17237046}, year = {2007} }

TY - JOUR ID - citeulike:1082904 L3 - citeulike-article-id:1082904 N2 - MOTIVATION: 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. AVAILABILITY: MotifRank is available from http://bio.dlg.cn. JF - Bioinformatics SN - 1460-2059 AD - State Key Laboratory of Intelligent Technology & System, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China. TI - Computing exact p-values for DNA motifs (Part I). KW - background AU - Zhang, Jing AU - Jiang, Bo AU - Li, Ming AU - Tromp, John AU - Zhang, Xuegong AU - Zhang, Michael Q PY - 2007/01/19/ UR - http://view.ncbi.nlm.nih.gov/pubmed/17237046 ER -