Computational Biology
@ Comenius University in Bratislava

Askar Gafurov, Tomas Vinar, Paul Medvedev, Brona Brejova. Efficient Analysis of Annotation Colocalization Accounting for Genomic Contexts. In Jian Ma, ed., Research in Computational Molecular Biology (RECOMB), 14758 volume of Lecture Notes in Computer Science, pp. 38-53, 2024. Springer.

Download preprint: not available

Download from publisher: https://doi.org/10.1007/978-1-0716-3989-4_3

Related web page: not available

Bibliography entry: BibTeX

Abstract:

An annotation is a set of genomic intervals sharing a particular function or 
property. Examples include genes, conserved elements, and epigenetic 
modifications. A common task is to compare two annotations to determine if one is 
enriched or depleted in the regions covered by the other. We study the problem of 
assigning statistical significance to such a comparison based on a null model 
representing two random unrelated annotations. To incorporate more background 
information into such analyses and avoid biased results, we propose a new null 
model based on a Markov chain which differentiates among several genomic 
contexts. These contexts can capture various confounding factors, such as GC 
content or sequencing gaps. We then develop a new algorithm for estimating 
p-values by computing the exact expectation and variance of the test statistic 
and then estimating the p-value using a normal approximation. Compared to the 
previous algorithm by Gafurov et al., the new algorithm provides three advances: 
(1) the running time is improved from quadratic to linear or quasi-linear, (2) 
the algorithm can handle two different test statistics, and (3) the algorithm can 
handle both simple and context-dependent Markov chain null models. We demonstrate 
the efficiency and accuracy of our algorithm on synthetic and real data sets, 
including the recent human telomere-to-telomere assembly. In particular, our 
algorithm computed p-values for 450 pairs of human genome annotations using 24 
threads in under three hours. The use of genomic contexts to correct for GC-bias 
also resulted in the reversal of some previously published findings.