# Iterative pandas row additions and row dropping

I have written a program that uses pandas dataframes to quickly access and filter data (DNA strings). Come to find out, pandas operations are actually the bottleneck in my program.

## The Program

I begin this part of the program with a df I call clust_prov. The clust_prov df is indexed by unique DNA sequences all of length k. The most important column is cluster, which contains a DNA sequence of at least length k+1. The other columns, prefix, suffix, prefix_rc, and suffix_rc contain strings derived from cluster. As an example, a column may have the cluster GATCATTACGACTGTACTGTACCGGAGAACGGT, and will have the other values as you see below. For this example, let's just consider prefix and suffix_rc for simplicity.

    GATCA                       ACGGT     < For this molecule, the vars are:
5' GATCATTACGACTGTACTGTACCGGAGAACGGT 3'  < prefix    - GATCA
< suffix_rc - ACGGT


My program looks at a cluster and asks if the prefix or suffix_rc matches the prefixes/suffix_rcs of other clusters, merges the two clusters, and starts the whole process over again. This is done iteratively until no more merges can be performed.

My df, clust_prov, has around 70k rows at the beginning of the program, and the joins are sparse so only maybe 20% of clusters are merge-able. Despite the fact that merge operations only occur 20% of the time, the function that handles it, update_by_addition(), takes around 60% of the runtime.

### Pseudocode of real control function

def merge_clusters(clust_prov, try_to_merge_these):
for cluster in try_to_merge_these:
if cluster in clust_prov:   # make sure we haven't already removed it
if cluster.prefix in clust_prov[, [prefix/suffix_rc]]:
cluster,
<cluster that matches if condition above>)


### Actual function I want to speed up

def update_by_addition(clust_prov, new_cluster, old_index,
merge_index, fate_round):
kmerlen = len(old_index)
clust_prov.loc[old_index] += clust_prov.loc[merge_index, ]
clust_prov.loc[old_index, "cluster"] = new_cluster
clust_prov.loc[old_index, "prefix"] = new_cluster[0:kmerlen]
clust_prov.loc[old_index, "suffix"] = seqpy.revcomp(new_cluster[-kmerlen:])
clust_prov.loc[old_index, "prefix_rc"] = seqpy.revcomp(new_cluster[0:kmerlen])
clust_prov.loc[old_index, "suffix_rc"] = new_cluster[-kmerlen:]
try:
clust_prov.loc[old_index, "merged_at"].append(fate_round)
except:
clust_prov.loc[old_index, "merged_at"] = [fate_round]

#we only need this if we don't sum
clust_prov = clust_prov.drop(merge_index)
return clust_prov


## Problem code

The slowest process from kernprof is adding two rows together, followed by dropping a single row.

## What I have done so far

I have tried a few different ways of dropping (like ~ operator). I have not tried anything else for row addition since this seems like the only option.

## Goal

I just need to figure out if there is any way that I can make this faster using pandas, or if I would be better converting everything to a dict of dicts, or some other data structure. Speed really is an issue here, as the current process time for this module in my program is 14hrs for 70k rows.

## Constraints

• This process is iterative, so I cannot vectorize the function, use partial, et cetera for a speed increase. Each operation depends on the addition of the previous two rows and the row that was deleted.
• The DataFrame will be large (>70k rows) and slowly will get smaller as rows are summed/modified, then removed.
• Not every row will eventually need to be modified. For example, I ran my parent program on 500 rows and it only needed to run this update_by_addition method 104 times.

## Profiling Results

Profiling the code with kernprof gives me the following output:

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
780                                           @profile
782                                                                  merge_index, fate_round):
791       104          333      3.2      0.0      kmerlen = len(old_index)
794       104     22786882 219104.6     40.8      clust_prov.loc[old_index] += clust_prov.loc[merge_index, ]
795       104      2882801  27719.2      5.2      clust_prov.loc[old_index, "cluster"] = new_cluster
796       104      3218409  30946.2      5.8      clust_prov.loc[old_index, "prefix"] = new_cluster[0:kmerlen]
797       104      3194060  30712.1      5.7      clust_prov.loc[old_index, "suffix"] = seqpy.revcomp(new_cluster[-kmerlen:])
798       104      3196542  30736.0      5.7      clust_prov.loc[old_index, "prefix_rc"] = seqpy.revcomp(new_cluster[0:kmerlen])
799       104      3214856  30912.1      5.8      clust_prov.loc[old_index, "suffix_rc"] = new_cluster[-kmerlen:]
800       104          477      4.6      0.0      try:
801       104        29723    285.8      0.1          clust_prov.loc[old_index, "merged_at"].append(fate_round)
802       104          126      1.2      0.0      except:
803       104       971903   9345.2      1.7          clust_prov.loc[old_index, "merged_at"] = [fate_round]
804
805                                               #we only need this if we don't sum
807       104     16298261 156714.0     29.2      clust_prov = clust_prov.drop(merge_index)
808       104          321      3.1      0.0      return clust_prov

• Everyone who closed the question: the code is already in there, just not in a format we’re used to because of the profiling metadata. @conchoecia Can you please add a bit more context, especially how this method is called so we know what kind of data you’re manipulating. – Mathias Ettinger Feb 23 '18 at 8:58
• I added some more context. This seems sufficient to get a handle on things? I will happily add more or clarify if needed. – conchoecia Feb 23 '18 at 21:06
• I’m getting back to this question and still have a hard time understanding the algorithm. As far as I understand the code, the size you name k in your prose is kmerlen in the code and is both the size of the index, the prefixes and the suffixes. What I don't exactly get and isn't clear from your pseudo-code, is how you match your elements: should a prefix match with a suffix_rc (and vice versa) or can a prefix match with a prefix (and suffix with suffix)? Also you talk about merging rows but I only understand it as a rewrite. Is new_cluster already a merge of some sort? – Mathias Ettinger Feb 25 '18 at 19:53
• Also what is the fate_round thing? – Mathias Ettinger Feb 25 '18 at 19:54
• @MathiasEttinger, yes I have obfuscated the code where prefixes and suffixes are matched for brevity. fate_round is just a counter to keep track of when we performed the addition command (not really important). I ended up reimplementing my algorithm using python dictionaries instead of pandas and it is very fast. My conclusion is that performing thousands of non-vectorized modifications on large pandas datasets is a bad idea and slow. I believe that I should delete this answer or close it. What do you think? – conchoecia Feb 26 '18 at 23:52