International,  ACL (papers with reading comittee)

BioInformatics

15 Feb 2013   Efficient comparison of sets of intervals with NC-lists

Matthias Zytnicki, YuFei Luo, Hadi Quesneville

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, in order 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 to 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 https://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. Moreover, the algorithm is also implemented in the " s_mart " package from the Galaxy Tool Shed. It is thus readily useable for the analysis of next-generation sequencing data.

The article is available on the BioInformatics Web site .

Keywords: bioinformatics