Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/CVPR.2016.638 | 2016 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR) |
Field | DocType | Volume |
Integer,Edit distance,Computer science,Segmentation,Global optimum,Algorithm,Theoretical computer science,Linear programming,Artificial intelligence,Merge (version control),Machine learning,Tracing | Journal | abs/1511.05512 |
Issue | ISSN | Citations |
1 | 1063-6919 | 0 |
PageRank | References | Authors |
0.34 | 21 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Florian Jug | 1 | 17 | 2.01 |
evgeny levinkov | 2 | 17 | 2.05 |
Corinna Blasse | 3 | 28 | 2.78 |
Eugene Myers | 4 | 3164 | 496.92 |
Bjoern Andres | 5 | 457 | 19.80 |