Effective p-value computations using Finite Markov Chain Imbedding (FMCI): application to local score and to pattern...

Area of Science:

• Computational Biology
• Bioinformatics
• Statistical Modeling

Background:

• Finite Markov Chain Imbedding (FMCI) is a classical method for sequence-related combinatorial problems.
• Efficient algorithms require rewriting FMCI approaches using recursive relations.

Purpose of the Study:

• To develop general recursive algorithms for numerically stable computation of exact Cumulative Distribution Functions (CDF) and complementary CDFs (CCDFs).
• To apply these algorithms to local sequence scores and pattern statistics, deriving asymptotic developments.
• To enable exact p-value computation for practical biological sequence analysis, overcoming limitations of previous approximations.

Main Methods:

• Development of general recursive algorithms for exact CDF/CCDF computation.
• Application of these algorithms to local sequence scores and pattern statistics.
• Derivation of asymptotic developments for both applications.

Main Results:

• Exact p-values for local sequence scores were computed for the first time, revealing unreliability of asymptotic approximations in 99.5% of cases for a protein database study.
• New FMCI algorithms for pattern statistics demonstrated superior reliability, ease of implementation, speed, and lower memory requirements compared to previous methods.

Conclusions:

• The proposed recursive FMCI algorithms offer a significant advancement for computing exact sequence statistics.
• These methods provide accurate p-values for biological sequence analysis, essential for reliable findings.
• The algorithms present a more efficient and robust approach for pattern statistics in sequence data.