Embargoed until April 28, 6PM UT

Figure S1. Architecture of the molecular finite automaton, featuring its input, software and hardware components. The current state of the computation is represented by a partially cleaved symbol-encoding dsDNA segment that exposes a four-nucleotide "sticky end" at a state-specific location. The cleavage is accomplished by the FokI hardware enzyme that recognizes the double-stranded DNA sequence GGATG and cleaves its substrate 9 and 13 nucleotides away from the recognition site in 5'_3' and 3'_5' strands, respectively. The transition molecule recognizes a particular state-symbol sticky end and directs the FokI bound to it to cleave within the next symbol at a precise location to expose the next state-symbol combination, thus realizing transition between states. The software molecule is recycled and the cleaved symbol is scattered. We note our unusual use of automaton components: its formal input, the diagnostic rule to be processed, functions in our application like a program, and its formal program, the software molecules, function in our application as the input mechanism, detecting the presence of molecular indicators.

Figure S2. Molecular components of the computer. a, Diagnostic molecules for prostate cancer. The diagnosis moiety (gray) implements the diagnosis component of a diagnosis and therapy rule and it consists of 7-bp sequences encoding the symbols for the molecular indicators. Following it are either a drug release moiety (purple) or a drug-suppressor release moiety (brown), consisting of a ssDNA that loops on itself to form a sequence encoding three diagnostic verification symbols (light purple/light brown) followed by a drug loop (purple) or a drug-suppressor loop (brown). For all symbol-representing sequences, the first four nucleotides of the sequence represent the symbol combined with state Yes, while nucleotides three to six represents the symbol combined with the state No. Example symbol encodings and state-symbol sticky ends are enlarged in red frames. b, c, Pair of competing transition molecules regulated by PIM1 mRNA, each containing a regulation (green, red) and a computation (blue, gray) fragment. The computation fragment consists of the double-stranded recognition site of the hardware enzyme FokI (blue), a single-stranded sticky end (gray) that recognizes a particular state-symbol combination of the diagnostic molecule, and possibly a 2-bp spacer (gray) between the two. A spacer of 2 bp effects a YesYes transition while a zero-length spacer
effects a YesNo transition. The regulation fragment of a transition molecule enables its regulation by a nucleic-acid-based molecular indicator, which may activate (green) or deactivate (red) the transition when in high concentration. The transition molecule YesNo (c) is inactivated by a subsequence of the PIM1 mRNA indicator ("inactivation tag") via its binding to the single-stranded overhang of the regulation fragment of the transition molecule followed by strand exchange due to higher stability of the mRNA-deactivation-tag/transition-sense-strand hybrid relative to the normal transition molecule hybrid. The transition molecule YesYes (b) is activated by high concentration of PIM1 mRNA. In its absence, formation of the transition molecule is prevented by a third "protecting" oligonucleotide (green) that partially hybridizes to the antisense strand and forms a complex that is more stable than the active transition molecule. The protecting strand is also complementary to a subsequence of PIM1 mRNA ("activation tag", light green). Activation tag of PIM1 mRNA triggers a strand exchange process that decouples the protecting strand from the antisense strand of the transition molecule and allows it to hybridize with the sense strand to form an active Yes Yes transition. In an idealized regulation process one PIM1 mRNA molecule inactivates one YesNo and activates one Yes Yes transition molecule. d, Pair of transition molecules regulated by mRNA point mutation. The positive transition has a regulation fragment complementary to the wild-type mRNA while the corresponding regulation fragment of the negative transition is complementary to the mutated mRNA. The positive transition is preferentially inactivated by the wild-type mRNA whereas the negative transition is inactivated by the mutated mRNA.

Figure S3. a, Calibration curve showing regulation of probability of Yes output state in a single-step computation by a pTRI-Xef generic mRNA indicator. Experimental data used to calculate the probabilities is shown in the insert. b, Regulation by point mutation by mixtures of model ssDNA oligonucleotides representing different ratios of mRNA of wild-type and of mutated genes. c-e, Adjusting confidence in a positive diagnosis for various concentrations of the molecular indicator by adjusting the absolute concentrations of the transition molecules. The gel (c) visualizes the increase in probability of Yes diagnostic output with increasing concentrations of INSM1 ssDNA model (over-expressed in the disease) for different concentrations of active and inactive transition molecules. (d) Display of the transition probabilities derived from the measured intensities of the Yes and No bands, highlighting the change in the No/Yes crossover point as a function of transition molecule concentration. (e) Plots this function.

Figure S4. Selectivity of the diagnostic automata for their disease models. Each pair of lanes is a particular combination of molecular indicators indicated in the figure and is diagnosed separately by the automata for SCLC (left lane) and PC (right lane). + indicates presence of disease indicators, - indicates a normal condition, and * indicates absence of disease-related molecules. Expected outcome of the diagnosis is indicated above each lane.

Figure S5. Release of the approved antisense drug. The two left-most lanes show, separately, a labelled diagnostic molecule and a labelled drug molecule. The third lane contains a non-labelled diagnostic molecule together with a labelled drug suppressor, incubated in NEB4 buffer. The fourth lane shows the release of an active Vitravene® drug upon positive diagnosis as visualized by the labelled drug suppressor probe. The right-most lane demonstrates that the active drug is not released upon negative diagnosis.