Abstract

Lineage tracing, the tracking of living cells as they moveand divide, is a central problem in biological image analysis. Solutions, called lineage forests, are key to understandinghow the structure of multicellular organisms emerges. We propose an integer linear program (ILP) whose feasible solu-tions define, for every image in a sequence, a decomposition into cells (segmentation) and, across images, a lineage forestof cells (tracing). In this ILP, path-cut inequalities enforce the morality of lineages, i.e., the constraint that cells do nomerge. To find feasible solutions of this NP-hard problem, with certified bounds to the global optimum, we define efficient separation procedures and apply these as part of a branch-and-cut algorithm. To show the effectiveness of this approach, we analyze feasible solutions for real microscopy data in terms of bounds and run-time, and by their weightededit distance to lineage forests traced by humans.