Context-Free Grammars and String Assembly Index

assemblycfg calculates upper bounds on directed string and molecular assembly indices using the RePair smallest-grammar algorithm. It quickly finds a short assembly path, but it does not guarantee the shortest possible path. It also places lower bounds on assembly index using vector addition chains.

Installation

assemblycfg supports Python 3.12 and later. Install the package from PyPI; its runtime dependencies are installed automatically:

python -m pip install assemblycfg

Plotting is optional. To run the visual examples, install the plot extra:

python -m pip install "assemblycfg[plot]"

String assembly

The central function, repair_with_pathways, returns an upper bound on the assembly index, the virtual objects used along the path, and a NetworkX directed graph representing that path:

import assemblycfg as cfg

length, virtual_objects, path = cfg.repair_with_pathways("abracadabra")
print(f'a("abracadabra") <= {length}')
print(f"Virtual objects used: {virtual_objects}")

Inputs may be a lowercase ASCII string or a list of such strings for a joint assembly path.

With the optional plotting dependency installed, the path can be visualized as follows:

import matplotlib.pyplot as plt
import networkx as nx

nx.draw(path, with_labels=True, font_weight="bold", pos=nx.spring_layout(path))
plt.show()

These graphs can become unwieldy. The AssemblyTheoryTools package provides more sophisticated pathway plotting functions.

Molecular assembly

calculate_assembly_path_det places a valid upper bound on the assembly index of a molecule. It performs especially well on string-like molecules such as lipids. For example:

import assemblycfg as cfg

smiles = "C[C@H](CCCC(C)C)[C@H]1CC[C@@H]2[C@@]1(CC[C@H]3[C@H]2CC=C4[C@@]3(CC[C@@H](C4)O)C)C"
molgraph = cfg.smi_to_nx(smiles)
length, virtual_objects, path = cfg.calculate_assembly_path_det(molgraph)
print(f"a(Cholesterol) <= {length}")

The virtual objects returned by the molecular workflow are NetworkX graphs that represent molecular fragments. More complete programs are available in the examples directory.

Lower bounds from vector addition chains

vac_lower_bound places a valid lower bound on the assembly index of a string, a molecule, or a list of them (bounding their joint assembly index):

import assemblycfg as cfg

print(cfg.vac_lower_bound("abracadabra"))          # 7
print(cfg.vac_lower_bound(cfg.smi_to_nx("CCO")))   # 6

Counting the copies of each basic unit (characters, or bonds by element pair and bond order) maps an object to a vector, and joining two objects adds their vectors. Every assembly pathway is therefore a vector addition chain of the same length, so the shortest chain reaching the object's vector bounds its assembly index from below.

Chains are solved by vac, which is installed on first use with cargo (install Rust from rustup.rs) into ~/.cache/assemblycfg/vac. Set VAC_PATH to use your own build, or VAC_REF to install a specific branch, tag or commit. Without vac, the function warns and returns the closed-form bounds it would start from.

Development

Development dependencies use the standardized dependency-groups table. With a recent version of pip:

python -m pip install --upgrade pip
python -m pip install --group dev -e .
python -m pytest
python -m build
python scripts/check_dist.py

Maintainers should follow the version and Trusted Publishing checklist in RELEASING.md.

Citation

If you use this package, cite the archived software release at doi:10.5281/zenodo.20562899. Complete software citation metadata is provided in CITATION.cff.