Inference algorithms for developmental systems with cell lineages (Q1090280)

Lineage patterns play an important role in the control of development (especially in genetically controlled plants). Thus the authors investigate an algorithmic procedure for inferring discrete generative lineage rules from observed developmental sequences of tree structures. The inference algorithms presented in the paper are worked out under the assumption that observations are taken in equidistant time-points and that the underlying model is an interactionless deterministic L system. Since in such a case an inference procedure can always be carried out, the authors pay attention to schemes satisfying some biologically motivated reliability constraints. They also tuch upon the problem of computational complexity of the proposed inference algorithms. They find some upper bounds, but, in general, the problem still remains open (as e.g. the question whether the exponential bound could be removed).