Re: [Seqan-dev] Merging/Melting a bunch of intervals

[Fabian Buske <f.buske@uq.edu.au>]

Hi Knut,

my problem at hand can be defined as follows:

I start of with a set of intervals. That is a set of pairs of integers 
defining the interval start and end point. This two integers do not 
necessarily span the same range in all the intervals in the set.

I then like to merge all overlapping/intersecting intervals. This may be 
done on the fly while constructing a new data structure.

It looks as if the IntervalTree would be the perfect datastructure to 
use since its storing the current sets of (non-overlapping) intervals 
which can be easily queried given the new interval to be added.

If the query interval overlaps one or potentially several intervals 
stored in the Tree all of them should be merged to obtain the spanning 
Interval (union of all intervals overlapping the query one).

It should be straightforward to simply remove the set of overlapping 
intervals from the IntervalTree and then add the spanning Interval.

According to wiki deletion of nodes from an interval tree may be tricky 
but should be possible
http://en.wikipedia.org/wiki/Interval_tree#Deletion

It seems that deletion of nodes (intervals) from the IntervalTree data 
structure contained in seqan is not supported yet.

I was wondering if I'm mistaken or if there is another straightforward 
way I'm not aware of.

Thanks a lot!

Best,
Fabian


Knut Reinert wrote:
> Dear Fabian,
>
> your problem is not yet well posed.
>
> Currently, an obvious solution (which you probably will not like) is to create a single interval using the overall minimum and maximum
> coordinate of your intervals.
>
> Can you elaborate more on your problem?
>
> Knut
>
> On Sep 16, 2010, at 7:00 AM, Fabian Buske wrote:
>
>   
> > I like to merge a bunch of intervals in case they overlap such that in 
> > the end any single point will be covered by at most interval.
> >     
>
>   


--
Fabian Buske
Institute for Molecular Bioscience
The University of Queensland 
Brisbane, Qld. 4072 Australia
Phone: (61)-(7)-334-62608