3

I have two large tab-delimited files (>10GB) and I know that when they're sorted, they're identical in content.

However, I'm interested in the order of rows and the index of the swapped ones when they share the same "key" (key here being defined as rows grouped based on Source and Location columns).

In other words, rows between these two files should be only compared against each other when they come from the same group (i.e. when they share the same Source and Location).

So for example, in the example below, rows 4, 5, 6 from file1.tsv should be compared against 4, 5, 6 from file2.tsv

Note: files are normal TSV. Additional spaces are only added here to make columns center- and right-aligned for better visibility. These spaces are not part of the original files

file1.tsv

     Identifier  Position Source  Location
     AY1:2301        87    ch1        14
    BC1U:4010       105    ch1        14
    AC44:1230        90    ch1        15
    AJC:93410        83    ch1        16
    ABYY:0001       101    ch1        16
       ABC:01        42    ch1        16
      HH:A9CX       413    ch1        17
      LK:9310         2    ch1        17
    JFNE:3410       132    ch1        18
    MKASDL:11        14    ch1        18
   MKDFA:9401        18    ch1        18
  MKASDL1:011       184    ch2        50
   LKOC:AMC02        18    ch2        50
     POI:1100       900    ch2        53
    MCJE:09HA        11    ch2        53
   ABYCI:1123        15    ch2        53
     MNKA:410         1    ch2        53

file2.tsv

     Identifier  Position Source  Location
     AY1:2301        87    ch1        14
    BC1U:4010       105    ch1        14
    AC44:1230        90    ch1        15
       ABC:01        42    ch1        16
    ABYY:0001       101    ch1        16
    AJC:93410        83    ch1        16
      HH:A9CX       413    ch1        17
      LK:9310         2    ch1        17
    MKASDL:11        14    ch1        18
    JFNE:3410       132    ch1        18
   MKDFA:9401        18    ch1        18
  MKASDL1:011       184    ch2        50
   LKOC:AMC02        18    ch2        50
     MNKA:410         1    ch2        53
     POI:1100       900    ch2        53
   ABYCI:1123        15    ch2        53
    MCJE:09HA        11    ch2        53

I want to do something similar to a "diff" but at the 'group' level (where rows are only compared when they share the same Source and Location)

I want to extract the original "row numbers" when the order of rows are 'swapped' within the same "Source/Location" "group" (or key).

The whole row should match in terms of content.

But I have no idea how to go about this. I can only think of writing a for loop which would be extremely inefficient when my original dataset has millions of rows.

Expected result:

Group_Source:Location  df1.index  df2.index

ch1:16                         4          6
ch1:16                         6          4
ch1:18                         9         10
ch1:18                        10          9
ch2:53                        14         15
ch2:53                        15         17
ch2:53                        17         14

Assumptions:

  • Both dataframes have the same number of rows
  • Both dataframes are identical (only order of rows are swapped, so if both are sorted by Source, then Location and then Position and then Identifier, then they will be exactly identical)
  • 'Swapped' rows always match exactly in terms of content in all columns
14
  • 1
    Are the line numbers actually part of the file or did you add them to help us understand the question? If they are not part of the file, please remove them so we know what input we will have.
    – terdon
    Commented May 30, 2022 at 10:39
  • 3
    A simple way to handle this is to use some tool that treat tsv etc. as a database and allow sql-like queries to it. Then you can just declare a join condition on Source and Location. There are several tools like this, one example is q.
    – dirkt
    Commented May 30, 2022 at 11:12
  • 1
    There are three cases where a variant is on chr16 in your input, but only two in the output, is that intentional? Also, can we assume that the first fields are unique? Those look like protein positions, and you can have multiple variants affecting the same protein position.
    – terdon
    Commented May 30, 2022 at 11:30
  • 1
    Ah, right. ABC is a HUGO gene name, so I assumed the others were just names I wasn't familiar with, thanks.
    – terdon
    Commented May 30, 2022 at 11:53
  • 2
    Do your files REALLY start with blanks such that the first column is right-aligned? Doe the other columns also start with blanks such that the data values are centered under the column header names? If not and your data is simply TSV then please fix that in your example.
    – Ed Morton
    Commented May 30, 2022 at 12:23

2 Answers 2

5

This is one of those rare occasions when I'd probably use getline due to the size of your input files so we only save a handful of lines in memory at a time instead of >10G:

$ cat tst.awk
BEGIN {
    OFS = "\t"
    print "Group_Source:Location", "df1.index", "df2.index"
}
NR != FNR { exit }
{ srcLoc = $3 ":" $4 }
srcLoc != prevSrcLoc {
    if ( NR > 1 ) {
        diff()
    }
    prevSrcLoc = srcLoc
}
{
    file1[$1,$2] = FNR - 1
    if ( (getline < ARGV[2]) > 0 ) {
        file2[$1,$2] = FNR - 1
    }
}
END { diff() }

function diff(          idPos) {
    for ( idPos in file1 ) {
        if ( file1[idPos] != file2[idPos] ) {
            print prevSrcLoc, file1[idPos], file2[idPos]
        }
    }
    delete file1
    delete file2
}

$ awk -f tst.awk file1.tsv file2.tsv
Group_Source:Location   df1.index       df2.index
ch1:16  6       4
ch1:16  4       6
ch1:18  10      9
ch1:18  9       10
ch2:53  17      14
ch2:53  15      17
ch2:53  14      15

For more info on getline, please read http://awk.freeshell.org/AllAboutGetline.

The above would work even if an Identifier and/or Position was repeated within the input since it's comparing all 4 fields between the 2 files. It does assume that the Source and Location values are in the same order between the 2 files as shown in the sample input.

2
  • 1
    Thank you for this fantastic answer. It does exactly what I need. Do you have any favorite resources online which you would recommend to better understand this type of awk programming? I'm quite new to awk and having trouble understanding some of the lines, such as srcLoc != prevSrcLoc {....
    – paropunam
    Commented May 31, 2022 at 8:22
  • Youre welcome. Thats a test comparing the contents of 2 variables, one containing the current Source and Location values from the current input line, the other those values from the previous input line. It's so we can do something (call diff()) when those key values change. Regarding favorite resources - get the book Effective AWK Programming, 5th Edition, by Arnold Robbins to learn how to write awk scripts. The author provides an online version for reference but everyone should first buy the book to support his work in providing gawk and the documentation. Then lurk here and in stackoverflow.
    – Ed Morton
    Commented May 31, 2022 at 13:51
3

This is relatively straightforward in awk. For example:

$ awk '{ 
        if(FNR==1){
            next
        }
        else if(FNR==NR){
            a[$1]=FNR-1;
        } 
        else if ( a[$1] != FNR-1 ){
            print $3":"$4, FNR-1, a[$1]
        }
    }' file1.tsv file2.tsv 
ch1:16 4 6
ch1:16 6 4
ch1:18 9 10
ch1:18 10 9
ch2:53 14 17
ch2:53 15 14
ch2:53 17 15

Explanation

  • if(FNR==1){ next }: FNR holds the line number (record number) of the file currently being read. So if this is the first line of either input file, just skip it since we don't want to process the header.
  • else if(FNR==NR){ ... }: NR holds the current input line number, irrespective of which file is being read. So if FNR is equal to NR, that means we are reading the first file.
  • a[$1]=FNR-1: so, if this is the first file, store the first field as an index (key) in an associative array whose value will be the current file's line number (FNR), but minus one because we don't want to be counting the header.
  • else if ( a[$1] != FNR-1 ){: this else if is linked to the previous one, so we will only enter this one if FNR is not equal to NR, so only when we are reading the second file. So, if we are reading the second file and the value stored in the a array for this line's first field is not equal to the current file's line number minus one, then we want to print.
  • print $3":"$4, FNR-1, a[$1]: so we print the 3rd field, a : and the 4th field, and then the FNR minus one and the value stored in the a array for this first field.

Finally, to have it pretty printed with padding and the header, use:

$ awk 'BEGIN{
            printf "%-26s%-12s%-12s\n", \
                "Group_Source:Location","df1.index","df2.index"
        } 
        { 
            if(FNR==1){ next }
            else if(FNR==NR){ a[$1]=FNR-1 } 
            else if ( a[$1] != FNR-1){
                printf "%-26s%-12s%-12s\n", $3":"$4, FNR-1, a[$1]
            }
        }' file1.tsv file2.tsv 
Group_Source:Location     df1.index   df2.index   
ch1:16                    4           6           
ch1:16                    6           4           
ch1:18                    9           10          
ch1:18                    10          9           
ch2:53                    14          17          
ch2:53                    15          14          
ch2:53                    17          15          

Important: this approach requires you to keep an albeit small amount of data in memory for every line of the first file (bar the header). This could be an issue for huge files, although probably not on most machines where you're likely to do this sort of operation. If this is a problem, I recommend Ed's answer which should both significantly faster and not have any memory issues.

5
  • 3
    FWIW I could be wrong but I THINK my answer might be a bit faster than yours rather than a bit slower since the larger the hash table the more collisions and so the slower it gets and with >10G of entries I could imagine that becoming an issue, plus awk has to dynamically allocate memory for the hash table as it grows (probably in blocks) so I could imagine that adding a few cycles as the memory needs increase. I dont really expect much difference in speed of execution either way though.
    – Ed Morton
    Commented May 30, 2022 at 13:17
  • 3
    @EdMorton you're not wrong at all. I was just investigating this because I was surprised to see that my approach was twice as fast as yours on the OP's data. But that's just because it's a trivial example. When testing on larger files, your approach is an order of magnitude faster! Granted that might be because I made my test data by concatenating the OPs files many times, so there will be a lot of overlap. Nevertheless, it was faster so it's both more memory efficient and faster. Neat!
    – terdon
    Commented May 30, 2022 at 13:26
  • 1
    I didn't expect a big difference at all. Interesting, thanks for testing it.
    – Ed Morton
    Commented May 30, 2022 at 13:31
  • 1
    Even if you have tons of memory on a machine, using it when you don't have to mean evicting more useful data from disk cache, making the system slower overall. (And with more copy/reallocate as a hash table grows, probably some memory bandwidth.) Commented May 31, 2022 at 3:12
  • FYI I've been chatting with one of the GNU awk developers and apparently, in gawk at least, arrays don't use memory very efficiently and as they grow (and they grow exponentially as they need more memory allocated so as to minimize how many times the reallocation happens) they can end up using huge amounts of memory and require paging which would contribute to the slow down.
    – Ed Morton
    Commented May 31, 2022 at 14:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .