Moral Lineage Tracing
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, for every image in a sequence, a decomposition into cells (segmentation) and, across images, a lineage forest of cells (tracing). In this ILP, path-cut inequalities enforce the morality of lineages, i.e., the constraint that cells do not merge. 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 weighted edit distance to lineage forests traced by humans.
Results
Below are traced lineages of cells form the N2DL-HeLa and Flywing Epithelium datasets
Code and Data
We base our implementation on the freely-available header-only graph library. The following code contains the latest (at the moment of publication) snapshot of the library and a bunch of command line tools to create, lift, solve, and visualize solutions of multicut problems. The project is organized using cmake and depends on hdf5 library. As an LP solver we used Gurobi, for which one can freely obtain an acedemic license. Please, supply the path to your Gurobi installation, if it is not in the default location, by setting GUROBI_ROOT_DIR for cmake.
In order to facilitate further research of the problem, we provide all the test data that has been used in the paper.
The format of the data files is decribed in the corresponding readme file.
For example, to perfrom tracking of the small N2DL-HeLa dataset, you can do:
./track-ilp -n data/N2DL-HeLa/small/nodes.csv -e data/N2DL-HeLa/small/edges.csv -s solution -T 5 -B 5 -F 2>/dev/null
And visualize the results:
./draw -n data/N2DL-HeLa/small/nodes.csv -e data/N2DL-HeLa/small/edges.csv -s solution-fragment-edge-labels.txt -o vis.h5
This will create file vis.h5, which you can display using freely available OpenGL viewer.
To find a fractional LP solution you can do:
./track-lp -n data/N2DL-HeLa/small/nodes.csv -e data/N2DL-HeLa/small/edges.csv -s solution -T 5 -B 5 -F
It is impossible to display it, because the solution is not integer, in general.
All the paths above assume that the executables are in the root directory of the project.
validate-solution can be used to check whether a solution (for example, obtained by another solver) violates lineage cut inequalities defined in the paper.