IntervalForest-class: Interval Search Forests

Description

Efficiently perform overlap queries with a set of interval trees.

Arguments

Constructor

: IntervalForest(rangesList): Creates an IntervalForest from the ranges list in rangesList, an object coercible to CompressedIRangesList.

Accessors

: length(x): Gets the number of ranges stored in the forest. This is a fast operation that does not bring the ranges into R.
: start(x): Get the starts of the ranges as a CompressedIntegerList.
: end(x): Get the ends of the ranges as CompressedIntegerList.
: x@partitioning: The range partitioning of class PartitioningByEnd.
: names(x): Get the names of the range partitioning.
: elementLengths(x): The number of ranges in each partition.

Details

A common type of query that arises when working with intervals is finding which intervals in one set overlap those in another. An efficient family of algorithms for answering such queries is known as the Interval Tree. The IntervalForest class stores a set of Interval Trees corresponding to intervals that are partitioned into disjoint sets. The most efficient way to construct IntervalForest objects is to call the constructor below on a CompressedIRangesList object. See the IntervalTree class for the underlying Interval Tree data structure.

A canonical example of a compressed ranges list are GenomicRanges objects, where intervals are partitioned by their seqnames. See the GIntervalTree class to see the use of IntervalForest objects in this case.

The simplest approach for finding overlaps is to call the findOverlaps function on a RangesList object. See the man page of findOverlaps-methods for how to use this and other related functions.

Examples

Run this code

  query <- IRangesList(a=IRanges(c(1,4),c(5,7)),b=IRanges(9,10))
  subject <- IRangesList(a=IRanges(c(2,2),c(2,3)),b=IRanges(10,12))
  forest <- IntervalForest(subject)

  findOverlaps(query, forest)