NCList-class: Nested Containment List objects
In IRanges: Foundation of integer range manipulation in Bioconductor

Description Usage Arguments Details Value Author(s) References See Also Examples

The NCList class is a container for storing the Nested Containment List representation of a IntegerRanges object. Preprocessing a IntegerRanges object as a Nested Containment List allows efficient overlap-based operations like findOverlaps.

The NCLists class is a container for storing a collection of NCList objects. An NCLists object is typically the result of preprocessing each list element of a IntegerRangesList object as a Nested Containment List. Like with NCList, the NCLists object can then be used for efficient overlap-based operations.

To preprocess a IntegerRanges or IntegerRangesList object, simply call the NCList or NCLists constructor function on it.

1 2	NCList(x, circle.length=NA_integer_) NCLists(x, circle.length=NA_integer_)

x

The IntegerRanges or IntegerRangesList object to preprocess.

circle.length

Use only if the space (or spaces if x is a IntegerRangesList object) on top of which the ranges in x are defined needs (need) to be considered circular. If that's the case, then use circle.length to specify the length(s) of the circular space(s).

For NCList, circle.length must be a single positive integer (or NA if the space is linear).

For NCLists, it must be an integer vector parallel to x (i.e. same length) and with positive or NA values (NAs indicate linear spaces).

The GenomicRanges package also defines the GNCList constructor and class for preprocessing and representing a vector of genomic ranges as a data structure based on Nested Containment Lists.

Some important differences between the new findOverlaps/countOverlaps implementation based on Nested Containment Lists (BioC >= 3.1) and the old implementation based on Interval Trees (BioC < 3.1):

With the new implementation, the hits returned by findOverlaps are not fully ordered (i.e. ordered by queryHits and subject Hits) anymore, but only partially ordered (i.e. ordered by queryHits only). Other than that, and except for the 2 particular situations mentioned below, the 2 implementations produce the same output. However, the new implementation is faster and more memory efficient.
With the new implementation, either the query or the subject can be preprocessed with NCList for a IntegerRanges object (replacement for IntervalTree), NCLists for a IntegerRangesList object (replacement for IntervalForest), and GNCList for a GenomicRanges object (replacement for GIntervalTree). However, for a one-time use, it is 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 (by preprocessing only what's needed when it's needed, and releasing memory as they go).
With the new implementation, countOverlaps on IntegerRanges or GenomicRanges objects doesn't call findOverlaps in order 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.
When minoverlap=0, zero-width ranges are now interpreted as insertion points and considered to overlap with ranges that contain them. With the old alogrithm, zero-width ranges were always ignored. This is the 1st situation where the new and old implementations produce different outputs.
When using select="arbitrary", the new implementation will generally not select the same hits as the old implementation. This is the 2nd situation where the new and old implementations produce different outputs.
The new implementation supports preprocessing of a GenomicRanges object with ranges defined on circular sequences (e.g. on the mitochnodrial chromosome). See GNCList in the GenomicRanges package for some examples.
Objects preprocessed with NCList, NCLists, and GNCList are serializable (with save) for later use. Not a typical thing to do though, because preprocessing is very cheap (i.e. very fast and memory efficient).

An NCList object for the NCList constructor and an NCLists object for the NCLists constructor.

Hervé Pagès

Alexander V. Alekseyenko and Christopher J. Lee – Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases. Bioinformatics (2007) 23 (11): 1386-1393. doi: 10.1093/bioinformatics/btl647

The GNCList constructor and class defined in the GenomicRanges package.
findOverlaps for finding/counting interval overlaps between two range-based objects.
IntegerRanges and IntegerRangesList objects.

## The example below is for illustration purpose only and does NOT
## reflect typical usage. This is because, for a one-time use, it is
## NOT advised to explicitely preprocess the input for findOverlaps()
## or countOverlaps(). These functions will take care of it and do a
## better job at it (by preprocessing only what's needed when it's
## needed, and release memory as they go).

query <- IRanges(c(1, 4, 9), c(5, 7, 10))
subject <- IRanges(c(2, 2, 10), c(2, 3, 12))

## Either the query or the subject of findOverlaps() can be preprocessed:

ppsubject <- NCList(subject)
hits1 <- findOverlaps(query, ppsubject)
hits1

ppquery <- NCList(query)
hits2 <- findOverlaps(ppquery, subject)
hits2

## Note that 'hits1' and 'hits2' contain the same hits but not in the
## same order.
stopifnot(identical(sort(hits1), sort(hits2)))