The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
IntervalTree-0.05
River stage zero No dependents
++
/ IntervalTree

NAME

IntervalTree.pm

VERSION

Version 0.01

DESCRIPTION

Data structure for performing intersect queries on a set of intervals which preserves all information about the intervals (unlike bitset projection methods).

SYNOPSIS

Data structure for performing window intersect queries on a set of of possibly overlapping 1d intervals.

Usage =====

Create an empty IntervalTree

    use IntervalTree;
    my $intersecter = IntervalTree->new();

An interval is a start and end position and a value (possibly None). You can add any object as an interval:

    $intersecter->insert( 0, 10, "food" );
    $intersecter->insert( 3, 7, {foo=>'bar'} );

    $intersecter->find( 2, 5 );
    # output: ['food', {'foo'=>'bar'}]

If the object has start and end attributes (like the IntervalTree::Interval class) there is are some shortcuts:

    my $intersecter = IntervalTree->new();
    $intersecter->insert_interval( IntervalTree::Interval->new( 0, 10 ) );
    $intersecter->insert_interval( IntervalTree::Interval->new( 3, 7 ) );
    $intersecter->insert_interval( IntervalTree::Interval->new( 3, 40 ) );
    $intersecter->insert_interval( IntervalTree::Interval->new( 13, 50 ) );

    $intersecter->find( 30, 50 );
    # output: [IntervalTree::Interval(3, 40), IntervalTree::Interval(13, 50)]

    $intersecter->find( 100, 200 );
    # output: []

Before/after for intervals

    $intersecter->before_interval( IntervalTree::Interval->new( 10, 20 ) );
    # output: [IntervalTree::Interval(3, 7)]

    $intersecter->before_interval( IntervalTree::Interval->new( 5, 20 ) );
    # output: []

Upstream/downstream

    $intersecter->upstream_of_interval(IntervalTree::Interval->new(11, 12));
    # output: [IntervalTree::Interval(0, 10)]
    $intersecter->upstream_of_interval(IntervalTree::Interval->new(11, 12, undef, undef, "-"));
    # output: [IntervalTree::Interval(13, 50)]

    $intersecter.upstream_of_interval(IntervalTree::Interval->new(1, 2, undef, undef, "-"), 3);
    # output: [IntervalTree::Interval(3, 7), IntervalTree::Interval(3, 40), IntervalTree::Interval(13, 50)]

insert

Insert the interval [start,end) associated with value `value`.

find

Return a sorted list of all intervals overlapping [start,end).

before

Find `num_intervals` intervals that lie before `position` and are no further than `max_dist` positions away

after

Find `num_intervals` intervals that lie after `position` and are no further than `max_dist` positions away

insert_interval

Insert an "interval" like object (one with at least start and end attributes)

before_interval

Find `num_intervals` intervals that lie completely before `interval` and are no further than `max_dist` positions away

after_interval

Find `num_intervals` intervals that lie completely after `interval` and are no further than `max_dist` positions away

upstream_of_interval

Find `num_intervals` intervals that lie completely upstream of `interval` and are no further than `max_dist` positions away

downstream_of_interval

Find `num_intervals` intervals that lie completely downstream of `interval` and are no further than `max_dist` positions away

traverse

call fn for each element in the tree

IntervalTree::Node

A single node of an `IntervalTree`.

NOTE: Unless you really know what you are doing, you probably should us `IntervalTree` rather than using this directly.

insert

Insert a new IntervalTree::Node into the tree of which this node is currently the root. The return value is the new root of the tree (which may or may not be this node!)

intersect

given a start and a end, return a list of features falling within that range

left

find n features with a start > than `position` f: a IntervalTree::Interval object (or anything with an `end` attribute) n: the number of features to return max_dist: the maximum distance to look before giving up.

find n features with a end < than position f: a IntervalTree::Interval object (or anything with a `start` attribute) n: the number of features to return max_dist: the maximum distance to look before giving up.

IntervalTree::Interval

Basic feature, with required integer start and end properties. Also accepts optional strand as +1 or -1 (used for up/downstream queries), a name, and any arbitrary data is sent in on the info keyword argument

    $f1 = IntervalTree::Interval->new(23, 36);
    $f2 = IntervalTree::Interval->new(34, 48, {'chr':12, 'anno':'transposon'});
    $f2
    # output: Interval(34, 48, {'anno': 'transposon', 'chr': 12})

AUTHOR

Ben Booth, <benwbooth at gmail.com>

Original Authors:

    James Taylor (james@jamestaylor.org),
    Ian Schenk (ian.schenck@gmail.com),
    Brent Pedersen (bpederse@gmail.com)

BUGS

Please report any bugs or feature requests to bug-intervaltree at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=IntervalTree. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc IntervalTree

You can also look for information at:

ACKNOWLEDGEMENTS

This code was directly ported from the bx-python project:

https://bitbucket.org/james_taylor/bx-python/src/tip/lib/bx/intervals/intersection.pyx

Original Authors:

    James Taylor (james@jamestaylor.org),
    Ian Schenk (ian.schenck@gmail.com),
    Brent Pedersen (bpederse@gmail.com)

Copyright 2012 Ben Booth.

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.