Cell fate determination is governed by complex signaling molecules at appropriate concentrations that regulate the cell decision-making process. In vertebrates, however, concentration and kinetic parameters are practically unknown, and therefore the mechanism by which these molecules interact is obscure. In myogenesis, for example, multipotent cells differentiate into skeletal muscle as a result of appropriate interplay between several signaling molecules, which is not sufficiently characterized. Here we demonstrate that treatment of biochemical events with SAT (satisfiability) formalism, which has been primarily applied for solving decision-making problems, can provide a simple conceptual tool for describing the relationship between causes and effects in biological phenomena. Specifically, we applied theŁukasiewicz logic to a diffusible protein system that leads to myogenesis. The creation of an automaton that describes the myogenesis SAT problem has led to a comprehensive overview of this non-trivial phenomenon and also to a hypothesis that was subsequently verified experimentally. This example demonstrates the power of applying Łukasiewicz logic in describing and predicting any decision-making problem in general, and developmental processes in particular.

Early in embryonic development, multipotent cells of the germ layers become committed to their cell fates and form lineages of progenitor cells that later differentiate into cell types. The decision-making mechanisms that control cell lineage determination are not fully understood, but recent biomolecular studies have shed light on these regulatory systems. In vertebrates, the paraxial mesoderm, which flanks the neural tube and notochord, develops into unsegmented presomitic mesoderm (PSM). The PSM develops into somites, which are segmentally arranged epithelial structures(Christ and Ordahl, 1995). The somitic cells can differentiate into numerous fates, including myotome,sclerotome, syndetome and dermatome, or undergo apoptosis.

Switch-graft manipulations and rotation experiments involving early epithelial somites lead to normal somitic development, supporting the notion that somitic cells are multi-potent and that their fates are determined by their position (Aoyama, 1993; Aoyama and Asamoto, 1988; Christ et al., 1992; Ordahl and Le Douarin, 1992). These observations imply that external signals control cell differentiation within somites. Four diffusible groups of proteins have been found to be the major determinants of myogenesis: the Wnt family of glycoproteins, sonic hedgehog (Shh), bone morphogenetic protein 4 (Bmp4) and antagonists of Bmp4,such as noggin (Fig. 1)(Hirsinger et al., 1997; Marcelle et al., 1997; Maroto et al., 1997; Munsterberg et al., 1995; Munsterberg and Lassar, 1995; Pourquie et al., 1996; Reshef et al., 1998). The current model suggests that a combinatorial effect between the Wnt proteins and Shh is required for myogenesis (Borello et al., 2006; Cairns et al.,2008; Munsterberg et al.,1995; Munsterberg and Lassar,1995; Stern et al.,1995), whereas other studies present data showing that the Wnt proteins and Shh antagonize each other(Lee et al., 2000; Lee et al., 2001). Conversely,it was demonstrated that a combinatorial effect between the Wnt proteins and noggin is also sufficient for myogenesis(Reshef et al., 1998), and that noggin addition lateral to the somites can promote myogenesis even when MyoD-expressing cells are removed from the somite(Gerhart et al., 2006). Studies in the field agree that Bmp4 inhibits myogenesis(Hirsinger et al., 1997; Marcelle et al., 1997; Pourquie et al., 1996; Reshef et al., 1998; Sela-Donenfeld and Kalcheim,2002; Watanabe and Le Douarin,1996). Our current study reconciles these seemingly contradicting statements.

The MyoD family of transcription factors - MyoD, Myf5, myogenin and Mrf4 -are the primary regulators of myogenesis and have been shown to determine myogenesis in many cell types (Davis et al., 1987; Emerson,1990; Gerhart et al.,2007; Olson, 1990; Weintraub et al., 1991). Activation of these genes occurs immediately after somite formation, well before myotomal muscle differentiation (de la Brousse and Emerson, 1990; Emerson, 1993; Ott et al., 1991; Pownall and Emerson, 1992; Sassoon et al., 1989; Tajbakhsh et al., 1997). Therefore, myogenesis is conveniently described as initiating the expression of these early myotomal markers.

The Boolean formalism (also known as binary logic or two-valued logic,using 0 and 1) has been applied for describing genetic and protein-protein networks and allows one to understand the qualitative features of complex signaling pathways (Albert and Othmer,2003; Huang, 1999; Tomlin and Axelrod, 2007). Although this formalism was suggested for describing simple protein-protein interactions, Łukasiewicz logic(Boicescu et al., 1991), a more complex formalism that uses a ternary (three-valued) numerical system (TNS),has never been applied to biological decision-making problems, such as lineage differentiation.

A satisfiability (SAT) problem refers to the conditions that would satisfy a search algorithm. The solution to the SAT problem would be the set of values that can be assigned to the variables in order to make a given expression true. The solution to the SAT problem does not necessarily find all of the solutions to the problem, nor does it pretend to find the most efficient or elegant solution to the problem. A solution will be achieved if it succeeds in satisfying the formula, that is, will make the expression within the formula true. A SAT problem is expressed in the form of a formula using the operations AND (), OR(), NOT(), as well as variables and parentheses (the laws of their usage and implementation appear later in the text, in the section Mathematical meaning and prediction ability').

Fig. 1.

The somitic morphogenetic field. Left, protein gradients. Blue, Wnt proteins; yellow, Shh; cyan, noggin; red, Bmp4; green, location of muscle pioneer cells. Right, somitic domains with protein concentrations depicted as colored TNS. The domain containing the values 1111 presents the normal physiological concentrations of the four morphogens that lead muscle pioneer cells to differentiate and express MyoD. Other domains contain various combinations of values that fail to express myogenic markers at the particular developmental stage. w, Wnt source; s, Shh source; g, noggin source; b, Bmp4 source.

Fig. 1.

The somitic morphogenetic field. Left, protein gradients. Blue, Wnt proteins; yellow, Shh; cyan, noggin; red, Bmp4; green, location of muscle pioneer cells. Right, somitic domains with protein concentrations depicted as colored TNS. The domain containing the values 1111 presents the normal physiological concentrations of the four morphogens that lead muscle pioneer cells to differentiate and express MyoD. Other domains contain various combinations of values that fail to express myogenic markers at the particular developmental stage. w, Wnt source; s, Shh source; g, noggin source; b, Bmp4 source.

The two commonly used forms of the SAT formula are the conjunctive normal form (CNF) and the disjunctive normal form (DNF)(Gopalakrishnan, 2006). The CNF and DNF are forms of presentation in logic. In the CNF, the operator separates the variables, and the operator separates the clauses. In the DNF, the operator separates the variables, and the operator separates the clause:

The CNF formula and the DNF formula are interconvertible, although conversion incurs an exponential cost(Gopalakrishnan, 2006). If the problem is presented in DNF, it is satisfiable when at least one of the clauses is true. We propose that DNF is more suitable for describing biological phenomena than CNF because each set of experimental conditions that leads to a defined outcome can be represented by one clause. Different experiments that lead to the same outcome are represented by several clauses separated by the operator.

We choose to use SAT formalism because it could potentially deal with large data sets and underpins the logic that defines the solutions. In SAT, one could collect a series of solutions (clauses in the DNF formalism) that has no apparent logic linking them (by using the operator). In this study,we use a blind' collection of all the solutions leading to myogenesis and link them as unconnected solutions. The SAT problem serves to describe the logic of the interplay of the above-mentioned morphogens. Any combination of morphogens (one clause in the case of the DNF formalism) that leads to myogenesis is a SAT solution, which, when it stands as a single solution, is not very interesting. However, by formulating the solutions into SAT formalism, logic for all the solutions could be revealed, thereby unraveling biochemical processes.

In this study, we demonstrate the power of using a TNS in SAT formalism for the description of myogenesis as an example of an uncharacterized decision-making problem during embryonic development. Construction of a finite automaton (see Results) that best describes the true clauses can lead to a better understanding of biochemical pathways. Here, the SAT formula and the finite automaton lead to the inevitable conclusion that myogenesis requires only Wnt signaling for its progression. This concept leads to a more comprehensive understanding of somitic myogenesis by predicting and discovering the existence of a hidden biochemical signaling pathway. We suggest that applying this logic to other biological pathways could serve as a powerful conceptual tool in the understanding of complex biological phenomena.

### Manipulations in chick embryos

Fertile White Leghorn chicken eggs were incubated at 38°C in a humidified incubator until embryos had reached stages HH10-HH12(Hamburger and Hamilton,1992). For in vivo implantation experiments, chick embryos were incubated using a modified form of new cultures(James and Schultheiss, 2005). The required manipulations were performed under a binocular Leica MZ12.5 stereomicroscope. In all the manipulations (cells and barriers), the required implant was inserted into a slit that was made between the middle PSM and the midline axial organs or the lateral plate mesoderm of the embryos. The manipulations were performed on one side of the embryo and the contra-lateral side was left as the control. The operated embryos were allowed to grow at 38°C for 20-24 hours. In notochord ablation experiments, the notochord was removed from the posterior part of the PSM of HH10-HH12 embryos. After the incubation, embryos were fixed in 4% paraformaldehyde for 24-48 hours at 4°C. Tissue culture experiments were performed as previously described(Munsterberg et al.,1995).

### Culture conditions for Wnt1- and noggin-secreting cells

RatB1A-LNCX parental cells or RatB1A-LNC Wnt1HA cells were kindly provided by A. B. Lassar (Harvard Medical School). The cells were selected in Geneticin(G418) and grown in Dulbecco's Modified Eagle's Medium (DMEM) containing high glucose, 2.5% fetal calf serum (FCS), 7.5% calf serum and 1% l-glutamine.

B3 CHO cells that produce noggin were selected in methotrexate and grown under conditions of minimum essential medium (MEM)-alpha without nucleosides,containing 10% dialyzed FCS and 1% Pen-Strep. Control dihydrofolate reductase(dhfr) cells were grown under conditions of MEM-alpha with nucleosides,containing 10% dialyzed FCS and 1% Pen-Strep.

### Cell implantation

Noggin- and Wnt1-secreting cells or RatB1A-LNCX parental cells were removed from culture, centrifuged, transferred to an Eppendorf tube, spun down and incubated for 3-5 hours to obtain cell aggregates of 20-40 μm in diameter that were used for transplantation.

### Barrier implantation

Cellophane paper was cut into small pieces and transferred onto the embryo. In experiments for which a cellophane barrier and secreting cells were used together, the implanted cells were inserted between the barrier and the PSM on the experimental side, and between the midline tissues and the PSM on the control contra-lateral side.

### Wholemount RNA in situ hybridization

The procedure was performed essentially as previously described(Reshef et al., 1998) with the indicated modifications. Embryos were treated with 10 μg/ml of proteinase K(Sigma) for 10 minutes. The probe concentration in the hybridization mix was∼0.2 μg/ml. The alkaline phosphatase reaction was developed for 30 minutes (Pax1) to 6 hours (Bmp4). MyoD was developed for 2-3 days with repeated washes with NTMT buffer.

### Sectioning and photography

Embryos were placed in a scintillation vial containing 5% sucrose in phosphate-buffered saline (PBS) and left for 1 hour at 4°C. The solution was discarded gently, and a solution of 20% sucrose in PBS was added. Vials were placed again at 4°C overnight and then placed in a 38°C water bath until temperature equilibration. A solution of 15% sucrose and 7.5%gelatin in PBS was heated to 65°C until the gelatin had melted. Then the solution was cooled gradually to 38°C. After temperature equilibration,the scintillation vials containing the embryos were removed from the water bath. The solution was discarded, replaced by the sucrose-gelatin solution and left in a 38°C water bath for 5 hours. The embryos were gently moved along with the gelatin-sucrose solution to a chilled rubber container. A 50 ml flask was filled with 2-methylbutane and left to chill on dry ice for 30 minutes. Trimmed blocks were immersed in chilled methylbutane for 15-20 seconds and were taken for cryosectioning. Using the Leica 3050 cryocut (-26°C), 16-20μm sections were collected on polylysine-treated glass slides, and cover slides were added using Glycergel Hydromount. (Dako). Photographs were taken using the differential interference contrast (DIC) system of a Leica DMIRE2 inverted microscope.

### RT-PCR analysis

Reverse transcription (RT)-PCR analysis was performed according to a well-established procedure (Maroto et al.,1997; Munsterberg et al.,1995). Pax3 was amplified in the presence of 5% formamide with an annealing temperature of 50°C. We used 24 cycles to assay Gapdh and 30-32 cycles to assay other genes.

We decided to present myogenesis using SAT formalism with the given concentration set of Wnt proteins, Shh, noggin and Bmp4 as the input (denoted by the variables w, s, g and b, respectively) and myogenesis as the output. Based on classical Łukasiewicz logic, the three input values refer to either less than the normal physiological concentration (0),the normal physiological concentration (1) or above the normal physiological concentration (2). This formalism seems to be appropriate for describing experimental biological systems in which genes and proteins are either downregulated (0), overexpressed (2) or unchanged (1). Usually in logic, the true value is defined as 1 and the false value as 0. In our system, the normal physiological concentration of a morphogen is sufficient for signaling and,therefore, defined as 1. Above the normal physiological concentration means that the concentration of the morphogen is greater than the already true value; therefore, we chose to assign the value 2 to this conformation. It is important to emphasize that we aim for the concentration itself and not for its biological effect.

We focused on myogenesis either in the anterior part of the PSM tissue or in stage I-III somites in avian embryos at HH10-HH12. These tissues have been extensively studied and can be easily manipulated. Avian embryos at stages HH10-HH12 express MyoD in the somites along the anterior-posterior axis but not in the PSM. The expression of MyoD is initially localized to the muscle pioneer cells, which are somitic cells adjacent to the neural tube(Fig. 1)(Kahane et al., 1998; Pownall et al., 1996). When surgically removed, isolated from surrounding tissues and cultured for 3 days,PSM and stage I-III somites fail to express myotomal markers(Munsterberg and Lassar, 1995; Reshef et al., 1998) in contrast to older somites (stage IV and above), in which somitic domains are already defined and cell fate is already specified. Thus, the PSM and stage I-III somites represent predetermined tissues that require an additional environmental input. Much of the experimental information required to obtain a complete picture of all possible scenarios defined by the TNS formalism is available in the literature. Therefore, we carried out only the missing experiments in vivo, in vitro or both.

We define the true output as either the beginning of myogenesis in cell culture in vitro or the unusual expansion of myogenic markers (in comparison with normal developmental patterns) within the somite in vivo. It is important to note that, unlike the in vitro experimental systems, in the in vivo setup,the directionality of the protein gradient has a significant effect on the size and location of myogenic gene expression in the somite. Therefore,various locations within the same somitic morphogenetic field exhibit different outputs in response to local concentrations of the input proteins. As a preliminary step, we decided to focus on pre-somitic cells in a given signaling environment (we will discuss the importance of cell location later in the text). Considering the above-defined three-values-four-variables(proteins w, s, g and b, which can take the values 0, 1 or 2), this treatment yields a matrix of 34=81 scenarios (see Table S1 in the supplementary material) that might or might not result in myogenesis.

### noggin is a unique morphogen

Whereas all other proteins are factors emanating from surrounding tissues,noggin is also significantly expressed in somitic cells(Hirsinger et al., 1997; Reshef et al., 1998; Gerhart et al., 2006). noggin levels can be ectopically elevated in two ways - either independently, by supplying it directly to somitic cells in culture or in vivo as a soluble protein (using noggin-secreting cells or noggin-soaked beads), or dependently,by linking it to high levels of Shh(Hirsinger et al., 1997) or high levels of Wnt proteins (Reshef et al., 1998) and by transplanting MyoD-positive epiblast cells(Gerhart et al., 2006). Conversely, noggin levels cannot be reduced without intrusively interfering with the somitic cell genome (such as noggin knockdown), an intervention that can dramatically change the cell response and influence the expression of early myogenic factors, thus elevating the degrees of freedom of the mathematical formulation. Therefore, as a preliminary treatment to that described in Table S1 in the supplementary material, we decided to ignore noggin level 0 (less than the normal physiological concentration), taking into consideration that this table is not complete, and thus creating Table 1.

Table 1.

TNS description of 54 input scenarios with their corresponding outputs

ScenarioWnt proteinsShhNogginBmp4MyogenesisOrigin of dataRemarks
Ref. 1,2,3 Myogenesis needs w and s. g is insufficient to induce it
Ref. 5 b inhibits myogenesis (Ref. 3,6,7)
b inhibits myogenesis (Ref. 3,6,7)
Fig. S1B, Ref. 3 g is insufficient for myogenesis
g titrates b, g is insufficient for myogenesis
g and b are stochiometric. g is insufficient for myogenesis (Fig. S1C, Ref. 3)
13  If w=0, then g=0 (Ref. 3,9)
14 Ref.11 If w=0, then g=0 (Ref. 3,9)
15  If w=0, then g=0 (Ref. 3,9)
16 This work (data not shown) Myogenesis requires w (Ref. 2,10). g could not induce myogenesis (Ref. 3)
17 This work (data not shown) Myogenesis requires w (Ref. 2,10). Myogenesis is antagonized by b
18 This work (data not shown) Myogenesis requires w (Ref. 2,10). Myogenesis is antagonized by b
22 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
23 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
24 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
25 This work (data not shown) Myogenesis requires w (Ref. 2,9). g could not induce myogenesis (Ref. 3)
26 This work (data not shown) Myogenesis requires w (Ref. 2,9)
27 This work (data not shown) Myogenesis requires w (Ref. 2,9)
31  See this study
32  See this study
33  b inhibits myogenesis
34 Ref. 3
35  g is in excess to b
36
40 Ref. 1,5,15
41  Normal conditions by definition
42 Ref. 3,6
43  If scenario 44 is true, then the removal of b will promote myogenesis
44 Ref. 3
45
49  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 52
50  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 53
51  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 54
52 Ref. 2,5,9,10,14,16
53  g titrates b. Collapses into scenario 52
54
58  See this study
59  See this study
60  b inhibits myogenesis
61 Fig. S1B
62  g titrates b. Collapses into scenario 61
63
67  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 70
68  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 71
69  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 72
70  If scenario 71 is true, then the removal of b will promote myogenesis
71 Fig. S2 g titrates b
72
76  If w=2 and s=2, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 79
77  If w=2 and s=2, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 80
78  If w=2 and s=2, then g=2 (Ref 3,9; Fig. S2). Collapses into scenario 81
79 Ref. 2,3,13
80  g titrates b. Collapses into scenario 79
81
ScenarioWnt proteinsShhNogginBmp4MyogenesisOrigin of dataRemarks
Ref. 1,2,3 Myogenesis needs w and s. g is insufficient to induce it
Ref. 5 b inhibits myogenesis (Ref. 3,6,7)
b inhibits myogenesis (Ref. 3,6,7)
Fig. S1B, Ref. 3 g is insufficient for myogenesis
g titrates b, g is insufficient for myogenesis
g and b are stochiometric. g is insufficient for myogenesis (Fig. S1C, Ref. 3)
13  If w=0, then g=0 (Ref. 3,9)
14 Ref.11 If w=0, then g=0 (Ref. 3,9)
15  If w=0, then g=0 (Ref. 3,9)
16 This work (data not shown) Myogenesis requires w (Ref. 2,10). g could not induce myogenesis (Ref. 3)
17 This work (data not shown) Myogenesis requires w (Ref. 2,10). Myogenesis is antagonized by b
18 This work (data not shown) Myogenesis requires w (Ref. 2,10). Myogenesis is antagonized by b
22 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
23 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
24 This work (data not shown) If w=0, then g=0 (Ref. 3,9). Insights in the Shh-noggin correlation hypothesis section
25 This work (data not shown) Myogenesis requires w (Ref. 2,9). g could not induce myogenesis (Ref. 3)
26 This work (data not shown) Myogenesis requires w (Ref. 2,9)
27 This work (data not shown) Myogenesis requires w (Ref. 2,9)
31  See this study
32  See this study
33  b inhibits myogenesis
34 Ref. 3
35  g is in excess to b
36
40 Ref. 1,5,15
41  Normal conditions by definition
42 Ref. 3,6
43  If scenario 44 is true, then the removal of b will promote myogenesis
44 Ref. 3
45
49  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 52
50  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 53
51  If w=1 and s=2, then g=2 (Ref. 9). Collapses into scenario 54
52 Ref. 2,5,9,10,14,16
53  g titrates b. Collapses into scenario 52
54
58  See this study
59  See this study
60  b inhibits myogenesis
61 Fig. S1B
62  g titrates b. Collapses into scenario 61
63
67  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 70
68  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 71
69  If w=2 and s=1, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 72
70  If scenario 71 is true, then the removal of b will promote myogenesis
71 Fig. S2 g titrates b
72
76  If w=2 and s=2, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 79
77  If w=2 and s=2, then g=2 (Ref. 3,9; Fig. S2). Collapses into scenario 80
78  If w=2 and s=2, then g=2 (Ref 3,9; Fig. S2). Collapses into scenario 81
79 Ref. 2,3,13
80  g titrates b. Collapses into scenario 79
81

T, true, myogenesis; F, false, no myogenesis; S, stoichiometric high concentrations of both noggin and Bmp4; ?, see text and Table S1. Missing scenarios were added into Table S1, completing all 81 possible scenarios.

References: 1 (Munsterberg and Lassar,1995); 2 (Munsterberg et al.,1995); 3 (Reshef et al.,1998); 4 (Galli et al.,2004); 5 (Pownall et al.,1996); 6 (Pourquie et al.,1996); 7 (Tonegawa and Takahashi, 1998); 8 (Linker et al., 2003); 9 (Hirsinger et al., 1997); 10 (Dietrich et al., 1997); 11 (Schmidt et al., 2004); 12 (Aoyama and Asamoto, 1988); 13 (Maroto et al., 1997); 14 (Borycki et al.,1998); 15 (Pourquie et al.,1995); 16 (Johnson et al.,1994).

As shown in Fig. 2A, 20 out of the 54 scenarios presented in Table 1, expressed in the form of the DNF clauses, result in myogenesis and thus satisfy the myogenesis function F. The following consistencies were noted:

1. In all cases satisfying myogenesis, w equals 1 or 2.

2. In all cases satisfying myogenesis, s equals 1 or 2. In cases where s equals 0, g equals 2.

3. In all cases satisfying myogenesis, b equals 0 or 1, but never 2.

Based on the three observation points described above, all of the 20 scenarios satisfying myogenesis were abridged to a general formulation(Fig. 2B). Thus, two clauses were sufficient to describe myogenesis, defining the interplay between all four morphogens in this developmental process. As myogenesis is antagonized by Bmp4, the effect of Bmp4 on myogenesis is inverse to its concentration. Therefore, we used a b negation value in the SAT formalism. The use of the negation value allows for the assignment of an anti-Bmp4' component. If Bmp4 levels are high (2), then the negation of Bmp4 is low (0). By contrast, the myogenesis agonists (Wnt proteins, Shh and noggin) are assigned their original values, as their concentration is in proportion to their biological effect in promoting myogenesis. The universal truth tables(Fig. 2C) serve to define F (Fig. 2B) and function as tools for applying different values in the function F. A truth table is a symmetric scheme that defines the laws of the mathematical operator [conjunction-AND(), disjunction-OR() and negation-NOT()]. It is used for computation of the functional values of logical expressions. In particular,truth tables can be used to tell whether a propositional expression is true for all legitimate input values. In the case of conjunction and disjunction,two variables are being processed. In these operators, the value of one variable is assigned to the upper row, whereas the value of the other is assigned to the left column. The order of assignment is not important as the tables are symmetric. One can assign only two inputs at a time. One input could be a variable, a value of a previous operation or the value of a clause. An operation within parentheses will precede an operation between two clauses. In the case of the negation operator, only one variable is being processed. Therefore, the value of a variable is assigned in the top row, and the result appears in the lower row (in our case x=2-x). Any value assigned to the different variables (any scenario in Table 1 and Table S1 in the supplementary material), could be processed by the SAT problem in Fig. 2B, and only the combinations that satisfy F (T in Table 1) will lead to myogenesis. Thus, this function, while processing the different values of the inputs w, s, g and b, is predicting whether myogenesis will occur. Any one of the 20 clauses presented in Fig. 2A is sufficient and solves the myogenic SAT problem. Solving the SAT problem itself is not interesting. Such solutions have existed in the literature for over ten years. However, the SAT problem structure is interesting. The combination of variable values within the clauses themselves, rather than their solution, reveals its logic and allows us to unravel a new biochemical pathway.

Fig. 2.

Myogenesis as a SAT problem presented in DNF using TNS. (A) A summary of all possible conditions from Table 1 that lead to myogenesis in SAT formalism. w, Wnt level; s, Shh level; g,noggin level; b, Bmp4 level; 0, less than the normal physiological concentration; 1, the normal physiological concentration; 2, above the normal physiological concentration. (B) Myogenesis SAT problem. As myogenesis is antagonized by Bmp4, the effect of Bmp4 on myogenesis is inverse to its concentration. Therefore, we used its negation value and assigned it to the SAT formula. Note that, in this formulation, values are not assigned to the variables. Any combination of values could be processed by this function using the truth tables in C. (C) The truth tables of the myogenic developmental pathway. (D) A three-symbol, four-state finite automaton that describes the SAT problem F. State S0, multipotent paraxial cell; states S1/S1′, unspecified paraxial cell; state S2, determined paraxial cell (myogenic cell). The white arrow represents the initial state, arrows represent transition rules, and their colors represent the symbols. The green circle represents the accepting state. The order of signals has no importance. Yet, a cell could be exposed to only Wnt signaling, thus accepting state S1′. Alternatively,a cell could be exposed to only Shh or noggin, minus Bmp4, thus accepting state S1. Note that, although we have used four soluble proteins,only three symbols are used, owing to the close dependence of noggin and Bmp4 signals. Therefore, noggin minus Bmp4 represents the stoichiometric ratio between the two components. If this ratio is negative, then the direction of progression is opposite to the arrow direction. (E) A summary of all possible solutions leading to myogenesis in SAT formalism generated from the function F in B. The colored clauses indicate an input that collapses into another (see remarks in Table S1 in the supplementary material. For further explanation, see section The Shh-noggin correlation hypothesis' in the text). The green clauses represent scenarios that have no biological meaning.

Fig. 2.

Myogenesis as a SAT problem presented in DNF using TNS. (A) A summary of all possible conditions from Table 1 that lead to myogenesis in SAT formalism. w, Wnt level; s, Shh level; g,noggin level; b, Bmp4 level; 0, less than the normal physiological concentration; 1, the normal physiological concentration; 2, above the normal physiological concentration. (B) Myogenesis SAT problem. As myogenesis is antagonized by Bmp4, the effect of Bmp4 on myogenesis is inverse to its concentration. Therefore, we used its negation value and assigned it to the SAT formula. Note that, in this formulation, values are not assigned to the variables. Any combination of values could be processed by this function using the truth tables in C. (C) The truth tables of the myogenic developmental pathway. (D) A three-symbol, four-state finite automaton that describes the SAT problem F. State S0, multipotent paraxial cell; states S1/S1′, unspecified paraxial cell; state S2, determined paraxial cell (myogenic cell). The white arrow represents the initial state, arrows represent transition rules, and their colors represent the symbols. The green circle represents the accepting state. The order of signals has no importance. Yet, a cell could be exposed to only Wnt signaling, thus accepting state S1′. Alternatively,a cell could be exposed to only Shh or noggin, minus Bmp4, thus accepting state S1. Note that, although we have used four soluble proteins,only three symbols are used, owing to the close dependence of noggin and Bmp4 signals. Therefore, noggin minus Bmp4 represents the stoichiometric ratio between the two components. If this ratio is negative, then the direction of progression is opposite to the arrow direction. (E) A summary of all possible solutions leading to myogenesis in SAT formalism generated from the function F in B. The colored clauses indicate an input that collapses into another (see remarks in Table S1 in the supplementary material. For further explanation, see section The Shh-noggin correlation hypothesis' in the text). The green clauses represent scenarios that have no biological meaning.

A three-symbol, four-state finite automaton is presented that describes this SAT problem (Fig. 2D). A finite automaton is an information-processing machine possessing several states that progresses in a unidirectional manner. Finite automata are extensively used in computer science and in logic(Benenson et al., 2001; Hopcroft et al., 2000; McCulloch and Pitts, 1943). The automaton can be in one of a finite number of internal states, of which one is designated as an initial state and others are designated as accepting states. The automaton can change states, by a defined set of transition rules,in response to a given symbol, based on the current state and the current symbol. Thus, given a specific state that reads one symbol, it might change into a different state. Once the state is changed, new transition rules are applied. The automaton might suspend in the middle of a computation without reaching an accepting final state if no transition rule applies. A computation is terminated upon processing the last input symbol. In following this logic,the automaton can move within a given environment of symbols (molecules) along defined routes (lineages). Therefore, such a presentation of finite automata can serve to describe developmental processes in general and myogenesis in particular. Graphical representation of this finite automaton demonstrates the signals (symbols, arrows) needed in order to reach the accepting state (i.e. a myogenic cell). The automaton represents myogenesis in a more comprehensive manner than Łukasiewicz logic. The signals in the automaton indicate above-threshold levels for the Wnt proteins and Shh and the stoichiometric relations between noggin and Bmp4. We generated the automaton based on the true clauses (Fig. 2A). Any true clause was illustrated using symbols (arrows) and states. The symbols are the morphogens and they are the only data presented in the SAT expression. The states, however, were chosen as intermediate stations' between transition rules. These states are required by automata definitions(Benenson et al., 2001; Gopalakrishnan, 2006; Hopcroft et al., 2000) and could represent a real biological meaning. The different states represent a multipotent paraxial cell (S0, Fig. 2D), a specified paraxial cell (S1 or S1′, Fig. 2D) and a determined paraxial, myogenic cell (S2, Fig. 2D). The automaton was generated graphically. Every two identical routes were reduced, until no further reduction was possible. The automaton was checked by all possible clauses to verify that none of the false clauses could reach the accepting state (S2). The creation of the automaton was performed independently of the SAT problem, indicating two individual, unrelated logic methods.

Fig. 3.

The effect of medio-ventral ectopic insertion of Wnt1-secreting cells on somitic myogenesis. (A) Wnt1-secreting cells inserted next to the notochord (dashed line on the right side compared with the contralateral control side) cause a reduction in Shh signaling and a ventro-medial expansion of the myotomal domain, as described schematically using TNS. According to this schematic prediction, Shh will be reduced in the ventral domain from S2 to S1, and hence its downstream genes will be affected accordingly. (B-L) As confirmed experimentally, Wnt1-secreting cells reduce Shh levels in the ventral domain as evident in the reduction of Shh expression in the Shh-induced floor plate (B). The floor plate domain is marked by Shh expression on the left control side and the red dashed line on the right, the reduction in the Shh-induced receptor, Patched (C) and the downstream chondrogenic marker, Pax1 (D). As expected from the TNS description of the somitic morphogenetic field, the myogenic markers MyoD (E) and Myf5 (F)were expanded ventrally, together with enhancement and slight ventral expansion of noggin expression (G) and the dermomyotomal and epithelial markers Pax3 (H) and paraxis (I), respectively. Note that in all cases the somite retains its epithelial state compared with the contralateral control side. RatB1 parental cells that are not expressing Wnt1 were inserted as control experiments next to the notochord. No effect was observed on the normal expression pattern of MyoD (J), Myf5 (K) and Pax1 (L). n, notochord;nt, neural tube; s, somite. Scale bar: 30 μm.

Fig. 3.

The effect of medio-ventral ectopic insertion of Wnt1-secreting cells on somitic myogenesis. (A) Wnt1-secreting cells inserted next to the notochord (dashed line on the right side compared with the contralateral control side) cause a reduction in Shh signaling and a ventro-medial expansion of the myotomal domain, as described schematically using TNS. According to this schematic prediction, Shh will be reduced in the ventral domain from S2 to S1, and hence its downstream genes will be affected accordingly. (B-L) As confirmed experimentally, Wnt1-secreting cells reduce Shh levels in the ventral domain as evident in the reduction of Shh expression in the Shh-induced floor plate (B). The floor plate domain is marked by Shh expression on the left control side and the red dashed line on the right, the reduction in the Shh-induced receptor, Patched (C) and the downstream chondrogenic marker, Pax1 (D). As expected from the TNS description of the somitic morphogenetic field, the myogenic markers MyoD (E) and Myf5 (F)were expanded ventrally, together with enhancement and slight ventral expansion of noggin expression (G) and the dermomyotomal and epithelial markers Pax3 (H) and paraxis (I), respectively. Note that in all cases the somite retains its epithelial state compared with the contralateral control side. RatB1 parental cells that are not expressing Wnt1 were inserted as control experiments next to the notochord. No effect was observed on the normal expression pattern of MyoD (J), Myf5 (K) and Pax1 (L). n, notochord;nt, neural tube; s, somite. Scale bar: 30 μm.

Two major findings were raised from the mathematical formulation:

1. The prediction of biochemical dependence. The automaton we designed to describe myogenesis is extremely simple, indicating two general routes for myogenesis progression, and in both the presence of Wnt proteins is crucial. Note that, for the progression of the automaton from left to right, Wnt signaling is required. However, for the progression from top to bottom, two types of signals are possible, and therefore Shh and noggin are identical in their results. Similarly, the SAT problem described in Fig. 2B comprises two clauses,both containing w and b, but one contains s whereas the other contains g. Thus, from both the automaton and the SAT formalism viewpoints, Shh and noggin are redundant. This formal redundancy raises an intriguing hypothesis that these two factors are located on the same biochemical pathway, which we define as the Shh-noggin hypothesis.

2. Prediction of additional scenarios. The function F and the automaton (Fig. 2B,D) predict that more clauses will lead to myogenesis(Fig. 2E, colored clauses). These include two types of predicted clauses. In one group (red), g=0. In this group, both w and s equal 1 or 2, and b equals 0 or 1. In a second group (green), w=1 or 2, s=0, g=1 and b equals 0 or 1.

We aimed to determine these findings as outlined below.

### Demonstration of the concept: changing the somitic morphogenetic field

The objectives of this section are to demonstrate the effect of a single morphogen on the somitic morphogenetic field, to demonstrate the prediction power of Łukasiewicz logic when describing this field and to show the first experimental verification of the Shh-noggin hypothesis.

In examining the somitic morphogenetic field, it can be seen that gradients of the variables w, s and b can be described in different domains by TNS (Fig. 1). Therefore, manipulation experiments, such as the introduction of barriers,ablation of surrounding tissues and the addition of ectopic proteins, could change not only the value (concentration) of a specific variable but also the concentration of other proteins, leading to different topical outputs in the morphogenetic field (Fig. 3A). For instance, the Wnt proteins and Shh antagonize each other by different mechanisms, resulting in either the reduction of the free soluble protein in the medium or an interruption of the protein signal transduction(Lee et al., 2000; Lee et al., 2001). It has been shown in mouse embryo PSM explants that Shh upregulates the gene encoding the Wnt modulator Sfrp2 to block the activity of several Wnt proteins(Lee et al., 2000). Similarly,the Wnt proteins were shown to induce the growth-suppressing protein Gas1,which binds to Shh and seems to diminish its activity in mouse explant cultures (Lee et al., 2001). When Shh was ectopically added both medio-dorsally or latero-dorsally to the somite, elevated noggin and MyoD levels were observed(Table 1; see Table S1 in the supplementary material, scenarios 52 and 53), leading to the assumption that Shh activates noggin expression (Hirsinger et al., 1997). Furthermore, in three different experiments - when the Shh source is located near the neural tube roof plate, when the Shh source is located at the dorso-lateral region of the somite, and upon rotation of the neural-tube-notochord complex - the MyoD expression pattern is altered, with its maximal expression being at a constant distance from the Shh source(Dietrich et al., 1997). An intriguing question is why both noggin and MyoD are not expressed near the source of Shh, the notochord and the neural tube floor plate. A plausible answer is that when the origin of Shh approaches Wnt-secreting tissues (the ectoderm, the dorsal part of the neural tube or ectopic Wnt-secreting cells),the appropriate balance between Shh and Wnt concentrations required for myogenesis is achieved. In order to assess this hypothesis, we designed such an experiment and predicted its result using Łukasiewicz logic(Fig. 3A). In this prediction, Wnt1-expressing cells that will be implanted into the ventro-medial part of the somite adjacent to the notochord will decrease Shh levels from S2 to S1 as defined in TNS, and, as a result, noggin and myogenic markers will expand ventrally (compare with Fig. 1, right field). Indeed,we found that medio-ventral ectopic insertion of Wnt1-secreting cells downregulates Shh signaling in the medio-ventral domain of the somitic field,as exhibited by downregulation of Shh in the floor plate, its receptor patched and the paired box protein Pax1 in the somite(Fig. 3B-D; see Table S2 in the supplementary material). Furthermore, Wnt1 insertion upregulates and ventrally expands MyoD, Myf5, noggin, Pax3 and paraxis, and, consistent with previous studies, maintains the somite in its epithelial state(Fig. 3E-I; see Table S2 in the supplementary material) (Borello et al.,1999; Cauthen et al.,2001; Galli et al.,2004; Hirsinger et al.,1997; Schmidt et al.,2004; Wagner et al.,2000). The ventral expansion of noggin, similar to the expansion of myogenic markers, provides a possible clue for the dependence of noggin expression on Shh signaling. Control experiments in which RatB1A-LNCX parental cells were implanted into the ventro-medial part of the somite adjacent to the notochord resulted in no change in myogenic or sclerogenic markers(Fig. 3J-L; see Table S2 in the supplementary material).

Fig. 4.

Blocking Shh signaling downregulates noggin expression in somites.(A,B) A barrier inserted between the midline tissues and the PSM(A), or ablation of the notochord from the PSM anterior level (B), causes a loss of noggin expression in somites, as is evident in wholemount RNA in situ hybridization. (C-H) A cross-section through the barrier level reveals no noggin expression on the operated side (C); however, Pax3 expression is expanded (D). When Wnt1-secreting cells were implanted laterally to a barrier that was inserted between the midline tissues and the PSM, no MyoD expression was observed compared with the contralateral side, where implanted Wnt1-secreting cells caused a ventral expansion of this gene product (E). Analyzing noggin in a similar experiment where Wnt1-secreting cells were implanted laterally to a barrier, no noggin expression was observed (F). Note,in all cases presented in C-F, the somite retained its epithelial state on the operated side. Cross-sections through regions G and H in B show no noggin expression in the absence of the notochord (G, arrow) compared with a more posterior region where noggin expression is normal (H). n, notochord; nt,neural tube; s, somite. Scale bar: 100 μm in A,B; 30 μm in C-H.

Fig. 4.

Blocking Shh signaling downregulates noggin expression in somites.(A,B) A barrier inserted between the midline tissues and the PSM(A), or ablation of the notochord from the PSM anterior level (B), causes a loss of noggin expression in somites, as is evident in wholemount RNA in situ hybridization. (C-H) A cross-section through the barrier level reveals no noggin expression on the operated side (C); however, Pax3 expression is expanded (D). When Wnt1-secreting cells were implanted laterally to a barrier that was inserted between the midline tissues and the PSM, no MyoD expression was observed compared with the contralateral side, where implanted Wnt1-secreting cells caused a ventral expansion of this gene product (E). Analyzing noggin in a similar experiment where Wnt1-secreting cells were implanted laterally to a barrier, no noggin expression was observed (F). Note,in all cases presented in C-F, the somite retained its epithelial state on the operated side. Cross-sections through regions G and H in B show no noggin expression in the absence of the notochord (G, arrow) compared with a more posterior region where noggin expression is normal (H). n, notochord; nt,neural tube; s, somite. Scale bar: 100 μm in A,B; 30 μm in C-H.

Another example of changing the somitic morphogenetic field following the schematic prediction expressed in TNS is presented in Fig. S2 in the supplementary material. These experiments demonstrate the realization of our description of the somitic morphogenetic field by Łukasiewicz logic and the power of its prediction.

### The Shh-noggin correlation hypothesis

The objective of this section is to demonstrate the close dependence of the noggin expression pattern on that of Shh, thus proving the prediction of the SAT problem and the automaton in which Shh and noggin are located on the same biochemical pathway (first finding in the Mathematical meaning and prediction ability section). In addition, it reconciles findings in which new clauses(scenarios) were predicted by the mathematical formulation mentioned above(second finding in the same section).

On the basis of the observations described in Fig. 3 and the insight that emerged from the automaton and the SAT problem, we concluded that a linkage between Shh signaling and noggin expression is inevitable. To examine the hypothesis that noggin expression requires Shh signaling, we carried out three experiments: (1) we inserted a barrier between the midline tissues and the PSM(Fig. 4A,C-F; see Table S2 in the supplementary material), (2) we ablated the notochord from the PSM anterior area (Fig. 4B,G-H; see Table S2 in the supplementary material) and (3) we implanted Wnt1-secreting cells lateral to a barrier that was inserted between the midline tissues and the PSM. Expression of noggin was not observed on the experimental side of the embryo, despite the presence of Wnt1, in any of the experiments(Fig. 4F). Furthermore, it was previously demonstrated that Wnt1 can rescue noggin expression in the somite when Wnt-secreting tissue was ablated(Hirsinger et al., 1997). Therefore, we conclude that Shh cannot act alone to elevate noggin expression. These results strongly support our hypothesis that noggin expression is downstream of Shh signaling. As noggin was shown to act downstream of the Wnt proteins and Shh in separate experimental setups (see Fig. S2 in the supplementary material) (Hirsinger et al.,1997; Reshef et al.,1998), and based on our current gain- and loss-of-function experiments, we conclude that the Wnt proteins and Shh have a combinatorial effect on noggin expression, thereby elucidating a fundamental part of myogenesis circuitry. Therefore, normal physiological expression (value 1) of noggin requires the combinatorial effect of normal levels (value 1) of Wnt proteins and Shh signaling (Fig. 3; Fig. 4). Moreover, the expression pattern of noggin in somitic cells corresponds to that of Bmp4 in surrounding tissues(Hirsinger et al., 1997; Marcelle et al., 1997; Reshef et al., 1998), and it has been shown that Bmp4 can upregulate noggin expression(Sela-Donenfeld and Kalcheim,2002). Taking together our results and other reports in the literature, we suggest that Bmp4 induces the ability of somitic cells to express noggin in response to the combinatorial effect of the Wnt proteins and Shh.

It is clear now that there are no situations in which noggin equals 0 while both the Wnt proteins and Shh equal 1 or 2(Fig. 2E, red). Moreover, there are no situations in which noggin equals 1 while one of the Wnt proteins or Shh equals 2 and the other equals 1 or 2(Fig. 2E, blue). Our findings also reveal the unique status of the green scenarios in Fig. 2E (indicated as ? in Table 1). Although mathematically these scenarios must lead to myogenesis, the biological system could not allow noggin to equal 1 while Shh equals 0, thus forcing noggin levels to collapse to the level 0. Therefore, these unique scenarios will not lead to myogenesis (F in Table S1 in the supplementary material). These results and observations were retro-fitted into Table 1 and allow the creation of the complete 81 scenarios (see Table S1 in the supplementary material),illuminating some of the scenarios. Therefore, in certain scenarios, the initial experimental input might constitute a forbidden situation in the somite that would collapse into another scenario (see Table S1 in the supplementary material).

As noggin operates as a Bmp4 antagonist, the combined effect of noggin and Bmp4 depends on stoichiometric relations between the two factors. If the ratio favors Bmp4, myogenesis will be disturbed, whereas if the ratio favors noggin,myogenesis can proceed. Because in our ternary presentation of variables at excessive levels (value 2) their absolute concentration is not defined, the balance between noggin and Bmp4 at high levels could vary with their relative stoichiometry. Therefore, some of the 81 scenarios presented in Table 1 and Table S1 in the supplementary material are meaningless, owing to unrealistic stoichiometries.

Several studies indicate that the initial steps of myogenesis are independent of environmental inputs, which are only required later for the enhancement and/or maintenance of the initial events. This idea is supported by experiments showing that pre-somitic cells that dissociated to produce a single-cell suspension in a serum-free medium prefer the myogenic differentiation pathway (George-Weinstein et al., 1996; George-Weinstein et al., 1997; Gerhart et al.,2004). Moreover, it was shown in a certain experimental set-up that the initiation of MyoD and Myf5 expression is actually an intrinsic property of the pre-somitic mesoderm derived by the Wnt proteins and that external signals are likely to be required for their actual in vivo expression(Linker et al., 2003). Furthermore, epiblast MyoD-positive (MyoDpos) cells populate later in development, mainly in somitic regions. These cells were shown to secrete noggin into their somitic environment(Gerhart et al., 2006). In this work, Gerhart et al. targeted and destroyed MyoDpos cells,thus specifically lowering noggin expression within the somite. As a result,myotomal markers were reduced, but not eliminated, suggesting the existence of another source of myotomal cells in the somite. Addition of exogenous noggin could compensate for the loss of MyoD, supporting the notion that other myotomal cells exist and are influenced by other signaling factors. There was no discernible link between Shh or the Wnt proteins and noggin in the Gerhart study. The combination of signaling factors, as presented in our study from the perspective of the somitic morphogenetic field, can be described as w=1, s=1, g=0 and b=1. This combination,according to our treatment, does not exist as there is no situation in which w and s equal 1 and g equals 0. Consistent with this statement, Gerhart's ablation experiments resulted only in a reduction of myotomal markers but not their complete elimination. As we pointed out in the subsection `noggin is a unique morphogen', damaging somitic cells that have reached a specific fate can be compared to performing a computation on a broken computer. Although the Gerhart study is important in understanding the role of epiblast MyoDpos cells in somitic myogenesis, it has to be circumvented in our case, at least with respect to the ablation experiments.

Hints for the existence of the above-discussed mechanism can be found in other vertebrates. For example, it has been shown that hedgehog-related proteins in zebrafish are required for myogenesis and that Bmp4 and the related protein dorsalin1 antagonize myogenesis(Stickney et al., 2000). It was also demonstrated that, as is the case for avian GBP, which is a Wnt11 homolog expressed in adaxial cells, its ectopic injection results in expansion of MyoD expression in zebrafish somites(Sumoy et al., 1999). It has also been demonstrated that loss of Bmp signaling in zebrafish leads to expansion of the trunk muscles and increased expression of MyoD(Pyati et al., 2005). Similar results were reported in Xenopus(Re'em-Kalma et al., 1995). Shh-injected Xenopus embryos exhibited significantly more muscle fibers than controls (Grimaldi et al.,2004). In Xenopus, Xwnt8 is essential for the development of myogenesis in somites (Hoppler et al.,1996). Bmp and noggin were shown in Xenopus to regulate myogenesis in a manner similar to that described in our model(Re'em-Kalma et al., 1995). All these observations support the notion that the above-described automaton of myogenesis applies to all vertebrates. It seems plausible that our model for the spatial and temporal coordination of myogenesis in vertebrate embryonic development is evolutionarily conserved.

The notion of applying computational models to developmental biology goes back to Alan Turing, who defined a system of chemicals (morphogens) that influence the developmental fate of a tissue(Turing, 1952). Turing's formalism, which uses complex differential equations, has been further developed and has also led to some experimental studies(Tomlin and Axelrod, 2007). Such models, however, require information about concentrations of the relevant morphogens and their kinetic parameters, none of which is easily accessible in a complex developmental system.

Logic can portray truth with various resolutions. The binary Boolean logic,which was introduced by George Boole, was followed by Łukasiewicz TNS logic. Grigore Moisil has further refined this latter formalism to multi-valued logic, which has paved the way for the introduction of the fuzzy logic by Zadeh, a continuous space of logic in which the space between true and false, or 0 and 1, could be divided into infinite sectors presenting a continuous gradient of truth (Boicescu et al., 1991). This fuzzy logic formalism is related back to continuous mathematics, some of which can be described by differential equations. When describing a system in Boolean logic, very little information is needed, and an unambiguous output is accepted. With increased resolution,finer descriptions are accepted, but more information is required. Although differential calculus could be most appropriate for describing developmental processes, this strategy requires substantial molecular information. Given our current insufficient understanding of myogenesis, the Łukasiewicz TNS strategy appears to be a very useful approach for describing the phenomena.

This study demonstrates the benefits of describing developmental progression using SAT formalism. Describing the tissue environment systematically predicts the tissue fate and allows a diversion from that fate by changing the values (concentrations) of the appropriate parameters. TheŁukasiewicz formalism allows for easy identification of missing data and helps in experimental design. Furthermore, applying a similar formalism to genetic networks has proven to be remarkably robust(Tomlin and Axelrod, 2007). This study does not try to find solutions to the myogenesis SAT problem, which has existed in the literature for over ten years. However, the SAT problem structure, which is the combination of variable values within the clauses,reveals the logic of the developmental process and helps in discovering the biological pathways governing it. Construction of a finite automaton that best describes the true clauses can lead to a better understanding of biochemical pathways. In this specific case, the finite automaton and SAT formalism have led to the inevitable conclusion that myogenesis requires only Wnt signaling for its progression, thus changing the current understanding of somitic myogenesis. According to a previous model, a combinatorial effect between the Wnt proteins and Shh is required for myogenesis(Borello et al., 2006; Munsterberg et al., 1995; Munsterberg and Lassar, 1995; Stern et al., 1995); however,nothing is known about the molecular nature of this combinatorial effect. Conversely, other studies present data showing that the Wnt proteins and Shh antagonize each other (Lee et al.,2000; Lee et al.,2001). Adding to the complexity, it was demonstrated that a combinatorial effect between the Wnt proteins and noggin is sufficient for myogenesis (Reshef et al.,1998) and that noggin addition lateral to the somites can promote myogenesis even when MyoD-expressing cells are removed from the somite(Gerhart et al., 2006). Recently, it was demonstrated that different members of the Wnt family antagonize each other but still support the epithelial state of the dermomyotome (Geetha-Loganathan et al.,2006). Our current study reconciles these seemingly contradicting statements by a simple biochemical model generated from an algebraic approach. According to this solution, the Wnt proteins alone are sufficient for myogenesis, and the aim of all combinations of the Wnt proteins and Shh or the Wnt proteins and anti-Bmp4 molecules is to release the Bmp4 inhibitory effect on myogenesis (Fig. 5A). Moreover, as an outcome from our algebraic model, we suggest that the antagonistic mutual effect between the Wnt proteins and Shh aims to control the accurate topical induction of the muscle pioneer cells and allow for the induction of both a positive control for their emergence (the combinatorial effect emerged from a precise range of morphogen concentrations) and a negative control on the borders of this muscle pioneer cell domain, resulting from an inappropriate combination of morphogen concentration levels(Fig. 5B).

Fig. 5.

Schematic presentation of signaling molecules affecting somitic myogenesis. (A) The relationships between signaling molecules and important transcription factors that participate in compartmentalization and differentiation of the somite. D, dorsal; V, ventral. The dotted black line indicates that Bmp4 presumably creates the ability to express noggin. The dashed gray line indicates a possible Shh signal upregulating early myotomal markers. (B) A schematic presentation of the somitic morphogenetic field demonstrating overlapping of the appropriate signaling molecules to promote the appearance of muscle pioneer cells with the proper space and timing (green area). W, Wnt proteins source; S, Shh source; b, Bmp4 source.

Fig. 5.

Schematic presentation of signaling molecules affecting somitic myogenesis. (A) The relationships between signaling molecules and important transcription factors that participate in compartmentalization and differentiation of the somite. D, dorsal; V, ventral. The dotted black line indicates that Bmp4 presumably creates the ability to express noggin. The dashed gray line indicates a possible Shh signal upregulating early myotomal markers. (B) A schematic presentation of the somitic morphogenetic field demonstrating overlapping of the appropriate signaling molecules to promote the appearance of muscle pioneer cells with the proper space and timing (green area). W, Wnt proteins source; S, Shh source; b, Bmp4 source.

The embryonic developmental program evokes myogenesis at early stages as a default pathway in gastrulating cells driven by Wnt signaling(Frank and Harland, 1991; Re'em-Kalma et al., 1995). In order to coordinate the developmental progression of myogenic tissues with other mesodermal lineages, myogenesis must be restrained. Thus, evolution has coordinated the action of all four proteins to unleash myogenesis at the appropriate location and timing. We define this process by the simple but powerful formula:
$\mathrm{Wnt}+(-\mathrm{BMP}4)=\mathrm{myogenesis}{\ },$
where Shh levels can control the biological outcome of this formula by regulating Wnt signaling and controlling the expression of noggin.

We acknowledge Gheoghe Pǎun of the Romanian Academy and Academia Europaea and Thomas Schultheiss from the Technion for their important insights on the manuscript. E.K. is the incumbent of the Benno Gitter & Ilana Ben-Ami Chair of Biotechnology, Technion. This work was supported by the National Science Foundationunder Grant No. 0523928. We thank the Israel-US Binational Science Foundation, the German-Israeli Project Cooperation (DIP)and the Skaggs Institute for Chemical Biology.

Albert, R. and Othmer, H. G. (
2003
). The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster.
J. Theor. Biol.
223
,
1
-18.
Aoyama, H. (
1993
). Developmental plasticity of the prospective dermatome and the prospective sclerotome region of an avian somite.
Dev. Growth Differ.
35
,
507
-519.
Aoyama, H. and Asamoto, K. (
1988
). Determination of somite cells: independence of cell differentiation and morphogenesis.
Development
104
,
15
-28.
Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z. and Shapiro, E. (
2001
). Programmable and autonomous computing machine made of biomolecules.
Nature
414
,
430
-434.
Boicescu, V., Filipoiu, A., Georgescu, G. and Rudeanu, S.(
1991
). Łukasiewicz-Moisil algebras.
Ann. Discr. Math.
49
.
Borello, U., Coletta, M., Tajbakhsh, S., Leyns, L., De Robertis,E. M., Buckingham, M. and Cossu, G. (
1999
). Transplacental delivery of the Wnt antagonist Frzb1 inhibits development of caudal paraxial mesoderm and skeletal myogenesis in mouse embryos.
Development
126
,
4247
-4255.
Borello, U., Berarducci, B., Murphy, P., Bajard, L., Buffa, V.,Piccolo, S., Buckingham, M. and Cossu, G. (
2006
). The Wnt/beta-catenin pathway regulates Gli-mediated Myf5 expression during somitogenesis.
Development
133
,
3723
-3732.
Borycki, A. G., Mendham, L. and Emerson, C. P., Jr(
1998
). Control of somite patterning by Sonic hedgehog and its downstream signal response genes.
Development
125
,
777
-790.
Cairns, D. M., Sato, M. E., Lee, P. G., Lassar, A. B. and Zeng,L. (
2008
). A gradient of Shh establishes mutually repressing somitic cell fates induced by Nkx3.2 and Pax3.
Dev. Biol.
323
,
152
-165.
Cauthen, C. A., Berdougo, E., Sandler, J. and Burrus, L. W.(
2001
). Comparative analysis of the expression patterns of Wnts and Frizzleds during early myogenesis in chick embryos.
Mech. Dev.
104
,
133
-138.
Christ, B. and Ordahl, C. P. (
1995
). Early stages of chick somite development.
Anat. Embryol.(Berl)
191
,
381
-396.
Christ, B., Brand-Saberi, B., Grim, M. and Wilting, J.(
1992
). Local signalling in dermomyotomal cell type specification.
Anat. Embryol. (Berl)
186
,
505
-510.
Davis, R. L., Weintraub, H. and Lassar, A. B.(
1987
). Expression of a single transfected cDNA converts fibroblasts to myoblasts.
Cell
51
,
987
-1000.
de la Brousse, F. C. and Emerson, C. P., Jr(
1990
). Localized expression of a myogenic regulatory gene, qmf1,in the somite dermatome of avian embryos.
Genes Dev.
4
,
567
-581.
Dietrich, S., Schubert, F. R. and Lumsden, A.(
1997
). Control of dorsoventral pattern in the chick paraxial mesoderm.
Development
124
,
3895
-3908.
Emerson, C. P. (
1990
). Myogenesis and developmental control genes.
Curr. Opin. Cell Biol.
2
,
1065
-1075.
Emerson, C. P., Jr (
1993
). Embryonic signals for skeletal myogenesis: arriving at the beginning.
Curr. Opin. Cell Biol.
5
,
1057
-1064.
Frank, D. and Harland, R. M. (
1991
). Transient expression of XMyoD in non-somitic mesoderm of Xenopus gastrulae.
Development
113
,
1387
-1393.
Galli, L. M., Willert, K., Nusse, R., Yablonka-Reuveni, Z.,Nohno, T., Denetclaw, W. and Burrus, L. W. (
2004
). A proliferative role for Wnt-3a in chick somites.
Dev. Biol.
269
,
489
-504.
Geetha-Loganathan, P., Nimmagadda, S., Huang, R., Christ, B. and Scaal, M. (
2006
). Regulation of ectodermal Wnt6 expression by the neural tube is transduced by dermomyotomal Wnt11: a mechanism of dermomyotomal lip sustainment.
Development
133
,
2897
-2904.
George-Weinstein, M., Gerhart, J., Reed, R., Flynn, J.,Callihan, B., Mattiacci, M., Miehle, C., Foti, G., Lash, J. W. and Weintraub,H. (
1996
). Skeletal myogenesis: the preferred pathway of chick embryo epiblast cells in vitro.
Dev. Biol.
173
,
279
-291.
George-Weinstein, M., Gerhart, J., Blitz, J., Simak, E. and Knudsen, K. A. (
1997
). N-cadherin promotes the commitment and differentiation of skeletal muscle precursor cells.
Dev. Biol.
185
,
14
-24.
Gerhart, J., Neely, C., Stewart, B., Perlman, J., Beckmann, D.,Wallon, M., Knudsen, K. and George-Weinstein, M. (
2004
). Epiblast cells that express MyoD recruit pluripotent cells to the skeletal muscle lineage.
J. Cell Biol.
164
,
739
-746.
Gerhart, J., Elder, J., Neely, C., Schure, J., Kvist, T.,Knudsen, K. and George-Weinstein, M. (
2006
). MyoD-positive epiblast cells regulate skeletal muscle differentiation in the embryo.
J. Cell Biol.
175
,
283
-292.
Gerhart, J., Neely, C., Elder, J., Pfautz, J., Perlman, J.,Narciso, L., Linask, K. K., Knudsen, K. and George-Weinstein, M.(
2007
). Cells that express MyoD mRNA in the epiblast are stably committed to the skeletal muscle lineage.
J. Cell Biol.
178
,
649
-660.
Gopalakrishnan, G. L. (
2006
).
Computation Engineering Applied Automata Theory and Logic
. New York: Springer.
Grimaldi, A., Tettamanti, G., Martin, B. L., Gaffield, W.,Pownall, M. E. and Hughes, S. M. (
2004
). Hedgehog regulation of superficial slow muscle fibres in Xenopus and the evolution of tetrapod trunk myogenesis.
Development
131
,
3249
-3262.
Hamburger, V. and Hamilton, H. L. (
1992
). A series of normal stages in the development of the chick embryo. 1951.
Dev. Dyn.
195
,
231
-272.
Hirsinger, E., Duprez, D., Jouve, C., Malapert, P., Cooke, J. and Pourquie, O. (
1997
). Noggin acts downstream of Wnt and Sonic Hedgehog to antagonize BMP4 in avian somite patterning.
Development
124
,
4605
-4614.
Hopcroft, J. E., Motwani, R. and Ullman, J. D.(
2000
).
Introduction to Automata Theory, Languages and Computation
Hoppler, S., Brown, J. D. and Moon, R. T.(
1996
). Expression of a dominant-negative Wnt blocks induction of MyoD in Xenopus embryos.
Genes Dev.
10
,
2805
-2817.
Huang, S. (
1999
). Gene expression profiling,genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery.
J. Mol. Med.
77
,
469
-480.
James, R. G. and Schultheiss, T. M. (
2005
). Bmp signaling promotes intermediate mesoderm gene expression in a dose-dependent,cell-autonomous and translation-dependent manner.
Dev. Biol.
288
,
113
-125.
Johnson, R. L., Laufer, E., Riddle, R. D. and Tabin, C.(
1994
). Ectopic expression of Sonic hedgehog alters dorsal-ventral patterning of somites.
Cell
79
,
1165
-1173.
Kahane, N., Cinnamon, Y. and Kalcheim, C.(
1998
). The origin and fate of pioneer myotomal cells in the avian embryo.
Mech. Dev.
74
,
59
-73.
Lee, C. S., Buttitta, L. A., May, N. R., Kispert, A. and Fan, C. M. (
2000
). SHH-N upregulates Sfrp2 to mediate its competitive interaction with WNT1 and WNT4 in the somitic mesoderm.
Development
127
,
109
-118.
Lee, C. S., Buttitta, L. and Fan, C. M. (
2001
). Evidence that the WNT-inducible growth arrest-specific gene 1 encodes an antagonist of sonic hedgehog signaling in the somite.
98
,
11347
-11352.
Linker, C., Lesbros, C., Stark, M. R. and Marcelle, C.(
2003
). Intrinsic signals regulate the initial steps of myogenesis in vertebrates.
Development
130
,
4797
-4807.
Marcelle, C., Stark, M. R. and Bronner-Fraser, M.(
1997
). Coordinate actions of BMPs, Wnts, Shh and noggin mediate patterning of the dorsal somite.
Development
124
,
3955
-3963.
Maroto, M., Reshef, R., Munsterberg, A. E., Koester, S.,Goulding, M. and Lassar, A. B. (
1997
). Ectopic Pax-3 activates MyoD and Myf-5 expression in embryonic mesoderm and neural tissue.
Cell
89
,
139
-148.
McCulloch, W. S. and Pitts, W. A. (
1943
). A logical calculus immanent in nervous activity.
Bull. Math. Biophys.
5
,
115
-133.
Munsterberg, A. E. and Lassar, A. B. (
1995
). Combinatorial signals from the neural tube, floor plate and notochord induce myogenic bHLH gene expression in the somite.
Development
121
,
651
-660.
Munsterberg, A. E., Kitajewski, J., Bumcrot, D. A., McMahon, A. P. and Lassar, A. B. (
1995
). Combinatorial signaling by Sonic hedgehog and Wnt family members induces myogenic bHLH gene expression in the somite.
Genes Dev.
9
,
2911
-2922.
Olson, E. N. (
1990
). MyoD family: a paradigm for development?
Genes Dev.
4
,
1454
-1461.
Ordahl, C. P. and Le Douarin, N. M. (
1992
). Two myogenic lineages within the developing somite.
Development
114
,
339
-353.
Ott, M. O., Bober, E., Lyons, G., Arnold, H. and Buckingham,M. (
1991
). Early expression of the myogenic regulatory gene,myf-5, in precursor cells of skeletal muscle in the mouse embryo.
Development
111
,
1097
-1107.
Pourquie, O., Coltey, M., Breant, C. and Le Douarin, N. M.(
1995
). Control of somite patterning by signals from the lateral plate.
92
,
3219
-3223.
Pourquie, O., Fan, C. M., Coltey, M., Hirsinger, E., Watanabe,Y., Breant, C., Francis-West, P., Brickell, P., Tessier-Lavigne, M. and Le Douarin, N. M. (
1996
). Lateral and axial signals involved in avian somite patterning: a role for BMP4.
Cell
84
,
461
-471.
Pownall, M. E. and Emerson, C. P., Jr (
1992
). Sequential activation of three myogenic regulatory genes during somite morphogenesis in quail embryos.
Dev. Biol.
151
,
67
-79.
Pownall, M. E., Strunk, K. E. and Emerson, C. P., Jr(
1996
). Notochord signals control the transcriptional cascade of myogenic bHLH genes in somites of quail embryos.
Development
122
,
1475
-1488.
Pyati, U. J., Webb, A. E. and Kimelman, D.(
2005
). Transgenic zebrafish reveal stage-specific roles for Bmp signaling in ventral and posterior mesoderm development.
Development
132
,
2333
-2343.
Re'em-Kalma, Y., Lamb, T. and Frank, D. (
1995
). Competition between noggin and bone morphogenetic protein 4 activities may regulate dorsalization during Xenopus development.
92
,
12141
-12145.
Reshef, R., Maroto, M. and Lassar, A. B.(
1998
). Regulation of dorsal somitic cell fates: BMPs and Noggin control the timing and pattern of myogenic regulator expression.
Genes Dev.
12
,
290
-303.
Sassoon, D., Lyons, G., Wright, W. E., Lin, V., Lassar, A.,Weintraub, H. and Buckingham, M. (
1989
). Expression of two myogenic regulatory factors myogenin and MyoD1 during mouse embryogenesis.
Nature
341
,
303
-307.
Schmidt, C., Stoeckelhuber, M., McKinnell, I., Putz, R., Christ,B. and Patel, K. (
2004
). Wnt 6 regulates the epithelialisation process of the segmental plate mesoderm leading to somite formation.
Dev. Biol.
271
,
198
-209.
Sela-Donenfeld, D. and Kalcheim, C. (
2002
). Localized BMP4-noggin interactions generate the dynamic patterning of noggin expression in somites.
Dev. Biol.
246
,
311
-328.
Stern, H. M., Brown, A. M. and Hauschka, S. D.(
1995
). Myogenesis in paraxial mesoderm: preferential induction by dorsal neural tube and by cells expressing Wnt-1.
Development
121
,
3675
-3686.
Stickney, H. L., Barresi, M. J. and Devoto, S. H.(
2000
). Somite development in zebrafish.
Dev. Dyn.
219
,
287
-303.
Sumoy, L., Kiefer, J. and Kimelman, D. (
1999
). Conservation of intracellular Wnt signaling components in dorsal-ventral axis formation in zebrafish.
Dev. Genes Evol.
209
,
48
-58.
Tajbakhsh, S., Rocancourt, D., Cossu, G. and Buckingham, M.(
1997
). Redefining the genetic hierarchies controlling skeletal myogenesis: Pax-3 and Myf-5 act upstream of MyoD.
Cell
89
,
127
-138.
Tomlin, C. J. and Axelrod, J. D. (
2007
). Biology by numbers: mathematical modelling in developmental biology.
Nat. Rev. Genet.
8
,
331
-340.
Tonegawa, A. and Takahashi, Y. (
1998
). Somitogenesis controlled by Noggin.
Dev. Biol.
202
,
172
-182.
Turing, A. M. (
1952
). The chemical basis of morphogenesis.
Philos. Trans. R. Soc. Lond. B Biol. Sci.
237
,
37
-72.
Wagner, J., Schmidt, C., Nikowits, W., Jr and Christ, B.(
2000
). Compartmentalization of the somite and myogenesis in chick embryos are influenced by wnt expression.
Dev. Biol.
228
,
86
-94.
Watanabe, Y. and Le Douarin, N. M. (
1996
). A role for BMP-4 in the development of subcutaneous cartilage.
Mech. Dev.
57
,
69
-78.
Weintraub, H., Davis, R., Tapscott, S., Thayer, M., Krause, M.,Benezra, R., Blackwell, T. K., Turner, D., Rupp, R., Hollenberg, S. et al.(
1991
). The myoD gene family: nodal point during specification of the muscle cell lineage.
Science
251
,
761
-766.