<p>We incorporate the interaction among extra-cellular matrix (ECM) and cells into P systems. ECM supports cells mechanically, decides cells’ fates, and becomes the base of a differentiated tissue. We propose an assembly P system which contains ECM as a kind of objects and rules which describe interactions among ECM and cell objects. The system assembles a structure from an initial multiset of ECM objects and a number of cells, which may be produced by cell division. The resulting assembly may be interpreted according to the goal of the system. Here we introduce, as an example, an assembly P system which solves the satisfiability problem of Boolean formula (SAT) and the Hamiltonian cycle problem (Hamiltonian). We emphasize that a single system, not uniquely constructed from the size of the instance or semi-uniquely constructed from the instance, can solve any instance of SAT or Hamiltonian by assembling a structure which corresponds to a possible solution. It should be noted, however, the system is nondeterministic, uses priorities among rules, objects with parameters, and conditions over the parameters. We also show that, for every linear bounded automaton <i>A</i>, there is an assembly P system such that the system simulates computations of <i>A</i>.</p>