I have a BLAST tabular output with millions of hits.Query is my sequence and subject is a protein hit. I am interested in finding the subjects corresponding to the same query that do not overlap. If I know the subject start and end sites it becomes possible to do; if S1 < E2 < S2 and E1 < S2 < E2 OR S2 - E1 > 0 Basically, since there are many hits and number of subjects vary, I may understand the algorithm, but find it difficult to implement in code. For example,my input file

```
query  subject  start end
cont20 EMT34567 2   115 
cont20 EMT28057 238 345
cont31 EMT45002 112 980
cont31 EMT45002 333 567
```

Desired output (I want the program to print only the query and subject names that do not overlap)

```
cont20 EMT28057 
cont20 EMT34567
```

I have started the script using regex, but I am not sure how to continue or if this is a right way

```py
import re
output=open('result.txt','w')
f=open('file.txt','r')
lines=f.readlines()
for line in lines:
    new_list=re.split(r'\t+',line.strip())
    query=new_list[0]
    subject=new_list[1]
    s_start=new_list[8]
    s_end=new_list[9]
```
<p><strong>UPDATED:</strong></p>

<p>Input: <code>file.txt</code></p>

<pre><code>query    subject    start    end    
contig1    EMT16196    481    931
contig15    EMT15298    1    148
contig18    EMT04099    1    290
contig18    EMT20601    1    290
contig18    EMT23062    1    290
contig20    EMT14935    298    524
contig20    EMT19916    415    434
contig20    EMT19915    422    441
contig20    EMT19914    298    317
contig29    EMT30092    1    20
contig30    EMT31940    61    795
contig35    EMT03428    181    785
contig37    EMT02979    364    1184
contig42    EMT19888    449    657
contig42    EMT19888    339    472
contig43    EMT19888    339    657
contig45    EMT27750    329    363
contig45    EMT17965    889    908
contig51    EMT32871    324    390
contig51    EMT32871    203    241
contig52    EMT15568    107    127
contig56    EMT28040    811    939
contig67    EMT32527    132    489
contig69    EMT12559    38    226
contig79    EMT05411    85    919
contig95    EMT26862    138    327
contig95    EMT10613    20    164
contig107    EMT33347    1    243
contig107    EMT33347    255    387
contig107    EMT14531    135    385
contig108    EMT33347    1    423
contig108    EMT14531    135    565
contig109    EMT07436    60    88
contig149    EMT17561    119    219
contig159    EMT28057    39    307
contig176    EMT23021    359    379
</code></pre>

<p>Python:</p>

<pre><code>from itertools import groupby

def nonoverlapping(hits):
    """Returns a list of non-overlapping hits."""
    nonover = list(hits)
    overst =  False
    for i in range(1,len(hits)):
        (p, c) = hits[i-1], hits[i]
        # Check whether hits overlap.
        if c[2]&lt;=p[3]:
            if not overst: nonover.remove(p)
            nonover.remove(c)
            overst = True
        else:
            overst = False     
    return nonover

fh = open('file.txt')
oh = open('results.txt', 'w')
fh.next() # Ignore header line in BLAST output.

# Loop over BLAST hits (grp) for each query (qid).
for qid, grp in groupby(fh, lambda l: l.split()[0]):
    hits = []
    # I need to convert start and end positions
    # from strings into integers.
    for line in grp:
        hsp = line.split()
        hsp[2], hsp[3] = int(hsp[2]), int(hsp[3])
        hits.append(hsp)
    # Sort hits by start position.
    hits.sort(key=lambda x: x[2])
    for hit in nonoverlapping(hits):
         oh.write('\t'.join([str(f) for f in hit])+'\n')
</code></pre>

<p>Results: <code>results.txt</code></p>

<pre><code>contig1    EMT16196    481    931
contig15    EMT15298    1    148
contig29    EMT30092    1    20
contig30    EMT31940    61    795
contig35    EMT03428    181    785
contig37    EMT02979    364    1184
contig43    EMT19888    339    657
contig45    EMT27750    329    363
contig45    EMT17965    889    908
contig51    EMT32871    203    241
contig51    EMT32871    324    390
contig52    EMT15568    107    127
contig56    EMT28040    811    939
contig67    EMT32527    132    489
contig69    EMT12559    38    226
contig79    EMT05411    85    919
contig109    EMT07436    60    88
contig149    EMT17561    119    219
contig159    EMT28057    39    307
contig176    EMT23021    359    379
</code></pre>
