sFFT: A faster accurate computation of the p-value of the entropy score
sFFT: A faster accurate computation of the p-value of the entropy score
复制标题
DOI：
10.1089/cmb.2005.12.416
复制
发表时间：
2005-05-01
影响因子：
1.7
通讯作者：
Keich, U
中科院分区：
文献类型：
--
作者：
Keich, U
我们提出了sFFT，一种有效地计算p值的信息内容，或熵得分的DNA序列的比对的算法。将FFT算法应用于指数移位的概率质量函数，使我们能够执行快速卷积，而不会受到累积数值舍入误差的压倒性影响。通过对sFFT各个步骤中数值误差传播的严格分析，我们提供了计算p值的总体误差的理论界。计算的p值的准确性，以及误差界的效用，经验证明。虽然有更快的算法可以计算这个p值，但它们可能会出现明显的错误; sFFT是最快的可靠算法。最后，我们注意到，基本算法可能适用于比这里考虑的更广泛的背景。
We present sFFT, an algorithm for efficiently computing the p- value of the information content, or the entropy score of an alignment of DNA sequences. Applying the FFT algorithm to an exponentially shifted probability mass function allows us perform fast convolutions that do not suffer from the otherwise overwhelming effect of accumulated numerical roundoff errors. Through a rigorous analysis of the propagation of numerical errors across the various steps of sFFT, we provide a theoretical bound on the overall error of our computed p- value. The accuracy of the computed p- value, as well as the utility of the error bound, are empirically demonstrated. Although there are faster algorithms that would compute this p- value, they can err significantly; sFFT is the fastest reliable algorithm. Finally, we note that the basic algorithm is likely to be applicable in a wider context than the one considered here.