Embedding Biological Sequences for Similarity Search

The case for embedding sequences instead of aligning them is usually made as an assertion about speed. It is worth deriving, because the size of the gap decides whether the approximation is worth its costs, and the derivation is short.

The search that does not finish

Fix a concrete task: one query protein of 300 residues against a database of 100 million protein sequences with a mean length of 300 residues. That is roughly the scale of a comprehensive protein database today. You want the sequences most similar to the query.

There are two shapes of answer. Compare the query to every database entry with an alignment algorithm, which is exact but pays a per-comparison cost that scales with the product of the two lengths. Or map every sequence to a fixed-length vector once, in advance, and compare vectors, which pays a much smaller per-comparison cost but answers a different question.

Costing an exhaustive scan

Smith-Waterman fills a matrix of m by n cells. For a 300-residue query against a 300-residue subject that is 90,000 cell updates. Across 100 million subjects:

cells per pair      300 x 300           = 9.0e4
pairs               1.0e8
total cell updates  9.0e4 x 1.0e8       = 9.0e12

Cell-update rates are quoted in the literature in CUPS, cell updates per second. Assume, as a stated assumption rather than a measurement, a well-vectorised implementation sustaining 10 GCUPS — 10 billion cell updates per second — on one machine. Then:

9.0e12 / 1.0e10 CUPS = 900 seconds  (15 minutes, one query)

Fifteen minutes per query is the number that shaped this field. Seed-and-extend heuristics exist precisely to cut it, and they do, typically by two to three orders of magnitude, by never filling most of those matrices at all — that is the mechanism in how BLAST searches. The trade there is sensitivity to remote homologues.

Costing a vector scan

Now embed each sequence as a single vector — a mean-pooled representation from a sequence model, of dimension 1,280 for the 650-million-parameter ESM-2 checkpoint. Similarity is a dot product, which is d multiply-accumulate operations, independent of sequence length:

operations per pair   1,280 MACs
pairs                 1.0e8
total                 1.28e11 MACs  = 2.56e11 flops

at 1e12 flops/s sustained (stated assumption, modest
for a single accelerator on a memory-bound reduction):

  2.56e11 / 1e12  = 0.26 seconds

Compare like with like: 9.0e12 cell updates against 1.28e11 multiply-accumulates, a factor of about 70 in raw operation count, and about 3,500 in the wall-clock estimates above because the vector operation is a dense contiguous reduction and the alignment matrix is not. Even the operation-count ratio understates it, because the embedding scan is a single dense matrix-vector product against a contiguous array while the alignment scan has a data dependency between adjacent cells.

The real cost of the embedding approach has moved somewhere else: you must embed 100 million sequences once, before any query, and store the result. At 1,280 dimensions in 32-bit floats that is 5,120 bytes per sequence, so 512 GB. In 16-bit floats, 256 GB. Product quantisation to 96 bytes per vector brings it to 9.6 GB, at some cost in recall — the same trade discussed in vector quantisation and vector storage cost.

What an index adds on top

The 0.26 seconds above is a brute-force scan of every vector. An approximate nearest-neighbour index cuts that further by not looking at most of them. A graph index such as HNSW navigates from an entry point toward the query through a small number of hops, touching on the order of thousands of vectors rather than 100 million, which brings a single query into the low milliseconds — see how HNSW navigates.

The word doing the work is approximate. The index returns the true nearest neighbours only most of the time, and the recall is a tunable parameter traded against latency. For a similarity search whose results a human will inspect, recall in the high nineties is usually fine. For a search whose negative result you intend to rely on — “no homologue exists” — approximate recall is the wrong tool, because the one hit you missed is the answer.

Two practical details decide whether the numbers above hold. Vectors should be L2-normalised if you are using inner product as a proxy for cosine, or the magnitude of the embedding — which for mean-pooled representations correlates with sequence length — leaks into the ranking. And the index must be built with the same model and the same pooling as the queries; mixing checkpoints silently degrades everything, since two models’ vector spaces have no reason to be aligned.

A third detail appears only at this scale. The 512 GB of float32 vectors above does not fit in one machine’s memory, and a graph index degrades badly once it has to page from disk, because its traversal is random access by construction. The three resolutions are quantising until the vectors fit, sharding across machines and merging per-shard results, or adopting an index designed to be disk-resident. Each changes the recall-versus-latency curve, so the millisecond figure quoted for an in-memory index is not what a hundred-million-vector deployment returns until you have chosen one of them and measured it.

What you give up

• There is no alignment. An alignment tells you which residues correspond, where the insertions are and which domains are shared. A cosine similarity is one number. For most biological questions the correspondence is the answer and the ranking is just how you found the candidates, which is why the practical pattern is embedding search as a retrieval stage followed by alignment on the top few hundred hits.
• There is no E-value. Alignment scores come with calibrated statistics that say how surprising a score is given the database size. A cosine of 0.82 has no such calibration and its meaning shifts with the model, the pooling and the composition of the corpus. You can build an empirical null by scoring random pairs from your own database, and if you are going to threshold on similarity you should.
• Pooling destroys locality. Mean-pooling a multi-domain protein averages domains together, so a query that shares one domain with a subject and nothing else can land far away. Per-domain or per-window embeddings fix this at the cost of a larger index.
• The model is a dependency. Re-embedding 100 million sequences is not a small operation, so a model upgrade is an index rebuild. Alignment has no such coupling: the algorithm from 1981 still reads the database from last night. Budget the rebuild before you commit to the architecture, because it is a recurring cost rather than a one-off: every new sequence added to the database must also be embedded with the same checkpoint, so the model you chose constrains the pipeline for as long as the index lives. The arithmetic for one such build is worked in what it costs to embed a genome.