Revisiting my undergrad thesis | Finding molecules, then and now

In the spring of 2008, in Havana, my friend Yadir Martínez Vergara and I spent eight months on one question: given a small piece of a molecule, which molecules in a database contain it?

It was our diploma project at the University of Information Sciences, part of GRAph TOol, a platform the Centro de Química Farmacéutica and the university's bioinformatics group were building to predict the biological activity of organic compounds. Chemists there wanted to select a fragment on screen, say two chlorine atoms on neighbouring carbons, and find every compound in their library of about 180,000 that had the same shape.

I recently reread the thesis, eighteen years later, and decided to do something I never had time for back then: rebuild the algorithm and measure it against how chemists search today. This post is what I found.

What we built

A chemist picked the fragment in a Java desktop client (the 3D viewer was Jmol). The search itself didn't run on that machine. A compute server, written by students and professors in our lab, cut the job into work units and handed them to whatever PCs were free. If a unit took too long, it was marked expired and given to someone else. Results came back, the server stitched them together, and the chemist watched the matches arrive.

That was 2008, on lab computers, with no cloud and a MySQL database holding every molecule's 2D and 3D coordinates.

The algorithm

Most chemistry software treats a molecule as a graph: atoms are nodes, bonds are edges, and finding a fragment is a subgraph problem. We did something less common. We treated the molecule as geometry.

First, any molecule with fewer bonds than the fragment is skipped. Then the search looks for a seed: a bond between the same two elements, of the same type. From there it grows the match one connected bond at a time. Each new bond has to agree on the angles it forms with the bonds already matched, which we computed with the law of cosines, within a tolerance the chemist chose. We used 10%. If nothing fits, the search undoes the last bond and tries the next candidate. In 3D the same loop also checks distances and dihedral angles, the twist between four atoms.

Try it below. Pick a fragment and a molecule, then press Play. The first molecule in the list is the one from the screenshot in our thesis.

Two things are worth watching. Search for Cl–C–C–Cl in 1,2-dichlorobenzene: the atoms are all there, but the carbon–carbon bond is aromatic, not single, so the match fails at the bond check. Then search for the benzene ring in benzophenone and count the backtracks. Rings are where this kind of search spends its time.

What the numbers said

We tested on the first 100 molecules of the database: ten random fragments of 4 to 13 atoms, in 2D and 3D. A search took between 0.7 and 1.8 seconds. Scaled to the whole database, that's at least 26 minutes per search, and up to 35 once the database was under load.

One result puzzled us. The slowest search wasn't the biggest fragment; it was a six-atom one. It was a benzene ring, the most common ring in organic chemistry. Almost every molecule passes the early checks, so the algorithm has to go all the way down every time.

The same search in 2026

This month I rebuilt the matcher in Python and ran it on 180,000 drug-like molecules from the public ZINC dataset, against two modern approaches built on RDKit, the open-source chemistry toolkit:

• Graph matching. Every molecule is checked with a VF2-style subgraph matcher. No geometry, just atoms and bonds.
• Fingerprint screen, then graph matching. Each molecule gets a fingerprint ahead of time, a short string of bits made by hashing its small substructures. If the fragment's bits aren't all present in a molecule's fingerprint, that molecule can't contain the fragment, and it's skipped without a match ever being attempted.

Most of the jump from 26 minutes to 8.5 seconds is not the algorithm. It's eighteen years of hardware, and data that sits in memory instead of being fetched molecule by molecule from a database across a lab network. The algorithm itself held up: within a factor of ten of a modern graph matcher written in C++, on the same machine, while doing extra geometry work.

The fingerprint screen is where the real gain is. For a rare fragment it rules out 99.9% of the database before matching starts, and a search takes about a sixth of a second.

And benzene? It's still the slow one. A ring that sits in 77% of all molecules can't be screened out, so the screened search costs as much as checking everything. The trick that saves seconds on rare fragments buys nothing on common ones, which is exactly what our six-atom search was telling us in 2008.

What I'd keep

Reading the thesis now, I wince at a few things: the orientation-dependent slopes, a 10% tolerance picked because it felt right, a sample of ten fragments. But I'd keep more than I expected.

We wrote an algorithm simple enough to prove things about, and we did: we counted its operations and showed it was cubic in the worst case. We measured it honestly, including the result that didn't fit the story. And we asked a question that, two decades later, still has the same shape: how do you avoid doing expensive work on data that can't possibly be the answer?

The answer then was a careful loop. The answer now is a cheap filter in front of a careful loop. That second half is the part I'd go back and tell us about.

Our thesis, "Módulo de búsqueda de fragmentos de estructuras químicas para la Plataforma GRAph TOol" (2008), is in the UCI Digital Repository. It was written with Yadir Martínez Vergara under the guidance of Dr. Ramón Carrasco Velar, MSc. Aurelio Antelo Collado and Ing. Yania Molina Souto. If you'd like the benchmark code to run it yourself, write to me.