Branch and bound computation of exact p-values

Area of Science:

• Bioinformatics
• Computational Biology
• Statistical Genetics

Background:

• P-value computation is vital for assessing statistical significance in bioinformatics.
• Approximation methods are often inaccurate for small sample sizes, sparse data, and rare events common in biological research.

Purpose of the Study:

• To develop and implement an efficient algorithm for exact p-value computation.
• To provide a tool for analyzing biological data where approximations are inadequate.

Main Methods:

• Utilized a likelihood-ratio statistic against a null multinomial distribution.
• Developed an efficient branch and bound algorithm for exact p-value calculation.
• Contrasted performance against full enumeration methods in commercial packages.

Main Results:

• The implemented code efficiently computes exact p-values, outperforming full enumeration.
• The method is particularly effective for small sample sizes, sparse data, and rare events.
• The codebase demonstrates adaptability for other statistics and sampling scenarios.

Conclusions:

• The developed method offers a more accurate and efficient approach to p-value computation in bioinformatics.
• This tool addresses limitations of approximation methods in challenging biological data scenarios.
• The approach has potential for broader applications in statistical analysis of biological data.