<p>Hi,</p>

<p>I‘ve got a list of genomic regions in python, say:</p>

<pre><code>list=["chr1: 100-300", "chr1:150-350", "chr1:200-400", "chr1:500-700", "chr1:600-800", "chr1:900-1000"]
</code></pre>

<p>Some of them overlap each other. I wanna create a new list contain subsets of genomic regions and without overlapping regions in each subset. The result should be something like:</p>

<pre><code>new_list=[["chr1:100-300", "chr1:500-700", "chr1:900-1000"], ["chr1:150-350", "chr1:600-800"], ["chr1:200-400"]]
</code></pre>

<p>I created my own function but it tooks 20 mins to achieve the result, if the origin list contain 1000 regions. </p>

<p>Is there any quick way to do that? Please help.</p>

I would build a recursive function

    def disjoint(l, res=[]):
        sl = []
        n = 1
        while n < len(l):
            p,q = l[n-1:n+1]
            if p[2] >= q[1] and p[0]==q[0]:
               l.remove(q)
               sl.append(q)
            else:
                n+=1
        res.append(l)
        if sl: disjoint(sl, res)
        return res

Running it on your example:

    l = [('chr1',100,300), ('chr1', 150, 350), ('chr1', 200, 400), ('chr1', 500, 700), ('chr1',600, 800), ('chr1', 900, 1000)] 
    print disjoint(l)

Gives you what you want:

    [[('chr1', 100, 300), ('chr1', 500, 700), ('chr1', 900, 1000)], [('chr1', 150, 350), ('chr1', 600, 800)], [('chr1', 200, 400)]]