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...
Autores principales: | , , , |
---|---|
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 |