IntervalTree

Class

IntervalTree

A datastructure that efficiently stores intervals.

IntervalTree<TValue, TCargo>

Include Headers

seqan/misc/misc_interval_tree.h

Parameters

TValue	The value type. Default: int
TCargo	The cargo/id type. Default: int Remarks: If the intervals are not associated with cargos/IDs, they will be numbered consecutively.

Metafunctions

Cargo	Type of additional data stored in an object.
Value	Type of the items in the container or behind an iterator.

Member Functions

IntervalTree

Constructor

Functions

addInterval	Adds an interval to an interval tree.
createIntervalTree	Create an interval tree.
findIntervals	Find all intervals that contain the query point or overlap with the query interval.
findIntervalsExcludeTouching	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.
removeInterval	Removes an interval from the interval tree.

Examples

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

File "interval_tree_example.cpp"

1	#include <iostream>
2	#include <seqan/misc/misc_interval_tree.h>
3
4	using namespace seqan;
5
6	int main()
7	{
8	// fill a string of intervals and keys
9	typedef IntervalAndCargo<int, CharString> TInterval;
10	String<TInterval> intervals;
11	appendValue(intervals, TInterval(100, 1000, "gene"));
12	appendValue(intervals, TInterval(100, 300, "exon1"));
13	appendValue(intervals, TInterval(150, 250, "coding1"));
14	appendValue(intervals, TInterval(500, 800, "exon2"));
15	appendValue(intervals, TInterval(600, 700, "coding2"));
16
17	// create IntervalTree of that string
18	IntervalTree<int, CharString> tree(intervals);
19
20	// find intervals that overlap the query interval [550,900)
21	String<CharString> results;
22	findIntervals(tree, 550, 900, results);
23
24	// output corresponding keys
25	for (unsigned i = 0; i < length(results); ++i)
26	std::cout << results[i] << std::endl;
27
28	return 0;
29	}

The resulting keys are:

gene
exon2
coding2

Example Programs

Interval Tree