{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:06:38Z","timestamp":1773270398223,"version":"3.50.1"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1453527"],"award-info":[{"award-number":["1453527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1931531"],"award-info":[{"award-number":["1931531"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union Horizon 2020","award":["872539"],"award-info":[{"award-number":["872539"]}]},{"DOI":"10.13039\/501100005357","name":"Slovak Research and Development Agency","doi-asserted-by":"publisher","award":["APVV-18-0239"],"award-info":[{"award-number":["APVV-18-0239"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Scientific Grant Agency VEGA","award":["1\/0463\/20"],"award-info":[{"award-number":["1\/0463\/20"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Genome annotations are a common way to represent genomic features such as genes, regulatory elements or epigenetic modifications. The amount of overlap between two annotations is often used to ascertain if there is an underlying biological connection between them. In order to distinguish between true biological association and overlap by pure chance, a robust measure of significance is required. One common way to do this is to determine if the number of intervals in the reference annotation that intersect the query annotation is statistically significant. However, currently employed statistical frameworks are often either inefficient or inaccurate when computing P-values on the scale of the whole human genome.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We show that finding the P-values under the typically used \u2018gold\u2019 null hypothesis is NP-hard. This motivates us to reformulate the null hypothesis using Markov chains. To be able to measure the fidelity of our Markovian null hypothesis, we develop a fast direct sampling algorithm to estimate the P-value under the gold null hypothesis. We then present an open-source software tool MCDP that computes the P-values under the Markovian null hypothesis in O(m2+n) time and O(m) memory, where m and n are the numbers of intervals in the reference and query annotations, respectively. Notably, MCDP runtime and memory usage are independent from the genome length, allowing it to outperform previous approaches in runtime and memory usage by orders of magnitude on human genome annotations, while maintaining the same level of accuracy.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>The software is available at https:\/\/github.com\/fmfi-compbio\/mc-overlaps. All data for reproducibility are available at https:\/\/github.com\/fmfi-compbio\/mc-overlaps-reproducibility.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac255","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i203-i211","source":"Crossref","is-referenced-by-count":4,"title":["Markov chains improve the significance computation of overlapping genome annotations"],"prefix":"10.1093","volume":"38","author":[{"given":"Askar","family":"Gafurov","sequence":"first","affiliation":[{"name":"Department of Computer Science, Comenius University , Bratislava 84248, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bro\u0148a","family":"Brejov\u00e1","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Comenius University , Bratislava 84248, Slovakia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University , University Park, PA 16802, USA"},{"name":"Department of Biochemistry and Molecular Biology, The Pennsylvania State University , University Park, PA 16802, USA"},{"name":"Huck Institutes of the Life Sciences, The Pennsylvania State University , University Park, PA 16802, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"issue":"2","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.cell.2009.01.002","article-title":"MicroRNAs: target recognition and regulatory functions","volume":"136","author":"Bartel","year":"2009","journal-title":"Cell"},{"issue":"13","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1743","DOI":"10.1001\/jama.1983.03330370053031","article-title":"If nothing goes wrong, is everything all right? Why we should be wary of zero numerators","volume":"249","author":"Burns","year":"1983","journal-title":"J. Am. Med. Assoc"},{"issue":"5","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1093\/bioinformatics\/bts009","article-title":"An effective statistical evaluation of ChipSeq dataset similarity","volume":"28","author":"Chikina","year":"2012","journal-title":"Bioinformatics"},{"key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-15-S7-S2","article-title":"Analysis of interactions between the epigenome and structural mutability of the genome using Genboree workbench tools","volume":"15","author":"Coarfa","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023041407562089600_","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Non-Uniform Random Variate Generation","author":"Devroye","year":"1986"},{"issue":"20","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"3323","DOI":"10.1093\/bioinformatics\/btx414","article-title":"Epigenomic annotation-based interpretation of genomic data: from enrichment analysis to machine learning","volume":"33","author":"Dozmorov","year":"2017","journal-title":"Bioinformatics"},{"issue":"8","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1038\/nbt.1662","article-title":"Discovery and characterization of chromatin states for systematic annotation of the human genome","volume":"28","author":"Ernst","year":"2010","journal-title":"Nat. Biotechnol"},{"key":"2023041407562089600_","volume-title":"Computers and Intractability","author":"Garey","year":"1979"},{"issue":"1","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jagm.1997.0913","article-title":"A survey of fast exponentiation methods","volume":"27","author":"Gordon","year":"1998","journal-title":"J. Algorithms"},{"issue":"1","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-021-02440-w","article-title":"Bedshift: perturbation of genomic interval sets","volume":"22","author":"Gu","year":"2021","journal-title":"Genome Biol"},{"issue":"1","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.cell.2007.05.042","article-title":"A chromatin landmark and transcription initiation at most promoters in human cells","volume":"130","author":"Guenther","year":"2007","journal-title":"Cell"},{"key":"2023041407562089600_","first-page":"99","author":"Isensee","year":"2005"},{"issue":"9","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/S0168-9525(00)02093-X","article-title":"Repbase update: a database and an electronic journal of repetitive elements","volume":"16","author":"Jurka","year":"2000","journal-title":"Trends Genet"},{"issue":"9","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1093\/bioinformatics\/bty835","article-title":"Colocalization analyses of genomic elements: approaches, recommendations and challenges","volume":"35","author":"Kanduri","year":"2019","journal-title":"Bioinformatics"},{"key":"2023041407562089600_","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller","year":"2009"},{"key":"2023041407562089600_","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4400-4","volume-title":"The Design and Analysis of Algorithms","author":"Kozen","year":"1992"},{"issue":"1","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bioinformatics\/bts652","article-title":"Binary Interval Search: a scalable algorithm for counting interval intersections","volume":"29","author":"Layer","year":"2013","journal-title":"Bioinformatics"},{"key":"2023041407562089600_","volume-title":"Interactive Linear Algebra","author":"Margalit","year":"2017"},{"issue":"5","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1038\/nbt.1630","article-title":"GREAT improves functional interpretation of cis-regulatory regions","volume":"28","author":"McLean","year":"2010","journal-title":"Nat. Biotechnol"},{"key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1093\/bioinformatics\/bti1044","article-title":"Computing the P-value of the information content from an alignment of multiple sequences","volume":"21(Suppl. 1","author":"Nagarajan","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041407562089600_","volume-title":"Markov Chains","author":"Norris","year":"1998"},{"issue":"1","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-017-1678-9","article-title":"Coordinates and intervals in graph-based reference genomes","volume":"18","author":"Rand","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023041407562089600_","volume-title":"DNA, Words and Models: Statistics of Exceptional Words","author":"Robin","year":"2005"},{"issue":"6","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1016\/j.cels.2019.05.006","article-title":"Computing the statistical significance of overlap between genome annotations with ISTAT","volume":"8","author":"Sarmashghi","year":"2019","journal-title":"Cell Syst"},{"issue":"4","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1093\/bioinformatics\/btv612","article-title":"LOLA: enrichment analysis for genomic region sets and regulatory elements in R and Bioconductor","volume":"32","author":"Sheffield","year":"2016","journal-title":"Bioinformatics"},{"issue":"7643","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1038\/nature21356","article-title":"Extrachromosomal oncogene amplification drives tumour evolution and genetic heterogeneity","volume":"543","author":"Turner","year":"2017","journal-title":"Nature"},{"issue":"5507","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1126\/science.1058040","article-title":"The sequence of the human genome","volume":"291","author":"Venter","year":"2001","journal-title":"Science (New York, N.Y.)"},{"issue":"14","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"2382","DOI":"10.1093\/bioinformatics\/btv145","article-title":"ChIP seeker: an R\/Bioconductor package for ChIP peak annotation, comparison and visualization","volume":"31","author":"Yu","year":"2015","journal-title":"Bioinformatics"},{"issue":"3","key":"2023041407562089600_","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1038\/nrg3871","article-title":"A copy number variation map of the human genome","volume":"16","author":"Zarrei","year":"2015","journal-title":"Nat. Rev. Genet"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i203\/49887032\/btac255.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i203\/49887032\/btac255.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T06:55:49Z","timestamp":1726988149000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i203\/6617480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":29,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac255","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}