{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T16:29:31Z","timestamp":1677256171502},"reference-count":12,"publisher":"Oxford University Press (OUP)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: High-throughput sequencing produces in a small amount of time a large amount of data, which are usually difficult to analyze. Mapping the reads to the transcripts they originate from, to quantify the expression of the genes, is a simple, yet time demanding, example of analysis. Fast genomic comparison algorithms are thus crucial for the analysis of the ever-expanding number of reads sequenced.<\/jats:p>\n               <jats:p>Results: We used NC-lists to implement an algorithm that compares a set of query intervals with a set of reference intervals in two steps. The first step, a pre-processing done once for all, requires time , where Q and R are the sets of query and reference intervals. The search phase requires constant space, and time , where M is the set of overlaps. We showed that our algorithm compares favorably with five other algorithms, especially when several comparisons are performed.<\/jats:p>\n               <jats:p>Availability: The algorithm has been included to S\u2013MART, a versatile tool box for RNA-Seq analysis, freely available at http:\/\/urgi.versailles.inra.fr\/Tools\/S-Mart. The algorithm can be used for many kinds of data (sequencing reads, annotations, etc.) in many formats (GFF3, BED, SAM, etc.), on any operating system. It is thus readily useable for the analysis of next-generation sequencing data.<\/jats:p>\n               <jats:p>Contact: \u00a0matthias.zytnicki@versailles.inra.fr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt070","type":"journal-article","created":{"date-parts":[[2013,2,15]],"date-time":"2013-02-15T04:03:00Z","timestamp":1360900980000},"page":"933-939","source":"Crossref","is-referenced-by-count":4,"title":["Efficient comparison of sets of intervals with NC-lists"],"prefix":"10.1093","volume":"29","author":[{"given":"Matthias","family":"Zytnicki","sequence":"first","affiliation":[{"name":"URGI, INRA Versailles, Plant Biology and Breeding Division, 78026 Versailles Cedex, France"}]},{"given":"YuFei","family":"Luo","sequence":"additional","affiliation":[{"name":"URGI, INRA Versailles, Plant Biology and Breeding Division, 78026 Versailles Cedex, France"}]},{"given":"Hadi","family":"Quesneville","sequence":"additional","affiliation":[{"name":"URGI, INRA Versailles, Plant Biology and Breeding Division, 78026 Versailles Cedex, France"}]}],"member":"286","published-online":{"date-parts":[[2013,2,14]]},"reference":[{"key":"2023020303305033200_btt070-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":"2023020303305033200_btt070-B2","author":"Anders","year":"2011"},{"key":"2023020303305033200_btt070-B3","volume-title":"Galaxy: A Web-Based Genome Analysis Tool for Experimentalists","author":"Blankenberg","year":"2010"},{"key":"2023020303305033200_btt070-B4","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":"2023020303305033200_btt070-B5","doi-asserted-by":"crossref","first-page":"R86","DOI":"10.1186\/gb-2010-11-8-r86","article-title":"Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences","volume":"11","author":"Goecks","year":"2010","journal-title":"Genome Biol."},{"key":"2023020303305033200_btt070-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":"2023020303305033200_btt070-B7","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023020303305033200_btt070-B8","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The Sequence Alignment\/Map format and SAMtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020303305033200_btt070-B9","doi-asserted-by":"crossref","first-page":"e26715","DOI":"10.1371\/journal.pone.0026715","article-title":"Segtor: rapid annotation of genomic coordinates and single nucleotide variations using segment trees","volume":"6","author":"Renaud","year":"2011","journal-title":"PLoS ONE"},{"key":"2023020303305033200_btt070-B10","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. Comput. Biol."},{"key":"2023020303305033200_btt070-B11","doi-asserted-by":"crossref","first-page":"R22","DOI":"10.1186\/gb-2011-12-3-r22","article-title":"Improving Rna-Seq expression estimates by correcting for fragment bias","volume":"12","author":"Roberts","year":"2011","journal-title":"Genome Biol."},{"key":"2023020303305033200_btt070-B12","doi-asserted-by":"crossref","first-page":"e25988","DOI":"10.1371\/journal.pone.0025988","article-title":"S-MART, a software toolbox to aid RNA-seq data analysis","volume":"6","author":"Zytnicki","year":"2011","journal-title":"PLoS ONE"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/7\/933\/49060847\/bioinformatics_29_7_933.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/7\/933\/49060847\/bioinformatics_29_7_933.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T03:31:54Z","timestamp":1675395114000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/7\/933\/253826"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,14]]},"references-count":12,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2013,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt070","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,4,1]]},"published":{"date-parts":[[2013,2,14]]}}}