Robust cell tracking in epithelial tissues through identification of maximum common subgraphs

Jochen Kursawe, Rémi Bardenet, Jeremiah J. Zartman, Ruth E. Baker, Alexander G. Fletcher

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
5 Downloads (Pure)


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 the Drosophila embryonic epidermis and compare cell-cell rearrangements to previous studies in other tissues. Our implementation is open source and generally applicable to epithelial tissues.
Original languageEnglish
Article number20160725
Number of pages13
JournalJournal of the Royal Society Interface
Issue number124
Early online date1 Nov 2016
Publication statusPublished - Nov 2016


  • Animals
  • Cell movement/physiology
  • Cell tracking
  • Drosophila melanogaster
  • Ectoderm/cytology
  • Epithelial cells/cytology
  • Models, biological


Dive into the research topics of 'Robust cell tracking in epithelial tissues through identification of maximum common subgraphs'. Together they form a unique fingerprint.

Cite this