Efficient and accurate P-value computation for Position Weight Matrices
Efficient and accurate P-value computation for Position Weight Matrices
复制标题
DOI：
10.1186/1748-7188-2-15
复制
发表时间：
2007-12-11
影响因子：
1
通讯作者：
Varre, Jean-Stephane
中科院分区：
文献类型：
--
作者：
Touzet, Helene;Varre, Jean-Stephane
背景：位置权重矩阵 (PWM) 是序列中信号的概率表示。它们广泛用于模拟 DNA 或蛋白质序列中的近似模式。使用 PWM 的先决条件是根据单词的得分了解其统计显着性。这是通过定义分数的 P 值来完成的，P 值是背景模型可以获得大于或等于观察值的分数的概率。这就产生了以下问题：给定一个 P 值，找到相应的分数阈值。现有方法依赖于动态规划或概率生成函数。对于许多 PWM 示例，它们无法在合理的时间内给出准确的结果。 结果：本文的贡献有两个方面。首先，我们研究了该问题的理论复杂性，并证明该问题是NP困难的。然后，我们描述了一种有效解决 P 值问题的新算法。主要思想是使用一系列离散分数分布逐步改进最终结果，直到满足某些收敛标准。此外，即使对于具有非整数系数值的矩阵，该算法也能够计算准确的 P 值，没有任何错误。同样的方法也用于设计逆向问题的精确算法：找到给定分数的 P 值。这两种方法均在名为 TFM-PVALUE 的软件中实现，该软件可免费获取。结论：我们已经在代表转录因子结合位点的大量 PWM 上测试了 TFM-PVALUE。实验结果表明，与现有工具相比，它在计算时间和精度方面取得了更好的性能。
Background: Position Weight Matrices (PWMs) are probabilistic representations of signals in sequences. They are widely used to model approximate patterns in DNA or in protein sequences. The usage of PWMs needs as a prerequisite to knowing the statistical significance of a word according to its score. This is done by defining the P-value of a score, which is the probability that the background model can achieve a score larger than or equal to the observed value. This gives rise to the following problem: Given a P-value, find the corresponding score threshold. Existing methods rely on dynamic programming or probability generating functions. For many examples of PWMs, they fail to give accurate results in a reasonable amount of time.Results: The contribution of this paper is two fold. First, we study the theoretical complexity of the problem, and we prove that it is NP-hard. Then, we describe a novel algorithm that solves the P-value problem efficiently. The main idea is to use a series of discretized score distributions that improves the final result step by step until some convergence criterion is met. Moreover, the algorithm is capable of calculating the exact P-value without any error, even for matrices with noninteger coefficient values. The same approach is also used to devise an accurate algorithm for the reverse problem: finding the P-value for a given score. Both methods are implemented in a software called TFM-PVALUE, that is freely available.Conclusion: We have tested TFM-PVALUE on a large set of PWMs representing transcription factor binding sites. Experimental results show that it achieves better performance in terms of computational time and precision than existing tools.