Data Mining the AlphaFold Protein Universe: How a 1994 Algorithm Found 26.8 Million Co-occurrence Patterns in 77 Million Proteins
Rewrite Apriori as bit-vector arithmetic, put the whole transaction table on a GPU, and one of the oldest algorithms in data mining reads the largest protein database ever assembled in minutes.
In 1994, Rakesh Agrawal and Ramakrishnan Srikant published Apriori, the algorithm that taught retailers that people who buy diapers also buy beer. Thirty years later, the same idea, applied to a very different kind of shopping basket, turns out to be a surprisingly good way to ask a big question: across every protein that AlphaFold has predicted a structure for, which annotations keep showing up together, and how deep do those combinations go?
This post explains the trick that makes that computation feasible, a vectorized reformulation of Apriori, and walks through what it found in the AlphaFold Protein Structure Database. The numbers below come from an independent re-execution of the published pipeline (details at the end).
Proteins as shopping baskets
Apriori works on transactions: sets of items. A transaction is frequent-itemset mining’s unit of observation, and an itemset is frequent if it appears in at least a minimum number of transactions, the support threshold.
The mapping to proteins is direct:
One transaction per protein. The AlphaFold DB (v4) has 214,683,829 entries. 205,620,298 of them have a mean predicted confidence (pLDDT) of at least 50.
Items are annotations. For each protein, its Pfam domain families and Gene Ontology (GO) terms are taken from UniProt TrEMBL, plus one item for its confidence bin (mean pLDDT 50–90 or above 90).
A small, dense vocabulary. Only the 500 most frequent Pfam families and the 500 most frequent GO terms (out of 24,291 and 25,993 seen) are kept, giving 1,006 defined items of which 1,002 actually occur.
After that encoding, 76,890,945 proteins (37.4%) carry at least two items. Those are the transactions that get mined; the other 128.7 million carry only their confidence bin and cannot participate in any pattern. The average mined protein has about four items, the busiest has 46.
The question then becomes: for a threshold as low as eight proteins, enumerate every combination of items that co-occurs at least that often. Combinations of size K are called K-itemsets, and the interesting ones are deep.
Classic Apriori: scan, count, prune, repeat
The original algorithm is level-wise:
1. Count every single item; keep the frequent ones (K = 1).
2. Build candidate pairs from frequent items; scan the whole database counting how many transactions contain each candidate; keep the frequent ones (K = 2).
3. Build candidate triples by joining frequent pairs that share a prefix, prune any candidate with an infrequent subset (the Apriori property: a superset of an infrequent set cannot be frequent), scan the database again, keep the survivors.
4. Repeat until a level produces nothing.
Everything expensive lives in step “scan the database”. The data are stored horizontally, one transaction after another, and each level walks through all of them, matching every transaction’s items against the candidate set, classically with a hash tree. With 77 million transactions, an average of four items each, and millions of candidates per level, that is a lot of pointer chasing, and it happens once per level for twenty-two levels.
Later algorithms changed the layout. Eclat stores the database vertically: for each item, the list of transaction IDs that contain it. The support of an itemset is then the size of the intersection of its items’ lists, and intersections compose: the list for {A, B, C} is the intersection of the list for {A, B} with the list for C. When data are dense enough, the ID lists become bitmaps, and intersection becomes a bitwise AND.
The vectorized formulation
ET-Miner (Efficient Transaction Miner) pushes the vertical, bitmap idea to its logical end and fits it to a GPU.
The database is a bit matrix. Every item gets a bit-vector with one bit per transaction: bit t is set if protein t carries the item. With 1,002 items and 76,890,945 transactions, each vector is 1,201,421 64-bit words and the entire database is 1,002 × 1,201,421 × 8 bytes ≈ 9.6 GB. It fits in the memory of a single modern GPU, so it is uploaded once and never touched from the host again. (A dense boolean table of the same data would be 77 GB; for the full 205.6-million set, 206 GB versus 25.8 GB as bit-vectors.)
Support is a population count. The support of an itemset is the number of set bits in the AND of its items’ vectors. On a GPU, that is a stream of 64-bit AND and popcount instructions over 1.2 million words, followed by a reduction. There is no per-transaction matching, no hash tree, no branching on data; it is memory-bandwidth-bound arithmetic, which is exactly what a GPU is built for.
Level 1 is one popcount per item.
Get Etje’s stories in your inbox
Join Medium for free to get updates from this writer.
Level 2 is a fused kernel over all 501,501 item pairs: for pair (*i*, *j*), AND the two vectors, popcount, compare with the threshold, and write the pair out only if it survives. Counting and filtering happen in the same pass; nothing infrequent ever reaches memory.
Levels 3 and up use the same join as classic Apriori: candidate K-itemsets are formed from frequent (K−1)-itemsets that share a common (K−2)-prefix. The vectorized version exploits that structure: the AND of the shared prefix is computed once per prefix group and reused for every extension, so a candidate costs one additional AND-and-popcount rather than K of them. Candidates are laid out so that a GPU thread block handles one prefix group, results are compacted in place, and the level’s survivors are sorted on the GPU to seed the next level. The Apriori property is still what keeps candidate sets small. It is just applied to sorted integer arrays instead of hash trees.
Two small but important details. First, a candidate whose running AND becomes all zeros can be abandoned early. Second, the loop condition is the same as the original: continue to level K while at least K frequent itemsets exist at level K−1. The algorithm stops on its own when the data run out of depth, with no cap on K.
The difference from the traditional formulation: classic Apriori spends its time moving through transactions to find candidates in them, while the vectorized formulation spends its time on candidates and answers each one with a fixed-size bit operation over all transactions at once. The database layout (vertical bitmaps instead of horizontal transaction lists) is what converts a data-structure-heavy search into dense arithmetic, and the fused count-and-filter kernels are what make the arithmetic cheap enough to run twenty-two levels deep on a 77-million-row table.
The result is exact. There is no sampling and no approximation. Every itemset with support at or above the threshold is enumerated, which is also what makes the outcome checkable, as we will see.
What it found
The published campaign runs the same exhaustive miner at six different support thresholds.
The deepest run is the headline. With a threshold of just eight proteins, the miner enumerates 26,849,505 frequent itemsets. The size distribution at this level is a broad hump that peaks at K = 9 (3,529,257 itemsets, 13.1% of the total) and thins out to 255 itemsets at K = 20, 23 at K = 21, and a single itemset at K = 22.
That single 22-item pattern is shared by exactly eight proteins, and each of the eight has exactly those 22 items and nothing else, which is why the enumeration cannot go deeper. Its members read like the résumé of a neuronal antiviral RNA helicase: the two DEAD/DEAH-box helicase domains (Pfam PF00270 and PF00271), ATP binding, RNA and DNA helicase activity, single- and double-stranded nucleic-acid binding, innate immune response, defense response to virus, cellular response to heat, and a spread of locations from cytosol and nucleus to mitochondrion, axon, dendrite, and nuclear speck, together with the medium-confidence structure bin. None of its 19 GO terms is an ancestor of another, so the depth is not an artifact of GO’s hierarchy.
A few of the intermediate patterns are easier to recognize:
- A 19-item RNA-helicase/spliceosome signature shared by 187 proteins.
- A 17-item receptor-tyrosine-kinase signature (kinase domain PF07714 with SH2 PF00017 and SH3 PF00018) shared by 611 proteins.
- A 12-item bacterial cell-wall synthase signature (transpeptidase PF00905 with transglycosylase PF00912) in about ~10,500 proteins.
Is this just what any big table would produce?
A permutation test says no. Shuffling the annotations among proteins while preserving how many annotations each protein has, then re-mining at the 769-protein threshold, gives about 171,000 frequent itemsets per shuffle against 475,865 in the real data. More telling than the totals is the depth: shuffled data never produce a single itemset beyond K = 6, whereas the real data contain 88,745 itemsets of size seven or more. The deep combinations are properties of biology and of how curators annotate it, not of the table’s marginals.
What it costs
The mining campaign used two consumer RTX 3090 cards. The same run takes 16 minutes on one of them with the single-GPU kernels, or 44 minutes with the chunked two-GPU row-split path that streams every level to disk. Feature extraction reads a 150 GiB compressed UniProt flat file and the AlphaFold metadata table.
What it does not mean
These are co-occurrences of annotations, mined at a chosen threshold, over a vocabulary of the ~1,000 most common labels. They are not mechanisms, and they inherit every bias of how UniProt’s automatic annotation works. The value of the exercise is different: it turns “which combinations of labels exist, how often, and how deep” into a question with an exact, reproducible answer over the entire annotated AlphaFold universe, computed in the time it takes to make coffee.
—
*Apriori: Agrawal & Srikant, “Fast Algorithms for Mining Association Rules”, VLDB 1994.
*AlphaFold DB: Varadi et al. 2024.
*ET-Miner code: github.com/Et9797/ET-miner
