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

[Knut Reinert <knut.reinert@fu-berlin.de>]

Ah sorry I meant [1,10] as the first solution.


But then the following algorithm should solve the problem.

1) insert all intervals in an interval tree
2) construct a graph G with nodes for the intervals and edges between nodes if the intervals intersect (edge computation is done using the interval tree)
3) compute the connected components.
4) on each connected component construct the interval as the minimum and maximum coordinates of the corresponding intervals

That can all be done in SeqAn.

my first example you would get a graph G=({1,2,3},{(1,2),(2,3)} and hence get the desired one component

in  your example  you would get two components.

Knut


On Sep 16, 2010, at 10:41 AM, Fabian Buske wrote:

> Hi Knut,
> 
>> Assume { [4,8], [1,5], [6,10]}
>> 
>> the second and third do not overlap. What should be the result?
>> 
>> [4,10]  ?
>> 
>> 
>> or 
>> 
>> [1,8] and [6,10]
>> 
>> 
> Neither of them.
> 
> The outcome should be the same whatever the order of the original intervals.
> 
> Since all of them are overlapping in some direct or indirect way the 
> final result should be [1-10]
> 
> 1-2-3-4-5
>      4-5-6-7-8
>          6-7-8-9-10
> ____________________
> 1-2-3-4-5-6-7-8-9-10
> 
> if there is another set that is completely separated, e.g. 
> {[12,15],[13-17]}, the result should be
> [1-10], [12-17]
> 
> Best,
> Fabian
> 
>>> 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.
>>> 
>> 
>> 
> 
> 
> -- 
> Fabian Buske
> Institute for Molecular Bioscience
> The University of Queensland 
> Brisbane, Qld. 4072 Australia
> Phone: (61)-(7)-334-62608
> 
> 
> _______________________________________________
> seqan-dev mailing list
> seqan-dev@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/seqan-dev

Attachment: smime.p7s
Description: S/MIME cryptographic signature