IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0277343.html
   My bibliography  Save this article

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

Author

Listed:
  • Andrew Lauziere
  • Ryan Christensen
  • Hari Shroff
  • Radu Balan

Abstract

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.

Suggested Citation

  • Andrew Lauziere & Ryan Christensen & Hari Shroff & Radu Balan, 2022. "An Exact Hypergraph Matching algorithm for posture identification in embryonic C. elegans," PLOS ONE, Public Library of Science, vol. 17(11), pages 1-21, November.
  • Handle: RePEc:plo:pone00:0277343
    DOI: 10.1371/journal.pone.0277343
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0277343
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0277343&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0277343?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John D. C. Little & Katta G. Murty & Dura W. Sweeney & Caroline Karel, 1963. "An Algorithm for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 11(6), pages 972-989, December.
    2. Jianfeng Cao & Guoye Guan & Vincy Wing Sze Ho & Ming-Kin Wong & Lu-Yan Chan & Chao Tang & Zhongying Zhao & Hong Yan, 2020. "Establishment of a morphological atlas of the Caenorhabditis elegans embryo using deep-learning-based 4D segmentation," Nature Communications, Nature, vol. 11(1), pages 1-14, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. José Berenguel & L. Casado & I. García & Eligius Hendrix, 2013. "On estimating workload in interval branch-and-bound global optimization algorithms," Journal of Global Optimization, Springer, vol. 56(3), pages 821-844, July.
    2. N. Kazazakis & C. S. Adjiman, 2018. "Arbitrarily tight $$\alpha $$ α BB underestimators of general non-linear functions over sub-optimal domains," Journal of Global Optimization, Springer, vol. 71(4), pages 815-844, August.
    3. Joaquín Antonio Pacheco Bonrostro, 1995. "Problemas de rutas con carga y descarga en sistemas lifo: soluciones exactas," Estudios de Economia Aplicada, Estudios de Economia Aplicada, vol. 3, pages 69-86, Junio.
    4. José Luis Verdegay & Edmundo Vergara-Moreno, 2003. "Solving NP-Hard problems by using fuzzy sets-based heuristics," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 13(4), pages 167-183.
    5. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(3), pages 545-560, September.
    6. Bogna MRÓWCZYŃSKA, 2015. "Multicriteria vehicle routing problem solved by artificial immune system," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 10(3), pages 141-152, September.
    7. Min Guo & Yicong Wu & Chad M. Hobson & Yijun Su & Shuhao Qian & Eric Krueger & Ryan Christensen & Grant Kroeschell & Johnny Bui & Matthew Chaw & Lixia Zhang & Jiamin Liu & Xuekai Hou & Xiaofei Han & Z, 2025. "Deep learning-based aberration compensation improves contrast and resolution in fluorescence microscopy," Nature Communications, Nature, vol. 16(1), pages 1-19, December.
    8. Michael Windham & J. Hutchinson & Shizuhiko Nishisato & Ludovic Lebart & George Furnas & Richard Dubes & Frank Critchley & A. Gordon & Fionn Murtagh & Ulf Bockenholt & Philip Hopke & Daniel Wartenberg, 1988. "Book reviews," Journal of Classification, Springer;The Classification Society, vol. 5(1), pages 105-154, March.
    9. Nikolakopoulos, Athanassios & Sarimveis, Haralambos, 2007. "A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1911-1929, March.
    10. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    11. Zhang Yang & Jiacheng Li & Lei Li, 2020. "Time-Dependent Theme Park Routing Problem by Partheno-Genetic Algorithm," Mathematics, MDPI, vol. 8(12), pages 1-20, December.
    12. Lawrence Hubert & Frank Baker, 1978. "Applications of combinatorial programming to data analysis: The traveling salesman and related problems," Psychometrika, Springer;The Psychometric Society, vol. 43(1), pages 81-91, March.
    13. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
    14. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    15. Ohashi, Kazumasa, 1999. "Dynamic process planning system for a machining center in an FMS environment," International Journal of Production Economics, Elsevier, vol. 60(1), pages 457-464, April.
    16. Luminiţa Nicolescu & Cristina Galalae & Alexandru Voicu, 2013. "Solving a Supply Chain Management Problem to Near Optimality Using Ant Colony Optimization, in an International Context," The AMFITEATRU ECONOMIC journal, Academy of Economic Studies - Bucharest, Romania, vol. 15(33), pages 8-26, February.
    17. Ashayeri, J. & Selen, W., 2007. "A planning and scheduling model for onsertion in printed circuit board assembly," European Journal of Operational Research, Elsevier, vol. 183(2), pages 909-925, December.
    18. Belhoul, Lyes, 2014. "Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée," Economics Thesis from University Paris Dauphine, Paris Dauphine University, number 123456789/14672 edited by Vanderpooten, Daniel.
    19. Linus Schrage & Kevin Cunningham, 2007. "Broadening the integer programming audience, the LINDO perspective," Annals of Operations Research, Springer, vol. 149(1), pages 177-183, February.
    20. Roodbergen, Kees Jan & de Koster, Rene, 2001. "Routing order pickers in a warehouse with a middle aisle," European Journal of Operational Research, Elsevier, vol. 133(1), pages 32-43, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0277343. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.