Exact calculation of distributions on integers, with application to sequence alignment.

Area of Science:

• Computational biology
• Bioinformatics
• Algorithm development

Background:

• High-dimensional discrete prediction and inference problems are common in computational biology.
• Dynamic programming is applicable to key problems like sequence alignment and RNA structure prediction.
• Integer-based scores are frequently used for computational efficiency or natural definition in these problems.

Purpose of the Study:

• To present novel algorithms for calculating exact probability distributions of integer scores.
• To apply these algorithms to determine alignment score distributions and Bayesian confidence limits in sequence alignment.
• To enhance statistical inference in computational biology tasks.

Main Methods:

• Development of three distinct algorithms for exact score distribution calculation.
• Application of these algorithms within the framework of pairwise local sequence alignments.
• Utilizing dynamic programming recursions for score distribution analysis.

Main Results:

• Successful calculation of exact probability distributions for relevant scores.
• Determination of the score distribution for pairwise local sequence alignments.
• Computation of Bayesian confidence limits for sequence alignments.

Conclusions:

• The presented algorithms provide exact score distributions, improving statistical rigor.
• This approach facilitates more accurate significance testing and confidence interval estimation in computational biology.
• The methods are particularly useful for analyzing sequence alignment scores and related problems.