Assembly in Directed Hypergraphs

2025/05/28 by Christoph Flamm, Flamm, Christoph, Daniel Merkle +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Constraint Satisfaction and Optimization #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence

paper · pdf · doi:10.48550/arxiv.2505.22826

openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Assembly theory has received considerable attention in the recent past. Here we analyze the formal framework of this model and show that assembly pathways coincide with certain minimal hyperpaths in B-hypergraphs. This makes it possible to generalize the notion of assembly to general chemical reaction systems and to make explicit the connection to rule based models of chemistry, in particular DPO graph rewriting. We observe, furthermore, that assembly theory is closely related to retrosynthetic analysis in chemistry. The assembly index fits seamlessly into a large family of cost measures for directed hyperpath problems that also encompasses cost functions used in computational synthesis planning. This allows to devise a generic approach to compute complexity measures derived from minimal hyperpaths in rule-derived directed hypergraphs using integer linear programming.

Citations

• Assembly Theory and its Relationship with Computational Complexity
• Assembly Theory is an approximation to algorithmic complexity based on LZ compression that does not explain selection or evolution
• Assembly Theory: What It Does and What It Does Not Do
• Assembly theory explains and quantifies selection and evolution
• On the Salient Limitations of the Methods of Assembly Theory and their Classification of Molecular Biosignatures
• Chemical Transformation Motifs - Modelling Pathways as Integer\n Hyperflows
• A Software Package for Chemically Inspired Graph Transformation
• Generic Strategies for Chemical Space Exploration
• Inferring Chemical Reaction Patterns Using Rule Composition in Graph\n Grammars
• Chemical Organisation Theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• General methods for the construction of complex molecules

Cited by

• Saturation-Based Atom Provenance Tracing in Chemical Reaction Networks
• Historical Contingencies Steer the Topology of Randomly Assembled Graphs

Related

• The Number of Ways to Assemble a Graph
• Assemblies as Graph Processes
• Quantifying the pathways to life using assembly spaces
• Defining Pathway Assembly and Exploring its Applications
• Atlasing of Assembly Landscapes using Distance Geometry and Graph Rigidity