A Faster Reliable Algorithm to Estimate the p-Value of the Multinomial llr Statistic

摘要

The subject of estimating the p-value of the log-likelihood ratio statistic for multinomial distribution has been studied extensively in the statistical literature. Nevertheless, bioinformatics laid new challenges before that research by often concentrating its interest on the "thin tail" of the distribution where classical statistical approximation typically fails. Hence, some of the more recent development in this area have come from the bioinformatics community. Since algorithms for computing the exact p-value have an exponential complexity, the only generally applicable algorithms for reliably estimating the p-value are lattice based. In particular, Hertz and Stormo have a dynamic programming algorithm whose complexity is O(QKN~2), where Q is the size of the lattice, K is the size of the alphabet and N is the size of the sample. We present a new algorithm that is practically as reliable as Hertz and Stormo's and has a complexity of O(QKN log N). An interesting feature of our algorithm is that it can guarantee the quality of its estimated p-value.