Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Templates Piotr Masierak Abstract Assembly Theory, as developed by Cronin and co-workers, assigns to an object an assembly index: the minimal number of binary join operations required to build at least one copy of the object from a specified set of basic building blocks, allowing reuse of intermediate components. For strings over a finite alphabet, the canonical assembly index can be defined in the free semigroup ( Σ + , ⋅ ) (\Sigma^{+},\cdot) with universal binary concatenation and a “no-trash” condition, and its exact computation has been shown to be NP-complete. In this paper we propose an extension of the canonical, string-based formulation which augments pure concatenation with templated assembly steps. Intermediate objects may contain a distinguished wildcard symbol ∗ \ast that represents a compressible block. Templates are restricted to block-compressed substrings of the target string and can be instantiated by inserting previously assembled motifs into one or many wildcard positions, possibly in parallel. This yields a new complexity measure, the templated assembly index, which strictly generalises the canonical index while preserving its operational character. We formalise the model, clarify its relation to the canonical assembly index and to classical problems such as the smallest grammar problem, and discuss the computational complexity of determining the templated assembly index. Finally, we sketch potential applications in sequence analysis, modularity detection, and biosignature design. Keywords: assembly theory, assembly index, information theory, complexity measures 1 Introduction Assembly Theory (AT) aims to quantify the historical contingency and structural complexity of objects by counting the minimal number of composition steps required to build them from simple components, under a specified set of admissible joins and with reuse of previously assembled substructures [ 2 , 1 , 4 ] . In its string-based form, one considers the free semigroup (\Sigma^{+},\cdot) over a finite alphabet \Sigma , with binary concatenation as the only join operation. The canonical assembly index of a string w\in\Sigma^{+} is then the minimal length of an assembly plan that produces at least one copy of w , using only substrings of w as intermediate objects and charging unit cost per join. This canonical, “no-trash” variant captures a universal lower bound for more operational, domain-specific versions of Assembly Theory. In [ 5 ] it was conjectured and in [ 3 ] it was shown that computing the assembly index of a given string—or even deciding whether the index is at most a given bound k —is NP-complete, via a reduction from the smallest grammar problem and a correspondence between assembly plans and straight-line programs. From a structural perspective, the canonical index is sensitive to hierarchical reuse of substrings, especially repeated motifs that can be assembled once and then copied in subsequent joins. However, many natural systems exhibit forms of templated or pattern-based assembly that are not fully captured by pure concatenation. For instance, a fixed molecular scaffold may contain multiple sites where the same functional group is attached, or a regulatory DNA sequence may contain recurrent binding motifs embedded in varying local contexts. From the perspective of string assembly, these phenomena resemble the use of templates: patterns with holes (wildcard positions) that are subsequently filled by previously assembled motifs, possibly at many positions in parallel. The central aim of this paper is to formalise this intuition in a way that remains faithful to the operational ethos of Assembly Theory. We introduce a new variant of the canonical string-based model in which intermediate objects may contain a special symbol \ast denoting a placeholder for an arbitrary non-empty string. Crucially, we restrict templates to those that arise as block-compressed substrings of the target string: roughly, a template is obtained by taking a substring u of the target w and replacing some contiguous blocks of u by \ast , thereby compressing entire blocks into a single wildcard. Assembly operations now include not only concatenation, but also template instantiation steps, where a previously available motif x is substituted for one or all occurrences of \ast in a template T , in a single step. This yields a new complexity measure, the templated assembly index \mathrm{TAI}(w) . By design, the canonical index \mathrm{ASI}(w) appears as the special case where wildcard templates are never used, and we show that \mathrm{TAI}(w)\leq\mathrm{ASI}(w) for all w . At the same time, \mathrm{TAI}(w) can be strictly smaller than \mathrm{ASI}(w) for strings that exhibit non-local, templated reuse of motifs, making \mathrm{TAI} sensitive to a different aspect of structure—which we term templated modularity. 2 Background: canonical string-based Assembly Theory We briefly recall the canonical string-based formulation of Assembly Theory and fix notation. Let \Sigma be a finite alphabet and let \Sigma^{+} denote the set of all non-empty strings over \Sigma . We consider the free semigroup (\Sigma^{+},\cdot) with concatenation as the binary operation. Definition 2.1 . Let w\in\Sigma^{+} . The canonical assembly space for w is the pair \mathcal{A}(w)=(O,R), where: • O\subseteq\Sigma^{+} is the set of objects, taken to be the set \mathrm{Sub}(w) of all non-empty substrings of w ; • R is the set of binary join rules of the form x\circ y\to xy for all x,y\in O such that xy\in O . Informally, O contains exactly the substrings of the target w , and we may join two substrings x,y in a single assembly step whenever their concatenation xy is again a substring of w . Intermediate objects are thus constrained by a no-trash condition: every object appearing in any assembly plan is a substring of the target w . Definition 2.2 . Let w\in\Sigma^{+} and \mathcal{A}(w)=(O,R) as above. An assembly plan for w is a sequence x_{1},x_{2},\dots,x_{m} of objects in O such that: (a) each x_{i} is either a single letter in \Sigma or is obtained from two earlier objects by a rule in R , i.e. there exist j,k0 and uses the magnitude of \mathrm{gain}(T,U) as a priority score (larger gain indicates a more promising template under the chosen proxy). Conversely, \mathrm{gain}(T,U)<0 suggests that the template is unlikely to be beneficial in this approximation, although one cannot exclude indirect benefits through later reuse effects in the full \mathrm{TAI} model. A sketch of a greedy heuristic. Starting from the explicit target word w , iterate: 1. Mine candidate skeletons T\in T(w) together with admissible fillers u for which x_{u}=T[P(T)\mapsto u]\in\mathrm{Sub}(w) , and compute \mathrm{occ}(x_{u}) in the current working representation. 2. For each T , choose a filler family U (e.g. all admissible fillers, or the best-scoring subset) and compute \mathrm{gain}(T,U) . 3. Select a skeleton T with a filler family U of maximum positive gain. 4. Commit to constructing T once (using R_{\mathrm{concat}} ), constructing each u\in U once, and generating each chosen occurrence of x_{u} via a single rule application in R_{\mathrm{temp}} (fully parallel substitution, S=P(T) ). 5. “Compress” the working representation of w by treating each generated occurrence of each x_{u} as an available object, and continue searching for further profitable candidates on the remaining structure. The resulting set of committed constructions and instantiations can be translated directly into a templated assembly plan in A^{\ast}(w) , and therefore yields an explicit computable upper bound on \mathrm{TAI}(w) . We leave a detailed experimental evaluation of such heuristics for future work. This viewpoint is consistent with Example 3.2: the skeleton T=\texttt{11*11*11} is instantiated in w with two different fillers, u=\texttt{22} and u=\texttt{00} , producing P=T[P(T)\mapsto\texttt{22}] and S=T[P(T)\mapsto\texttt{00}] . For the baseline choice c(y)=|y|-1 , we have |T|=8 and thus c(T)=7 , while |\texttt{22}|=|\texttt{00}|=2 and hence c(\texttt{22})=c(\texttt{00})=1 . Moreover, |P|=|S|=10 , so c(P)=c(S)=9 , and in this example \mathrm{occ}(P)=\mathrm{occ}(S)=1 . Taking U=\{\texttt{22},\texttt{00}\} , the aggregate score becomes \mathrm{gain}(T,U)=(1\cdot 9+1\cdot 9)-\bigl(7+(1+1)+(1+1)\bigr)=18-11=7, which is positive precisely because the one-time cost of constructing the skeleton T is amortised across two instantiations with different fillers. Accordingly, a gain-based greedy strategy would naturally commit to assembling the single skeleton T once and then instantiating it for each filler, capturing the step savings exhibited by the templated assembly plan in that example. paragraphGain calculations for the additional worked examples I and II. We reuse the baseline proxy c(y):=|y|-1 . Example I ( w_{1}=10113121101011212111211 ). Take the skeleton T=1\ast 11 and the filler family U=\{0,2\} , which produces x_{0}=T[\ast\mapsto 0]=1011,\qquad x_{2}=T[\ast\mapsto 2]=1211. Here |T|=4 , so c(T)=3 , and |0|=|2|=1 , hence c(0)=c(2)=0 . Moreover |x_{0}|=|x_{2}|=4 , so c(x_{0})=c(x_{2})=3 . In the block factorisation w_{1}=1011\;3\;1211\;0\;1011\;2\;1211\;1211 we have \mathrm{occ}(x_{0})=2 and \mathrm{occ}(x_{2})=3 . Therefore \displaystyle\mathrm{gain}(T,U) \displaystyle=\bigl(2\cdot c(x_{0})+3\cdot c(x_{2})\bigr)-\Bigl(c(T)+\bigl(c(0)+c(2)\bigr)+\bigl(\mathrm{occ}(x_{0})+\mathrm{occ}(x_{2})\bigr)\Bigr) \displaystyle=(2\cdot 3+3\cdot 3)-\bigl(3+(0+0)+(2+3)\bigr) \displaystyle=15-8=7. Example II ( w_{2}=101131211010112121112111011 ). With the same T=1\ast 11 and U=\{0,2\} , we still have c(T)=3 , c(0)=c(2)=0 , and c(1011)=c(1211)=3 . Using the factorisation w_{2}=1011\;3\;1211\;0\;1011\;2\;1211\;1211\;1011, we obtain \mathrm{occ}(1011)=3 and \mathrm{occ}(1211)=3 , hence \displaystyle\mathrm{gain}(T,U) \displaystyle=(3\cdot 3+3\cdot 3)-\bigl(3+(0+0)+(3+3)\bigr) \displaystyle=18-9=9. 5 Computational complexity We consider the decision problem associated with the templated assembly index \mathrm{TAI}(w) . Definition 5.1 . The decision problem TAI-DEC is defined as follows: • Instance: a string w\in\Sigma^{+} and a non-negative integer k (given in unary or binary). • Question: does there exist a templated assembly plan for w of total cost at most k in the templated assembly space \mathcal{A}_{\ast}(w) ? Lemma 5.2 . TAI-DEC belongs to \mathrm{NP} . Sketch. A certificate is a sequence of rule applications (concatenations and template instantiations), together with the intermediate objects they produce. Since every step strictly increases the length of at least one constructed object, the length of a valid plan is polynomially bounded in |w|+k . Verification proceeds by simulating each operation and checking that the produced object belongs to O_{\ast}=\mathrm{Sub}(w)\cup\mathcal{T}(w) . All checks can be carried out in time polynomial in |w|+k , hence TAI-DEC is in \mathrm{NP} . ∎ On hardness. The canonical decision problem \textsc{ASI-DEC}=\{\,(w,k)\mid\mathrm{ASI}(w)\leq k\,\} is NP-complete for fixed finite alphabets [ 3 ] . Since \mathrm{TAI}(w)\leq\mathrm{ASI}(w) for all w , the templated model is a genuine extension of the canonical one. However, this extension goes in the easier direction (it potentially shortens optimal plans), so NP-hardness of TAI-DEC does not follow immediately from NP-hardness of ASI-DEC . One can nevertheless view ASI-DEC as the restriction of TAI-DEC to assembly plans that never apply a rule in R_{\mathrm{temp}} . Equivalently, under the promise that w admits no beneficial template instantiation (so that \mathrm{TAI}(w)=\mathrm{ASI}(w) ), the problems TAI-DEC and ASI-DEC coincide. This observation does not, however, settle the unconditional worst-case complexity of TAI-DEC . Indeed, once beneficial template instantiations are allowed, deciding whether \mathrm{TAI}(w)\leq k requires simultaneously reasoning about the classical reuse-vs.-concatenation trade-off and about whether it is worthwhile to invest concatenation steps into constructing templates in order to amortize them through one or more instantiation steps. For this reason, we strongly conjecture that TAI-DEC remains NP-hard (already over fixed alphabets): the templated model preserves the combinatorial “hard core” of canonical assembly planning, while adding an additional layer of discrete structure selection (identifying and exploiting profitable templates). While this is not a proof, it provides compelling evidence that intractability should persist in the worst case. Establishing unconditional NP-hardness (or polynomial-time solvability) of TAI-DEC for fixed alphabets remains an interesting open question. 6 Discussion We have proposed an extension of the canonical string-based formulation of Assembly Theory in which intermediate objects may contain a wildcard symbol \ast representing compressed blocks, and templates are restricted to block-compressed substrings of the target string. This leads to the templated assembly index \mathrm{TAI}(w) , a new complexity measure that generalises the canonical assembly index \mathrm{ASI}(w) and is sensitive to templated modularity: the presence of modules that recur in multiple, possibly distant contexts linked by a common scaffold. Formally, we defined templated assembly spaces, specified concatenation and template instantiation rules, and established basic relationships between \mathrm{TAI}(w) and \mathrm{ASI}(w) . We established membership in NP and clarified why NP-hardness does not follow from a trivial embedding argument. We conjecture that TAI-DEC is NP-hard (already for fixed alphabets), while leaving unconditional NP-hardness open. We also outlined connections to grammar-based compression and to formalisms such as pattern languages. Some domains where \mathrm{TAI} and its future variants may offer novel insights are: • Chemistry and molecular design: Many molecules can be described as relatively rigid scaffolds decorated by repeated functional groups: aromatic cores bearing several identical substituents, oligomers with the same side chain attached at multiple positions, or dendritic architectures built from a small set of branching units. In a string-based representation of molecules (for example a linearised encoding of a core with substituents), such patterns correspond to templates where wildcard positions mark sites of functionalisation. Canonical assembly indices quantify reuse of repeated fragments, but they do not distinguish between independent repetitions and repetitions coordinated by a shared backbone. In contrast, templated assembly makes this distinction explicit: a common scaffold with wildcard sites is built once, and then instantiated with chosen functional groups. Molecules or families of molecules with a large gap \mathrm{ASI}(w)-\mathrm{TAI}(w) would then correspond to structures where much of the apparent combinatorial complexity comes from templated substitution patterns rather than from genuinely unrelated submotifs, suggesting applications in quantifying scaffold–decoration modularity in medicinal chemistry, combinatorial library design, and polymer or supramolecular engineering. • Sequence analysis and genomics: Many genomic regions exhibit modular architectures, with recurring motifs (e.g. transcription factor binding sites, protein domains) embedded in diverse local contexts. Canonical assembly indices already provide a measure of hierarchical reuse, but templated indices could more directly reflect shared scaffolds with multiple occurrences of the same motif. Differential behaviour of \mathrm{ASI}(w) and \mathrm{TAI}(w) across genomic regions might highlight functionally relevant templated structures. • Biosignatures and origins of life: Assembly Theory has been proposed as a framework for defining universal biosignatures based on complexity measures derived from putative assembly paces [ 2 , 1 , 4 ] . The templated assembly index offers a complementary axis: high \mathrm{TAI}(w) together with a large gap \mathrm{ASI}(w)-\mathrm{TAI}(w) might signal systems that exploit templated copying of modules in ways characteristic of evolved biological organisation, for example gene families under common regulatory architectures. Future work may include a more detailed classification of the gap \mathrm{ASI}(w)-\mathrm{TAI}(w) for various families of strings, refined complexity and approximation results, and empirical studies of \mathrm{TAI} on biological and artificial datasets. On the conceptual side, templated Assembly Theory suggests a broader programme: to systematically explore how different classes of templates and rewriting operations give rise to distinct families of assembly indices, each probing a different facet of structure and history in complex systems.