Cargando…

An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans

The nematode Caenorhabditis elegans (C. elegans) is a model organism used frequently in developmental biology and neurobiology [White, (1986), Sulston, (1983), Chisholm, (2016) and Rapti, (2020)]. The C. elegans embryo can be used for cell tracking studies to understand how cell movement drives the...

Descripción completa

Detalles Bibliográficos
Autores principales: Lauziere, Andrew, Christensen, Ryan, Shroff, Hari, Balan, Radu
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2022
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9707761/
https://www.ncbi.nlm.nih.gov/pubmed/36445888
http://dx.doi.org/10.1371/journal.pone.0277343
_version_ 1784840767768887296
author Lauziere, Andrew
Christensen, Ryan
Shroff, Hari
Balan, Radu
author_facet Lauziere, Andrew
Christensen, Ryan
Shroff, Hari
Balan, Radu
author_sort Lauziere, Andrew
collection PubMed
description The nematode Caenorhabditis elegans (C. elegans) is a model organism used frequently in developmental biology and neurobiology [White, (1986), Sulston, (1983), Chisholm, (2016) and Rapti, (2020)]. The C. elegans embryo can be used for cell tracking studies to understand how cell movement drives the development of specific embryonic tissues. Analyses in late-stage development are complicated by bouts of rapid twitching motions which invalidate traditional cell tracking approaches. However, the embryo possesses a small set of cells which may be identified, thereby defining the coiled embryo’s posture [Christensen, 2015]. The posture serves as a frame of reference, facilitating cell tracking even in the presence of twitching. Posture identification is nevertheless challenging due to the complete repositioning of the embryo between sampled images. Current approaches to posture identification rely on time-consuming manual efforts by trained users which limits the efficiency of subsequent cell tracking. Here, we cast posture identification as a point-set matching task in which coordinates of seam cell nuclei are identified to jointly recover the posture. Most point-set matching methods comprise coherent point transformations that use low order objective functions [Zhou, (2016) and Zhang, (2019)]. Hypergraphs, an extension of traditional graphs, allow more intricate modeling of relationships between objects, yet existing hypergraphical point-set matching methods are limited to heuristic algorithms which do not easily scale to handle higher degree hypergraphs [Duchenne, (2010), Chertok, (2010) and Lee, (2011)]. Our algorithm, Exact Hypergraph Matching (EHGM), adapts the classical branch-and-bound paradigm to dynamically identify a globally optimal correspondence between point-sets under an arbitrarily intricate hypergraphical model. EHGM with hypergraphical models inspired by C. elegans embryo shape identified posture more accurately (56%) than established point-set matching methods (27%), correctly identifying twice as many sampled postures as a leading graphical approach. Posterior region seeding empowered EHGM to correctly identify 78% of postures while reducing runtime, demonstrating the efficacy of the method on a cutting-edge problem in developmental biology.
format Online
Article
Text
id pubmed-9707761
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-97077612022-11-30 An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans Lauziere, Andrew Christensen, Ryan Shroff, Hari Balan, Radu PLoS One Research Article The nematode Caenorhabditis elegans (C. elegans) is a model organism used frequently in developmental biology and neurobiology [White, (1986), Sulston, (1983), Chisholm, (2016) and Rapti, (2020)]. The C. elegans embryo can be used for cell tracking studies to understand how cell movement drives the development of specific embryonic tissues. Analyses in late-stage development are complicated by bouts of rapid twitching motions which invalidate traditional cell tracking approaches. However, the embryo possesses a small set of cells which may be identified, thereby defining the coiled embryo’s posture [Christensen, 2015]. The posture serves as a frame of reference, facilitating cell tracking even in the presence of twitching. Posture identification is nevertheless challenging due to the complete repositioning of the embryo between sampled images. Current approaches to posture identification rely on time-consuming manual efforts by trained users which limits the efficiency of subsequent cell tracking. Here, we cast posture identification as a point-set matching task in which coordinates of seam cell nuclei are identified to jointly recover the posture. Most point-set matching methods comprise coherent point transformations that use low order objective functions [Zhou, (2016) and Zhang, (2019)]. Hypergraphs, an extension of traditional graphs, allow more intricate modeling of relationships between objects, yet existing hypergraphical point-set matching methods are limited to heuristic algorithms which do not easily scale to handle higher degree hypergraphs [Duchenne, (2010), Chertok, (2010) and Lee, (2011)]. Our algorithm, Exact Hypergraph Matching (EHGM), adapts the classical branch-and-bound paradigm to dynamically identify a globally optimal correspondence between point-sets under an arbitrarily intricate hypergraphical model. EHGM with hypergraphical models inspired by C. elegans embryo shape identified posture more accurately (56%) than established point-set matching methods (27%), correctly identifying twice as many sampled postures as a leading graphical approach. Posterior region seeding empowered EHGM to correctly identify 78% of postures while reducing runtime, demonstrating the efficacy of the method on a cutting-edge problem in developmental biology. Public Library of Science 2022-11-29 /pmc/articles/PMC9707761/ /pubmed/36445888 http://dx.doi.org/10.1371/journal.pone.0277343 Text en https://creativecommons.org/publicdomain/zero/1.0/This is an open access article, free of all copyright, and may be freely reproduced, distributed, transmitted, modified, built upon, or otherwise used by anyone for any lawful purpose. The work is made available under the Creative Commons CC0 (https://creativecommons.org/publicdomain/zero/1.0/) public domain dedication.
spellingShingle Research Article
Lauziere, Andrew
Christensen, Ryan
Shroff, Hari
Balan, Radu
An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title_full An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title_fullStr An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title_full_unstemmed An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title_short An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans
title_sort exact hypergraph matching algorithm for posture identification in embryonic c. elegans
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9707761/
https://www.ncbi.nlm.nih.gov/pubmed/36445888
http://dx.doi.org/10.1371/journal.pone.0277343
work_keys_str_mv AT lauziereandrew anexacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT christensenryan anexacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT shroffhari anexacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT balanradu anexacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT lauziereandrew exacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT christensenryan exacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT shroffhari exacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans
AT balanradu exacthypergraphmatchingalgorithmforpostureidentificationinembryoniccelegans