hide
Free keywords:
-
Abstract:
We present dynamic programming algorithms for two exact statistical tests that frequently arise in computational biology. The first test concerns the decision whether an observed sequence stems from a given profile (also known as position specific score matrix or position weight matrix), or from an assumed background distribution. We show that the common assumption that the log-odds score has a Gaussian distribution is false for many short profiles, such as transcription factor binding sites or splice sites. We present an efficient implementation of a non-parametric method (first mentioned by Staden) to compute the exact score distribution. The second test concerns the decision whether observed category counts stem from a specified Multinomial distribution. A branch-and-bound method for computing exact p-values for this test was presented by Bejerano at a recent RECOMB conference. Our contribution is a dynamic programming approach to compute the entire distribution of the test statistic, allowing not only the computation of exact p-values for all values of the test statistic simultaneously, but also of the power function of the test. As one of several applications, we introduce p-value based sequence logos, which provide a more meaningful visual description of probabilistic sequences than conventional sequence logos do.
