Branch and bound computation of exact p-values.
P-value computation is often used in bioinformatics to quantify the surprise, or significance, associated with a given observation. An implementation is provided that computes the exact p-value associated with any observed sample, against a null multinomial distribution, using the likelihood-ratio statistic. The efficient branch and bound code, far exceeding the full enumeration implemented by commercial packages, is especially useful with small sample, sparse data and rare events, common scenarios in bioinformatics, where approximations are often inaccurate and inappropriate. This code base can also be adapted to compute exact p-values of other statistics in diverse sampling scenarios.


BACKGROUND
Freely available at http://www.soe.ucsc.edu/~jill/src/.
Bejerano
Gill
G
Center for Biomolecular Science and Engineering, School of Engineering, 1156 High Street, University of California, Santa Cruz, CA 95064, USA. jill@soe.ucsc.edujill
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D008954:Models, Biological; D015233:Models, Statistical; D017421:Sequence Analysis / Q000379:methods*