Moral Lineage Tracing

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

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 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.

Related collections

Most cited references 7

Record: found
Abstract: found
Article: not found

Imaging in systems biology.

Sean G. Megason, Scott Fraser (2007)

Most systems biology approaches involve determining the structure of biological circuits using genomewide "-omic" analyses. Yet imaging offers the unique advantage of watching biological circuits function over time at single-cell resolution in the intact animal. Here, we discuss the power of integrating imaging tools with more conventional -omic approaches to analyze the biological circuits of microorganisms, plants, and animals.

0 comments Cited 59 times – based on 0 reviews      Review now

Bookmark

Record: found
Abstract: found
Article: not found

Global linking of cell tracks using the Viterbi algorithm.

Penney M Gilbert, Joakim Jaldén, Helen Blau … (2015)

Automated tracking of living cells in microscopy image sequences is an important and challenging problem. With this application in mind, we propose a global track linking algorithm, which links cell outlines generated by a segmentation algorithm into tracks. The algorithm adds tracks to the image sequence one at a time, in a way which uses information from the complete image sequence in every linking decision. This is achieved by finding the tracks which give the largest possible increases to a probabilistically motivated scoring function, using the Viterbi algorithm. We also present a novel way to alter previously created tracks when new tracks are created, thus mitigating the effects of error propagation. The algorithm can handle mitosis, apoptosis, and migration in and out of the imaged area, and can also deal with false positives, missed detections, and clusters of jointly segmented cells. The algorithm performance is demonstrated on two challenging datasets acquired using bright-field microscopy, but in principle, the algorithm can be used with any cell type and any imaging technique, presuming there is a suitable segmentation algorithm.

0 comments Cited 45 times – based on 0 reviews      Review now

Bookmark

Record: found
Abstract: found
Article: not found

Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis.

Dirk Padfield, Jens Rittscher, Badrinath Roysam (2011)

A growing number of screening applications require the automated monitoring of cell populations in a high-throughput, high-content environment. These applications depend on accurate cell tracking of individual cells that display various behaviors including mitosis, merging, rapid movement, and entering and leaving the field of view. Many approaches to cell tracking have been developed in the past, but most are quite complex, require extensive post-processing, and are parameter intensive. To overcome such issues, we present a general, consistent, and extensible tracking approach that explicitly models cell behaviors in a graph-theoretic framework. We introduce a way of extending the standard minimum-cost flow algorithm to account for mitosis and merging events through a coupling operation on particular edges. We then show how the resulting graph can be efficiently solved using algorithms such as linear programming to choose the edges of the graph that observe the constraints while leading to the lowest overall cost. This tracking algorithm relies on accurate denoising and segmentation steps for which we use a wavelet-based approach that is able to accurately segment cells even in images with very low contrast-to-noise. In addition, the framework is able to measure and correct for microscope defocusing and stage shift. We applied the algorithms on nearly 6000 images of 400,000 cells representing 32,000 tracks taken from five separate datasets, each composed of multiple wells. Our algorithm was able to segment and track cells and detect different cell behaviors with an accuracy of over 99%. This overall framework enables accurate quantitative analysis of cell events and provides a valuable tool for high-throughput biological studies. Copyright © 2010 Elsevier B.V. All rights reserved.