[Bioc-devel] findOverlaps() news

[Hervé Pagès]

Developers,

In BioC 3.1 the code behind overlap operations like findOverlaps(),
countOverlaps(), subsetByOverlaps(), summarizeOverlaps(), nearest(),
etc... has been refactored and improved. Some highlights on what has
changed:

- The underlying code used for finding/counting overlaps is now based
   on the beautiful Nested Containment List algorithm by Alexander V.
   Alekseyenko1 and Christopher J. Lee2 [1].

- The old algorithm based on interval trees is still available. The
   'algorithm' argument was added to most overlap-based operations to
   let the user choose between the new (algorithm="nclist", the default)
   and the old (algorithm="intervaltree") algorithm. Except for the 3
   particular situations mentioned below, choosing one or the other
   doesn't affect the output, only the performance.

- Either the query or subject can be preprocessed with NCList() for
   a Ranges object (replacement for IntervalTree()), and GNCList()
   for a GenomicRanges object (replacement for GIntervalTree()).
   For a one time use, it's not advised to explicitely preprocess the
   input. This is because findOverlaps() or countOverlaps() will take
   care of it and do a better job at it (that is, they preprocess only
   what's needed when it's needed and release memory as they go).

- GNCList() supports preprocessing of a GenomicRanges object with
   ranges located on a circular sequence.

- With the new algorithm, countOverlaps() on Ranges or GenomicRanges
   objects doesn't call findOverlaps() to collect all the hits in a
   growing Hits object and count them only at the end. Instead the
   counting happens at the C level and the hits are not kept. This
   reduces memory usage considerably when there is a lot of hits.

- Zero-width ranges are now interpreted as insertion points and are
   considered to overlap with ranges that contain them. This is the
   1st situation where using 'algorithm="nclist"' or
   'algorithm="intervaltree"' produces different output.

- When using 'select="arbitrary"', the new algorithm will generally
   not select the same hits as the old algorithm. This is the 2nd
   situation where using 'algorithm="nclist"' or
   'algorithm="intervaltree"' produces different output.

- When using the old interval tree algorithm, 'maxgap' has a special
   meaning if 'type' is "start", "end", or "within". This is not yet
   the case with the new algorithm. That feature seems somewhat useful
   though so maybe the new algorithm should also support it? Anyway,
   this is the 3rd situation where using 'algorithm="nclist"' or
   'algorithm="intervaltree"' produces different output.

- Objects preprocessed with NCList() or GNCList() are serializable.

Performance:

In BioC 3.1 overlaps operations like findOverlaps() or
summarizeOverlaps() on GRanges and/or GRangesList objects are
typically between 3x and 10x faster than in BioC 3.0 for a medium
size data set (e.g. 25 million reads). Memory usage is also reduced
by 25% or more. These numbers may vary but the bigger the data set,
the better they will be.

This is with IRanges 2.1.29 and GenomicRanges 1.19.21 (will become
available tomorrow).

Some remaining tasks:

   (a) Bring back special meaning of 'maxgap' when 'type' is "start",
       "end", or "within".

   (b) Update documentation.

   (c) Enable user interrupts.

   (d) GNCLists for prepreocessing a GRangesList object (just a
       GNCList inside a CompressedList).

   (e) Use threads (OpenMP) for even better performance (to be
       implemented in an add-on package).

Even though a lot of time and effort was spent in testing the new
code and making sure it won't crash your session, you might run into
problems. Please report.

Enjoy and let me know if you have questions or comments about this.

Thanks!
H.

[1] Alexander V. Alekseyenko1 and Christopher J. Lee2.
     Nested Containment List (NCList): a new algorithm for accelerating
     interval query of genome alignment and interval databases.
     Bioinformatics (2007) 23 (11): 1386-1393.

-- 
Hervé Pagès

Program in Computational Biology
Division of Public Health Sciences
Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N, M1-B514
P.O. Box 19024
Seattle, WA 98109-1024

E-mail: hpages at fredhutch.org
Phone:  (206) 667-5791
Fax:    (206) 667-1319