Combining sea urchin embryo cell lineages by error-tolerant graph matching

Obtaining the complete cell lineage tree of an embryo's development is a very appealing and ambitious goal, but fortunately recent developments both in optical imaging and digital image processing are bringing it closer. However, when imaging the embryos (sea urchin embryos for this work) with high enough spatial resolution and short enough time-step to make cell segmentation and tracking possible, it is currently not possible to image the specimen throughout its all embryogenesis. For this reason it is interesting to explore how cell lineage trees extracted from two different embryos of the same species and imaged for overlapping periods of time can be concatenated, resulting in a single lineage tree covering both embryos' development time frames. To achieve this we used an error-tolerant graph matching strategy by selecting a time point at which both lineage trees overlap, and representing the information about each embryo at that time point as a graph in which nodes stand for cells and edges for neighborhood relationships among cells. The expected output of the graph matching algorithm is the minimal-cost correspondence between cells of both specimens, allowing us to perform the lineage combination.