Efficient comparison of sets of intervals with NC-lists - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Journal Articles Bioinformatics Year : 2013

Efficient comparison of sets of intervals with NC-lists


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. 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 O½#Rlogð#RÞ þ #Qlogð#QÞ , where Q and R are the sets of query and reference intervals. The search phase requires constant space, and time Oð#R þ #Q þ #MÞ, where M is the set of overlaps. We showed that our algorithm compares favorably with five other algorithms, especially when several comparisons are performed. Availability: The algorithm has been included to S–MART, 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.


Dates and versions

hal-02652069 , version 1 (29-05-2020)



Matthias Zytnicki, Yufei Luo, Hadi Quesneville. Efficient comparison of sets of intervals with NC-lists. Bioinformatics, 2013, 29 (7), pp.933-939. ⟨10.1093/bioinformatics/btt070⟩. ⟨hal-02652069⟩


3 View
0 Download



Gmail Facebook X LinkedIn More