Re: [Seqan-dev] Merging/Melting a bunch of intervals
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
