Robust cell tracking in epithelial tissues through identification of maximum common subgraphs.
Tracking of cells in live-imaging microscopy videos of epithelial sheets is a powerful tool for investigating fundamental processes in embryonic development. Characterizing cell growth, proliferation, intercalation and apoptosis in epithelia helps us to understand how morphogenetic processes such as tissue invagination and extension are locally regulated and controlled. Accurate cell tracking requires correctly resolving cells entering or leaving the field of view between frames, cell neighbour exchanges, cell removals and cell divisions. However, current tracking methods for epithelial sheets are not robust to large morphogenetic deformations and require significant manual interventions. Here, we present a novel algorithm for epithelial cell tracking, exploiting the graph-theoretic concept of a 'maximum common subgraph' to track cells between frames of a video. Our algorithm does not require the adjustment of tissue-specific parameters, and scales in sub-quadratic time with tissue size. It does not rely on precise positional information, permitting large cell movements between frames and enabling tracking in datasets acquired at low temporal resolution due to experimental constraints such as phototoxicity. To demonstrate the method, we perform tracking on theDrosophilaembryonic epidermis and compare cell-cell rearrangements to previous studies in other tissues. Our implementation is open source and generally applicable to epithelial tissues.
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK kursawe@maths.ox.ac.uk.
Jochen
0000-0002-0314-9623
J
Kursawe
CNRS and CRIStAL, Université de Lille, 59651 Villeneuve d'Ascq, France.
Rémi
R
Bardenet
Department of Chemical and Biomolecular Engineering, University of Notre Dame, 205D McCourtney Hall of Molecular Science and Engineering, Notre Dame, IN 46556, USA.
Jeremiah J
JJ
Zartman
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK.
Ruth E
RE
Baker
School of Mathematics and Statistics, University of Sheffield, Hicks Building, Hounsfield Road, Sheffield S3 7RH, UK a.g.fletcher@sheffield.ac.uk.|Bateson Centre, University of Sheffield, Sheffield S10 2TN, UK.
Alexander G
0000-0003-0525-4336
AG
Fletcher
D000818:Animals; D002465:Cell Movement / Q000502:physiology*; D058948:Cell Tracking; D004331:Drosophila melanogaster; D004475:Ectoderm / Q000166:cytology / Q000196:embryology*; D004847:Epithelial Cells / Q000166:cytology / Q000378:metabolism*; D008954:Models, Biological
cell tracking; epithelial sheets; maximum common subgraph; planar graphs