Class
IntervalTreeData structure for efficient interval storage.
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
-
void addInterval(intervalTree, interval);, void addInterval(intervalTree, begin, end[, cargo]);, void addInterval(graph, propertyMap, interval);
Adds an interval to an interval tree. -
void createIntervalTree(intervalTree, intervals[, tag]);, void createIntervalTree(g, pm, intervals[, tag]);, void createIntervalTree(g, pm, intervals, center[, tag]]);
Create an interval tree. -
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. -
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. -
bool removeInterval(intervalTree, iBegin, iEnd, iId);
Removes an interval from the interval tree.
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!