# Moral Lineage Tracing

arXiv: https://arxiv.org/abs/1511.05512 · HTML: https://mlsanity.com/paper/1511.05512/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2015.

## Built on by (most cited first, 5 of 5)

- [Graph Neural Network for Cell Tracking in Microscopy Videos](https://mlsanity.com/paper/2202.04731/) (2022)
- [Trackastra: Transformer-based cell tracking for live-cell microscopy](https://mlsanity.com/paper/2405.15700/) (2024)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Large-Scale Multi-Hypotheses Cell Tracking Using Ultrametric Contours Maps](https://mlsanity.com/paper/2308.04526/) (2023)
- [Accurate Tracking of Arabidopsis Root Cortex Cell Nuclei in 3D Time-Lapse Microscopy Images Based on Genetic Algorithm](https://mlsanity.com/paper/2504.12676/) (2025)

## Abstract (arXiv)

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.