title: Efficient comparison of sets of intervals with NC-lists.
abstract: BACKGROUND
  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[#R log(#R) + #Q log(#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.
  
  
  BACKGROUND
  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.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors: URGI, INRA Versailles, Plant Biology and Breeding Division, 78026 Versailles Cedex, France. matthias.zytnicki@versailles.inra.fr
authors: Matthias
authors: M
authors: Zytnicki
authors: YuFei
authors: Y
authors: Luo
authors: Hadi
authors: H
authors: Quesneville
mesh_terms: D000465:Algorithms; D016678:Genome; D023281:Genomics; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D017423:Sequence Analysis, RNA