Algorithmic Complexity and Reprogrammability of Chemical Structure Networks

Hector Zenil, Narsis A. Kiani, Ming-Mei Shang, Jesper TegnérarXiv 2018 · arXiv

TL;DR

This paper introduces a novel way to analyze chemical structures by treating them as outputs of computational programs. By applying algorithmic information theory to molecular networks, the researchers can classify compounds and predict physical properties—like boiling point and density—using only the "algorithmic signature" of the molecule's shape, entirely independent of traditional atomic data.

What Problem Does This Paper Address?

In the world of chemoinformatics, researchers typically characterize molecules using "chemical fingerprints" or statistical graph metrics like degree distribution and clustering coefficients. While useful, these methods are often descriptive rather than predictive; they tell us what a molecule looks like, but not necessarily how it behaves or how it might be transformed into something else.

The authors argue that the field needs to move toward causal modeling. The challenge is that "molecular complexity" is notoriously difficult to define. Most existing measures are ad-hoc or depend heavily on which features a researcher chooses to focus on. This paper seeks a more universal, objective measure of complexity rooted in theoretical computer science to better understand the mechanistic "generating programs" behind chemical structures.

Methods

The researchers leverage Algorithmic Information Theory (AIT), specifically the concept of Kolmogorov-Chaitin complexity—the length of the shortest computer program required to reproduce a piece of data (in this case, a molecular graph).

Because calculating true Kolmogorov complexity is mathematically uncomputable, they use two sophisticated approximation techniques:

  • Coding Theorem Method (CTM): This estimates the probability of a small structure appearing based on how often it is generated by random Turing machines.
  • Block Decomposition Method (BDM): Since CTM only works for very small strings or arrays, BDM breaks down large molecular networks into smaller, overlapping blocks, calculates their complexity via CTM, and then reassembles these values into a global complexity score.

A key innovation here is the Information Signature. The authors perform "in silico alchemy" by perturbing the network—systematically removing an atom (node) or a bond (edge)—and measuring how that change affects the overall algorithmic complexity. This allows them to rank elements by their "causal contribution" to the molecule's identity.

Figure 1: Structural diagrams and information signatures of aspirin and statins.

Datasets

The study utilized a massive dataset of 158,399 chemical elements extracted from the Wolfram Language ChemicalData[] function. This dataset spans a wide variety of classes, including:

  • Functional classes: Acids, alcohols, esters, and amines.
  • Physical states: Solids, liquids, and gases.
  • Biological categories: Drugs (including a deep dive into aspirin and statins) and biomolecules like pyrimidines.
  • Chemical types: Organic vs. inorganic, heavy molecules, and hydrocarbons.

Key Insights and Ideas

  • Molecules as Programs: The core "aha moment" is that the topology of a molecule contains a hidden "program." Simple structures (like long chains) have low algorithmic complexity, while highly branched or cyclic structures (like the carbon rings in aspirin) are more complex because they require more "instructions" to describe.
  • Stability via Complexity: In aspirin, the carbon ring is identified as the most stable part of the structure. Removing a bond there drastically simplifies the graph (turning a cycle into a path), which shows up as a massive spike in the information signature.
  • Algorithmic Causal Paths: The difficulty of transforming one chemical into another (e.g., an alcohol to an acid) is reflected in the algorithmic "distance" between them. The researchers found that transformations requiring specific, selective oxidants in the lab also appear more "difficult" or less probable from an algorithmic perspective.
  • Agnostic Classification: Remarkably, the method could separate organic from inorganic compounds and solids from liquids without knowing anything about atomic weights, charges, or valency. The physical properties are seemingly "baked into" the algorithmic structure of the network.

Key Results

  • Physical Property Correlation: The authors found significant (though weak) correlations between a molecule's BDM complexity and its boiling point, melting point, density, and combustion heat. Crucially, no molecule with high physical property values had a high algorithmic probability (low complexity).
  • Class Separation: The method successfully profiled all 558 pyrimidines in the database with high accuracy based on complexity alone.
  • Drug Repositioning: By comparing information signatures, the authors showed that aspirin and statins share structural algorithmic properties that traditional geometric alignments might miss. This provides a potential computational explanation for why these different classes of drugs often show similar clinical benefits in cardiovascular health.
Figure 2: Classification of compound classes by algorithmic complexity and "in silico alchemy" signatures.

Limitations and Future Work

The primary limitation acknowledged is that the current model is "physics-agnostic." It treats all atoms and bonds as identical nodes and edges in a graph, ignoring critical data like atomic charge, valency, and 3D stereochemistry. While the results are impressive despite this, the authors note that incorporating these features as "weights" in the network would likely increase the predictive power.

Future research directions include:

  1. Applying this "interventional calculus" to reaction networks to predict the outcomes of chemical synthesis.
  2. Exploring logical depth as a measure of "sophistication" in drug design.
  3. Generalizing the approach to larger biological systems, such as protein-protein interaction networks.

Summary updated

Abstract

Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of applying a computational interventional calculus based on the principles of algorithmic probability to chemical structure networks. We profile the sensitivity of the elements and covalent bonds in a chemical structure network algorithmically, asking whether reprogrammability affords information about thermodynamic and chemical processes involved in the transformation of different compound classes. We arrive at numerical results suggesting a correspondence between some physical, structural and functional properties. Our methods are capable of separating chemical classes that reflect functional and natural differences without considering any information about atomic and molecular properties. We conclude that these methods, with their links to chemoinformatics via algorithmic, probability hold promise for future research.
BibTeX
@misc{zenil2018algorithmic,
  author = {Hector Zenil and Narsis A. Kiani and Ming-Mei Shang and Jesper Tegnér},
  title = {{Algorithmic Complexity and Reprogrammability of Chemical Structure Networks}},
  year = {2018},
  eprint = {1802.05856},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.05856},
}

Loading related content...

Figure