Class IntervalTree
Data structure for efficient interval storage.

Defined in <seqan/misc/interval_tree.h>
Signature template <[typename TValue[, typename TCargo]]> class IntervalTree;

Template Parameters

TValue The type to use for coordinates. Default: int.
TCargo The type to use for cargo. Default: unsigned.

Member Function Overview

Interface Function Overview

Detailed Description

Remarks

If the intervals are not associated with cargos/IDs, they will be numbered consecutively.

Example

The following example creates an integer interval tree with string keys. This tree is quired for keys of intervals that overlap the interval [550, 990).

#include <iostream>
#include <seqan/misc/interval_tree.h>

using namespace seqan;

int main()
{
    // fill a string of intervals and keys
    typedef IntervalAndCargo<int, CharString> TInterval;
    String<TInterval> intervals;
    appendValue(intervals, TInterval(100, 1000, "gene"));
    appendValue(intervals, TInterval(100, 300, "exon1"));
    appendValue(intervals, TInterval(150, 250, "coding1"));
    appendValue(intervals, TInterval(500, 800, "exon2"));
    appendValue(intervals, TInterval(600, 700, "coding2"));

    // create IntervalTree of that string
    IntervalTree<int, CharString> tree(intervals);

    // find intervals that overlap the query interval [550,900)
    String<CharString> results;
    findIntervals(results, tree, 550, 900);

    // output corresponding keys
    for (unsigned i = 0; i < length(results); ++i)
        std::cout << results[i] << std::endl;

    return 0;
}

The resulting keys are:

gene
exon2
coding2

Member Functions Detail

IntervalTree::IntervalTree(); IntervalTree::IntervalTree(intervals); IntervalTree::IntervalTree(intervals[, center]); IntervalTree::IntervalTree(intervals[, tag]); IntervalTree::IntervalTree(intervalBegins, intervalEnds, [intervalCargos,] len);

Constructor

Parameters

intervals Container of intervals. A strin gof IntervalAndCargo<Value, TCargo> objects, see IntervalAndCargo.
intervalBegins Iterator pointing to begin position of first interval.
intervalEnds Iterator pointing to end position of first interval.
intervalCargos Iterator pointing to cargo/ids for intervals.
len Number of intervals to store in tree.
tag Tag for tree construction method.

Data Races

Thread safety unknown!

Interface Functions Detail

void addInterval(intervalTree, interval); void addInterval(intervalTree, begin, end[, cargo]); void addInterval(graph, propertyMap, interval);

Adds an interval to an interval tree.

Parameters

intervalTree The interval tree to add the interval to. Types: IntervalTree.
interval The interval to be added to the interval tree.
begin Begin position of interval of type TValue.
end End position of interval of type TValue.
cargo Cargo to attach to the interval. Types: IntervalAndCargo.
graph The directed graph that contains the topography of the interval tree.
propertyMap The property map containing the node properties of the interval tree.

Data Races

Thread safety unknown!

void createIntervalTree(intervalTree, intervals[, tag]); void createIntervalTree(g, pm, intervals[, tag]); void createIntervalTree(g, pm, intervals, center[, tag]]);

Create an interval tree.

Parameters

intervalTree An interval tree Types: IntervalTree
g DirectedGraph to create interval tree in. Types: Graph.
pm Property map to use for the created interval tree.
tag Tag for tree construction method;
intervals Container of intervals. A string of IntervalAndCargo<TValue, TCargo> objects, see IntervalAndCargo. Types: AllocString.

Data Races

Thread safety unknown!

void findIntervals(result, intervalTree, query); void findIntervals(result, intervalTree, queryBegin, queryEnd); void findIntervals(result, graph, propertyMap, query);

Find all intervals that contain the query point or overlap with the query interval.

Parameters

result A reference to the result string of TCargo objects. Types: String.
intervalTree An IntervalTree.
graph The directed graph that contains the topography of the interval tree.
propertyMap The property map containing the node properties of the interval tree.
query A query point.
queryBegin The begin position of the query interval.
queryEnd The end position of the query interval.

Data Races

Thread safety unknown!

void findIntervalsExcludeTouching(result, intervalTree, query); void findIntervalsExcludeTouching(result, graph, propertyMap, query,);

Find all intervals that contain the query point, exclude intervals that touch the query, i.e. where the query point equals the start or end point.

Parameters

result The resulting string of cargos/ids of the intervals that contain the query point. Should be a string of TCargo. Types: String
intervalTree An interval tree Types: IntervalTree
graph The directed graph that contains the topography of the interval tree.
query The TValue to query here.
propertyMap The property map containing the node properties of the interval tree

Data Races

Thread safety unknown!

bool removeInterval(intervalTree, iBegin, iEnd, iId);

Removes an interval from the interval tree.

Parameters

intervalTree An interval tree Types: IntervalTree
iBegin The begin position of the interval to be removed.
iEnd The end position of the interval to be removed.
iId The ID of the interval to be removed.

Returns

bool true on success, false on failure.

Data Races

Thread safety unknown!