Markov chains improve the significance computation of overlapping genome annotations

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genome annotations represent genomic features like genes and regulatory elements.
• Assessing overlap significance is crucial for identifying true biological connections versus chance overlaps.
• Current statistical methods struggle with efficiency and accuracy for whole-genome analyses.

Purpose of the Study:

• To address the computational challenges in determining the statistical significance of overlapping genomic annotations.
• To develop a novel, efficient, and accurate method for calculating P-values for genome-wide annotation overlaps.

Main Methods:

• Demonstrated that calculating P-values under the standard 'gold' null hypothesis is NP-hard.
• Introduced a reformulated null hypothesis using Markov chains for improved efficiency.
• Developed a fast direct sampling algorithm to estimate P-values under the gold null hypothesis.
• Presented MCDP, an open-source software tool for computing P-values under the Markovian null hypothesis.

Main Results:

• The 'gold' null hypothesis for P-value computation is NP-hard.
• MCDP computes P-values in O(m2+n) time and O(m) memory, independent of genome length.
• MCDP significantly outperforms previous methods in runtime and memory usage for human genome annotations.
• The accuracy of MCDP is maintained compared to existing approaches.

Conclusions:

• The Markov chain-based approach provides an efficient and accurate solution for assessing genome annotation overlaps.
• MCDP offers a scalable and robust tool for analyzing large-scale genomic datasets.
• The software and associated data are publicly available for reproducibility and further research.