Moral Lineage Tracing
This work addresses lineage tracing for biological researchers, offering a novel method to enforce morality constraints, but it is incremental as it builds on existing ILP formulations with specific improvements.
The paper tackles the problem of lineage tracing in biological image analysis by proposing an integer linear program (ILP) that enforces morality constraints to prevent cell merging, using path-cut inequalities and a branch-and-cut algorithm. It demonstrates effectiveness on real microscopy data with results including certified bounds to the global optimum and weighted edit distance to human-traced ground truth.
Lineage tracing, the tracking of living cells as they move and divide, is a central problem in biological image analysis. Solutions, called lineage forests, are key to understanding how the structure of multicellular organisms emerges. We propose an integer linear program (ILP) whose feasible solutions define a decomposition of each image in a sequence into cells (segmentation), and a lineage forest of cells across images (tracing). Unlike previous formulations, we do not constrain the set of decompositions, except by contracting pixels to superpixels. The main challenge, as we show, is to enforce the morality of lineages, i.e., the constraint that cells do not merge. To enforce morality, we introduce path-cut inequalities. To find feasible solutions of the NP-hard ILP, with certified bounds to the global optimum, we define efficient separation procedures and apply these as part of a branch-and-cut algorithm. We show the effectiveness of this approach by analyzing feasible solutions for real microscopy data in terms of bounds and run-time, and by their weighted edit distance to ground truth lineage forests traced by humans.