Code, Math, and Algorithms
Assembly Index Explorer
Default first-principles method: This presentation implementation was built de novo from the definitions in the supplemental complexity proof. It is not the split-bound method implemented by the Cronin group. For production-quality Assembly Index calculations, see the Cronin group's work.
As we show in the supplemental complexity proof, the general Assembly Index decision problem, with an assembly space and its allowed joins supplied as input, is NP-complete; minimizing the index is NP-hard. This implementation places a time limit on search and returns the best valid path found within that time. It reports an exact Assembly Index only when the minimum has been proved; otherwise the result is labelled as an upper bound. In the default first-principles method, fragments and joins are generated as needed under the time limit and OS memory/CPU limits. String and Molecule assembly use the same generic lazy assembly-space solver. The Custom objects tab accepts your own objects and permitted joins. Separately selectable published methods are described below.
Cronin group's molecular assembly methods
Research lineage: Split-branch — Marshall et al. (2021) → Exact molecular assembly search — Jirasek et al. (2024) → Graph assembly algorithm — Seet et al. (2025). The earlier split-branch method restricts fragment reuse and supplies an upper bound on unrestricted MA. Jirasek's later exact search removes that restriction; Seet builds on this line with cached assembly states and stronger conditional bounds. Seet is a successor in this research line, rather than a new name for split-branch. Both later methods return an upper bound if stopped before proving optimality. The earlier papers are historical references here; the runnable options are our independent Seet implementation and our separately labelled multicpu extension.
Assembly Theory and Computational Complexity (PDF) Supplemental complexity proof (PDF) Marshall et al. (Cronin group), molecular assembly (2021) Marshall et al. (Cronin group), assembly spaces (2022) Sharma et al. (Cronin group), Assembly Theory (2023) API documentation
Seet multicpu is Assembly Explorer's independently developed parallel extension of the underlying graph assembly method described by Seet et al. (2025). Its independent C++17 implementation uses OpenMP-parallel fragment generation, exact fragment matching, and shared-frontier duplicate-removal search. Workers share checked upper bounds and a memory-bounded state cache. The publication's search branches and conditional bounds (Eqs. 3–4) are preserved; parallel scheduling is an Assembly Explorer extension. A completed, independently checked search proves the minimum; interruption retains the best checked upper bound. The server assigns up to 32 threads and 64 GiB across active methods. Select this alongside serial Seet to compare them; sequential comparisons give each method the full allocation. Preparation counts and the advisory Kilby et al. (2006) weighted-backtrack estimator are displayed separately from the time-budget bar. Execution, estimate limitations, and HPC options.
Compression-guided producing-join — Assembly Explorer (experimental) uses reusable objects and their checked construction recipes as a dictionary. Short greedy completions guide the shared OpenMP frontier toward branches likely to yield smaller pathways. A complete, validated construction can improve the upper bound; heuristic estimates only order the search, while admissible bounds control pruning. Strings, molecules and custom objects share this generic core, based on the Kempes et al. (2025) assembly-space definitions. This algorithm was developed for Assembly Explorer. A finished proof gives the minimum; an interrupted search retains its best checked upper bound. Performance depends on the input and includes the cost of guidance.
Assembly Explorer's de novo producing-join search uses the assembly-space definitions in Kempes et al. (2025), supplement, Section 3. It chooses joins for required objects and reuses constructed fragments, with memoization and lower bounds to prune the search. Strings, molecules and user-defined objects share this core through a common assembly-space representation. A completed proof gives the minimum within the supplied space; an interrupted search retains a validated upper-bound pathway. The search algorithm and parallel execution were developed for this app. Checking the service backend…
RePair upper bound — Siebert et al. (2026), Assembly Spaces, “Upper Bound”, pp. 28–29, adapts Larsson and Moffat's RePair (2000). It repeatedly replaces the most frequent nonoverlapping adjacent pair. For molecules, it compresses a partition into simple paths, then joins those paths. A completed run gives a checked upper-bound pathway. This independent C++17 implementation uses one CPU thread. Where the assembly paper leaves choices open, it uses first-encounter token IDs for ties, input bond order for one path partition, and left-to-right residual joins. Counts are completed RePair pathway candidates. Implementation and provenance details.
RePair + LZ/addition-chain bounds — Siebert et al. (2026), Assembly Spaces, pp. 28–33, pairs a checked RePair construction with a lower relaxation. Strings use non-self-referencing LZ parsing (Charikar et al., 2005), with phrase count minus one in this app's binary-join metric. Molecules use the paper's scalar bond-count addition-chain relaxation (Brauer, 1939). Matching bounds prove the index; otherwise the result is a certified interval. Long dashes show the upper bound and short dashes the lower bound. This independent C++17 implementation uses one thread, the documented RePair conventions, and a complete depth evaluator for the scalar relaxation. Unfinished depth searches retain only previously established bounds. Cost conventions, implementation choices and provenance.
Graph assembly algorithm — Seet et al. (2025), Rapid Exploration of the Assembly Chemical Space of Molecular Graphs, precomputes matching molecular fragments, then searches duplicate removals largest-first with state caching. This independent serial C++17 implementation uses the paper's simple conditional addition-chain bound (Eqs. 3–4) and reconstructs pathways using its supplement's bag-of-pieces procedure. Complete search proves the minimum for the supplied labelled graph; interruption retains a checked upper bound. Input bond order determines unspecified ties. Explicit hydrogens, when supplied, are retained, so literature comparisons require matching graph representations. Counts are assembly states; preprocessing is included in elapsed time. Method variant, verification and provenance.
Batched producing-join — Assembly Explorer (experimental CPU) uses compact object IDs and bit-vector search states, grouping producing-join expansions into batches. It shares its scheduler, bounds and checked-pathway construction with the matched CUDA variant, with one CPU search thread. Strings, molecules and custom objects use the same generic core based on the Kempes et al. (2025) assembly-space definitions. Its representation and scheduling differ from the OpenMP solver. Complete search proves the minimum; interrupted search retains a checked upper bound.
Batched producing-join — Assembly Explorer (experimental CUDA) runs child-state construction and incumbent-cost pruning on the GPU, with one CPU coordinator handling object discovery, scheduling and pathway checks. This is an Assembly Explorer adaptation of operator batching described by Chakroun and Melab (2013), using the same assembly search as the matched batched CPU option. Proof requires all branches and device batches to finish. Timing includes GPU startup, transfers and checks; speedup depends on the workload.
Pooled-subtree producing-join — Assembly Explorer (experimental CPU) assigns disjoint search branches to resumable depth-first lanes and advances each for several steps per batch. Lazy object discovery supplies additional recipes when needed. This one-thread C++ implementation is the matched control for the CUDA subtree variant. Its pruning and traversal order differ from the packed-batch and OpenMP variants. The assembly model follows Kempes et al. (2025); the execution design adapts the subtree/work-pool ideas discussed by Gmys et al. (2017). A minimum is proved only when every owned branch is complete.
Pooled-subtree producing-join — Assembly Explorer (experimental CUDA) advances resumable search lanes on the GPU, with a warp collaborating on each lane. One CPU coordinator supplies lazily generated objects and recipes and checks candidate pathways. It shares its search with the matched subtree CPU option. This Assembly Explorer adaptation draws on operator batching from Chakroun and Melab (2013) and subtree/work-pool designs from Gmys et al. (2017); the cited papers solve different optimization problems. Unfinished lanes, pending recipes or interrupted transfers retain upper-bound status.
Hypergraph ILP — adaptation of Flamm et al. (2025), Assembly in Directed Hypergraphs, represents object and recipe choices with binary variables. This independent specialization preserves the app's ranked binary joins for strings, molecular fragments and custom objects, rather than adopting the paper's chemical rewriting model. It builds the complete finite ancestor graph, then runs integer branch-and-bound with one CPU thread and HiGHS numerical relaxations. Exact integer bound checks and checked pathways govern pruning; proof also requires complete model generation and exhausted search. Model construction is included in the time limit.
Primal-dual LP — Flamm et al. (2025) adaptation (experimental CPU) uses our generic finite-DAG formulation of Assembly in Directed Hypergraphs. Batches of numerical relaxations use an independently implemented specialization of Chambolle–Pock (2011), Algorithm 1. One CPU thread runs the search and numerical updates. Exact integer lower-bound checks and independently validated pathways control pruning and reported results. Complete model generation, exhausted branches and a timely clean exit are required for proof; preprocessing is included in the time limit. This assembly adaptation is distinct from the publication-labelled baselines.
Primal-dual LP — Flamm et al. (2025) adaptation (experimental CUDA) shares its search and generic model with the CPU primal-dual option, based on Flamm et al. (2025). The GPU computes batched sparse-matrix updates using an independently implemented specialization of Chambolle–Pock (2011), Algorithm 1. One CPU coordinator generates the model, certifies lower bounds with exact arithmetic and validates pathways. GPU numerical output supplies proposals, while checked bounds and complete branch accounting determine proof. Timing includes preprocessing, GPU startup and transfers. The isolated GPU worker is shared with the other CUDA options.
All algorithms offered here are new implementations developed for Assembly Explorer. Publication-based methods cite their sources; adaptations and experimental variants are identified in their descriptions.
Check one algorithm to run it, or several to compare their results.
Select any pair or larger set to compare. The shared plot tracks each method's best Assembly Index in its own colour; individual bars show time budget used, not an estimate of search completion. The time limit below applies to each algorithm. A comparison occupies one queue slot. Pathways and timings stay separate; work counts use each method's own unit.
GPU methods share one device and run one at a time, including in parallel comparisons. Each search clock starts when the device is assigned; CPU methods can run alongside the current GPU method.
How the selected algorithms report results
Each result applies to its input assembly space. An interrupted run returns a checked upper-bound pathway when one is available. Each method's plot tracks that bound over elapsed time; its progress bar shows time budget used. Work counts use the method's own unit, and the rate is its count divided by elapsed time. A minimum is labelled proved only after the run satisfies its proof conditions and the service checks its pathway.
Directed input string
The time limit covers worker startup, model construction, calculation and certificate validation. The service has a 64 GiB aggregate memory limit and a 32-core CPU quota.
Constructed assembly pathway
Target:
Molecule pathway
Molecule catalogue
Select a molecule card, then use Build Pathway below the selected preview. Search by name or filter by size, class or origin.
Downloaded structures are kept in the shared local library and reused. Searches send your query to the selected provider through QUOX. Size refers to the prepared graph. Origin tags can overlap and require source evidence; unclassified is not evidence of absence. Online filters examine each fetched page of name matches. Local filters search the whole saved library.
Choose a sample card or supply your own single connected V2000 `.mol` file (maximum 64 KiB). A double or triple bond counts as one graph edge. When you build a pathway, the selected structure is sent over HTTPS to QUOX. Uploaded files and full pathways expire about 10 minutes after completion. Calculation summaries and graph hashes are saved in shared history; matching molecule cards show the best previously checked index and its provenance. A proved minimum is labelled “proved”; a checked construction from an unfinished search is an “upper bound”. Library, classification and calculation-history details.
Built-in examples (available offline)
User-defined assembly space
Describe your objects, legal joins and target in JSON. The same solver searches for a smallest reusable pathway in this supplied space. Strings and molecules use adapters to generate this representation; here you define it directly.
Each distinct object has a unique id, an optional display label and optional data metadata. Joins specify left, right and output IDs. Objects with no producing joins form the elementary basis. Include all intermediate objects and allowed joins you want searched, forming an acyclic dependency graph. Repeated IDs represent reusable object types; the Assembly Index counts distinct constructed nonbasis types.
Public API limits: 128 objects, 1,024 joins and a 96 KiB request. The time control above sets the search duration. Submission sends this space to QUOX; inputs and results are held temporarily, for about 10 minutes after completion. Object IDs define identity; labels and metadata are preserved for display. A proved result applies to the joins you supplied.
Constructed assembly pathway
Target:
Elementary basis used: