Retaining rows that have percent overlapping ranges in Pandas

user_3938025 0
Viewed 406

I have a dataframe with the columns:

[id, range_start, range_stop, score]

If two rows have a range overlap by x percentage I retain the row with the higher score. However, I am confused how to pull out rows with no overlap to other ranges. I am using a nested loop and recursion to condense overlapping ranges into a new dataframe. However, this structure causes all rows to be retained when I am looking for the non overlapping rows.

## This is my function to recursively select the highest scoring overlapping regions

def overlap_retention(df_overlap, threshold, df_nonoverlap=None):
     if df_nonoverlap != None:
          df_nonoverlap = pd.DataFrame()
     
     df_overlap = pd.DataFrame() 
    
     for index, row in x.iterrows():
          rs = row['range_start']
          re = row['range_end']

          ## Silly nested loop to compare ranges between all rows 
          for index2, row2 in x.drop(index).iterrows():   
               rs2 = row2['range_start']
               re2 = row2['range_end']
               readRegion=[*range(rs,re,1)]
               refRegion=[*range(rs2,re2,1)]
               regionUnion = set(readRegion).intersection(set(refRegion))
               overlap_length = len(regionUnion)
            
               overlap_min = min(rs, rs2)
               overlap_max = max(re, re2)
               overlap_full_range = overlap_max-overlap_min

               overlap_percentage = (overlap_length/overlap_full_range)*100

               ## Check if they overlap by x_percentage and retain the higher score
               if overlap_percentage>x_percentage:
                    evalue = row['score']
                    evalue_2 = row2['score']
            
                    if evalue_2 > evalue:
                          df_overlap = df_overlap.append(row2)
                    else:
                         df_overlap = df_overlap.append(row)
#----------------------------------------------------------
                ## How to find non-overlapping rows without pulling everything?
               else:
                    df_nonoverlap = df_nonoverlap.append(row)
# ---------------------------------------------

          ### Recursion here to condense overlapped list further
          if len(df_overlap)>1:
              overlap_retention(df_overlap, threshold, df_nonoverlap)
          else:
              return(df_nonoverlap)

An example input is below:

data = {'id':['id1', 'id2', 'id3', 'id4', 'id5', 'id6'],
       'range_start':[1,12,11,1,20, 10],
       'range_end':[4,15,15,6,23,16],
       'score':[3,1,8,2,5,1]}
input = pd.DataFrame(data, columns=['id', 'range_start', 'range_end', 'score'])

The desired output can change based on the overlap threshold. In the example above id1 and id4 may both be retained or simply id1 depending on the overlap threshold:

data = {'id':['id1', 'id3', 'id5'],
       'range_start':[1,11,20],
       'range_end':[4,15,23],
       'score':[3,8,5]}
output = pd.DataFrame(data, columns=['id', 'range_start', 'range_end', 'score'])
pandas dataframe recursion overlap python
2 Answers

You can make a cartesian join between all the ranges, then find length and % of the overlap for each pair, and filter it based on the x_overlap threshold.

After that, for each range we can find the overlapping range with the highest score (which could be the range itself, with the overlap of 100%):

# set min overlap parameter
x_overlap = 0.5

# cartesian join all ranges
z = df.assign(k=1).merge(
    df.assign(k=1), on='k', suffixes=['_1', '_2'])

# find lengths of overlaps
z['len_overlap'] = (
    z[['range_end_1', 'range_end_2']].min(axis=1) -
    z[['range_start_1', 'range_start_2']].max(axis=1)).clip(0)

# we're only interested in cases where ranges overlap, so the total
# range is the range between min(start1, start2) and max(end1, end2)
z['len_total'] = (
    z[['range_end_1', 'range_end_2']].max(axis=1) -
    z[['range_start_1', 'range_start_2']].min(axis=1)).clip(0)

# find % overlap and filter out pairs above threshold
# these include 'pairs' where a range is paired to itself
z['pct_overlap'] = z['len_overlap'] / z['len_total']
z = z[z['pct_overlap'] > x_overlap]

# for each range find an overlapping range with the highest score
# (could be the range itself)
z = z.sort_values('score_2').groupby('id_1')['id_2'].last()

# filter the inputs
df_out = df[df['id'].isin(z)]

df_out

Output:

    id  range_start  range_end  score
0  id1            1          4      3
2  id3           11         15      8
4  id5           20         23      5

P.S. Please note that it is not very clear what should happen with id4 in your example. Since you don't have it in your output, I assumed (hopefully correctly) that you're not interested in zero-length ranges in the output

P.P.S. There is a new syntax for cartesian join in pandas 1.2.0+ with how=cross parameter in the merge method. I've used in my answer a version with a dummy variable k=1, which is more verbose, but compatible with older versions

user_67927430

I think you need a very clear definition of overlap. If you have [2;7], [6;10] and [7;8], which one overlaps with which one ?

Avoid using input as a variable name, it shadows the function input() (to get input from the user)

If you want to select clear overlaps (only the start or the end differs), and you only have at most ONE overlap, here you go:

sorted_df = df.sort_values(by=["range_start"])
starts_earlier = sorted_df[sorted_df.range_end.shift(-1) == sorted_df.range_end]

sorted_df = df.sort_values(by=["range_end"])
ends_earlier = sorted_df[sorted_df.range_start.shift(-1) == sorted_df.range_start]

Then you can do a df.drop(starts_earlier.index) and df.drop(ends_earlier.index) to remove the shorter ones/

df.shift() : https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.shift.html

This code won't work for multiple overlapping segments. If you are interested in that, let me know.

user_47676450
Related