{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T04:26:56Z","timestamp":1776054416768,"version":"3.50.1"},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The comparison of diverse genomic datasets is fundamental to understand genome biology. Researchers must explore many large datasets of genome intervals (e.g. genes, sequence alignments) to place their experimental results in a broader context and to make new discoveries. Relationships between genomic datasets are typically measured by identifying intervals that intersect, that is, they overlap and thus share a common genome interval. Given the continued advances in DNA sequencing technologies, efficient methods for measuring statistically significant relationships between many sets of genomic features are crucial for future discovery.<\/jats:p>\n               <jats:p>Results: We introduce the Binary Interval Search (BITS) algorithm, a novel and scalable approach to interval set intersection. We demonstrate that BITS outperforms existing methods at counting interval intersections. Moreover, we show that BITS is intrinsically suited to parallel computing architectures, such as graphics processing units by illustrating its utility for efficient Monte Carlo simulations measuring the significance of relationships between sets of genomic intervals.<\/jats:p>\n               <jats:p>Availability: \u00a0https:\/\/github.com\/arq5x\/bits.<\/jats:p>\n               <jats:p>Contact: \u00a0arq5x@virginia.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts652","type":"journal-article","created":{"date-parts":[[2012,11,6]],"date-time":"2012-11-06T03:08:43Z","timestamp":1352171323000},"page":"1-7","source":"Crossref","is-referenced-by-count":44,"title":["Binary Interval Search: a scalable algorithm for counting interval intersections"],"prefix":"10.1093","volume":"29","author":[{"given":"Ryan M.","family":"Layer","sequence":"first","affiliation":[{"name":"1 Department of Computer Science, University of Virginia, Charlottesville, VA 22904, 2Department of Biochemistry and Molecular Genetics and 3Department of Public Health Sciences and Center for Public Health Genomics, University of Virginia, Charlottesville, VA 22908, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Skadron","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Virginia, Charlottesville, VA 22904, 2Department of Biochemistry and Molecular Genetics and 3Department of Public Health Sciences and Center for Public Health Genomics, University of Virginia, Charlottesville, VA 22908, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Robins","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Virginia, Charlottesville, VA 22904, 2Department of Biochemistry and Molecular Genetics and 3Department of Public Health Sciences and Center for Public Health Genomics, University of Virginia, Charlottesville, VA 22908, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ira M.","family":"Hall","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Virginia, Charlottesville, VA 22904, 2Department of Biochemistry and Molecular Genetics and 3Department of Public Health Sciences and Center for Public Health Genomics, University of Virginia, Charlottesville, VA 22908, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron R.","family":"Quinlan","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science, University of Virginia, Charlottesville, VA 22904, 2Department of Biochemistry and Molecular Genetics and 3Department of Public Health Sciences and Center for Public Health Genomics, University of Virginia, Charlottesville, VA 22908, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,11,4]]},"reference":[{"key":"2023020303200782400_bts652-B1","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1093\/bioinformatics\/btl647","article-title":"Nested containment list (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases","volume":"23","author":"Alekseyenko","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020303200782400_bts652-B2","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1038\/nature05874","article-title":"Identification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project","volume":"447","author":"ENCODE Project Consortium (2007)","journal-title":"Nature"},{"key":"2023020303200782400_bts652-B3","doi-asserted-by":"crossref","first-page":"e1002529","DOI":"10.1371\/journal.pcbi.1002529","article-title":"Exploring massive, genome scale datasets with the GenometriCorr package","volume":"8","author":"Favorov","year":"2012","journal-title":"PLoS Comput. Biol."},{"key":"2023020303200782400_bts652-B4","doi-asserted-by":"crossref","first-page":"1775","DOI":"10.1126\/science.1196914","article-title":"Integrative analysis of the Caenorhabditis elegans genome by the modENCODE project","volume":"330","author":"Gerstein","year":"2010","journal-title":"Science"},{"key":"2023020303200782400_bts652-B5","doi-asserted-by":"crossref","first-page":"1451","DOI":"10.1101\/gr.4086505","article-title":"Galaxy: a platform for interactive large-scale genome analysis","volume":"15","author":"Giardine","year":"2005","journal-title":"Genome Res."},{"key":"2023020303200782400_bts652-B6","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1101\/gr.229102","article-title":"The human genome browser at UCSC","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023020303200782400_bts652-B7","volume-title":"Programming Massively Parallel Processors: A Hands-On Approach","author":"Kirk","year":"2010"},{"key":"2023020303200782400_bts652-B8","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The sequence alignment\/map (SAM) format and SAMtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020303200782400_bts652-B9","doi-asserted-by":"crossref","DOI":"10.1145\/1653771.1653827","article-title":"A parallel plane sweep algorithm for multi-core systems","volume-title":"Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems","author":"McKenney","year":"2009"},{"key":"2023020303200782400_bts652-B10","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1142\/S0129626411000187","article-title":"High performance and scalable radix sorting: a case study of implementing dynamic parallelism for GPU computing","volume":"21","author":"Merrill","year":"2011","journal-title":"Parallel Process. Lett."},{"key":"2023020303200782400_bts652-B11","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","article-title":"Finding repeated elements","volume":"2","author":"Mirsa","year":"1982","journal-title":"Sci. Comput. Progr."},{"key":"2023020303200782400_bts652-B12","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1093\/bioinformatics\/bts277","article-title":"BEDOPS: high performance genomic feature operations","volume":"28","author":"Neph","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020303200782400_bts652-B13","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1093\/bioinformatics\/btq033","article-title":"BEDTools: a flexible suite of utilities for comparing genomic features","volume":"26","author":"Quinlan","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020303200782400_bts652-B14","doi-asserted-by":"crossref","first-page":"1457","DOI":"10.1089\/cmb.2006.13.1457","article-title":"fjoin: simple and efficient computation of feature overlaps","volume":"13","author":"Richardson","year":"2006","journal-title":"J. Computat. Biol."},{"key":"2023020303200782400_bts652-B15","doi-asserted-by":"crossref","DOI":"10.1109\/IPDPS.2009.5161005","article-title":"Designing efficient sorting algorithms for manycore GPUs","volume-title":"International Symposium on Parallel and Distributed Processing, 2009","author":"Satish","year":"2009"},{"key":"2023020303200782400_bts652-B16","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature09534","article-title":"A map of human genome variation from population-scale sequencing","volume":"467","author":"The 1000 Genomes Project Consortium (2010)","journal-title":"Nature"},{"key":"2023020303200782400_bts652-B17","doi-asserted-by":"crossref","DOI":"10.1145\/1342250.1342263","article-title":"Parallel white noise generation on a GPU via cryptographic hash","volume-title":"Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games","author":"Tzeng","year":"2008"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/1\/1\/49060487\/bioinformatics_29_1_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/1\/1\/49060487\/bioinformatics_29_1_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T03:20:48Z","timestamp":1675394448000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/1\/1\/273289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,4]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts652","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,1]]},"published":{"date-parts":[[2012,11,4]]}}}