3
\$\begingroup\$

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]]:
                clust_prov = update_by_addition(clust_prov, 
                                       cluster, 
                                      <cluster that matches if condition above>)

Actual function I want to speed up

Code without profiling metadata is:

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
   781                                           def update_by_addition(clust_prov, new_cluster, old_index,
   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
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Mathias Ettinger Feb 23 '18 at 8:58
  • \$\begingroup\$ I added some more context. This seems sufficient to get a handle on things? I will happily add more or clarify if needed. \$\endgroup\$ – conchoecia Feb 23 '18 at 21:06
  • \$\begingroup\$ 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? \$\endgroup\$ – Mathias Ettinger Feb 25 '18 at 19:53
  • \$\begingroup\$ Also what is the fate_round thing? \$\endgroup\$ – Mathias Ettinger Feb 25 '18 at 19:54
  • \$\begingroup\$ @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? \$\endgroup\$ – conchoecia Feb 26 '18 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.