Document Open Access Logo

Shape Decomposition Algorithms for Laser Capture Microdissection

Authors Leonie Selbach, Tobias Kowalski, Klaus Gerwert, Maike Buchin, Axel Mosig

PDF
Thumbnail PDF

File

LIPIcs.WABI.2020.13.pdf
  • Filesize: 1.09 MB
  • 17 pages

Document Identifiers

Author Details

Leonie Selbach
  • Department of Computer Science and Center for Protein Diagnostics, Ruhr University Bochum, Germany
Tobias Kowalski
  • Department of Biophysics and Center for Protein Diagnostics, Ruhr University Bochum, Germany
Klaus Gerwert
  • Department of Biophysics and Center for Protein Diagnostics, Ruhr University Bochum, Germany
Maike Buchin
  • Department of Computer Science, Ruhr University Bochum, Germany
Axel Mosig
  • Department of Biophysics and Center for Protein Diagnostics, Ruhr University Bochum, Germany

Cite As Get BibTex

Leonie Selbach, Tobias Kowalski, Klaus Gerwert, Maike Buchin, and Axel Mosig. Shape Decomposition Algorithms for Laser Capture Microdissection. In 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 172, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.WABI.2020.13

Abstract

In the context of biomarker discovery and molecular characterization of diseases, laser capture microdissection is a highly effective approach to extract disease-specific regions from complex, heterogeneous tissue samples. These regions have to be decomposed into feasible fragments as they have to satisfy certain constraints in size and morphology for the extraction to be successful. We model this problem of constrained shape decomposition as the computation of optimal feasible decompositions of simple polygons. We use a skeleton-based approach and present an algorithmic framework that allows the implementation of various feasibility criteria as well as optimization goals. Motivated by our application, we consider different constraints and examine the resulting fragmentations. Furthermore, we apply our method to lung tissue samples and show its advantages in comparison to a heuristic decomposition approach.

Subject Classification

ACM Subject Classification
  • Applied computing → Bioinformatics
  • Theory of computation → Computational geometry
  • Theory of computation → Dynamic programming
Keywords
  • Laser capture microdissection
  • shape decomposition
  • skeletonization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sander P. A. Alewijnse, Kevin Buchin, Maike Buchin, Andrea Kölzsch, Helmut Kruckenberg, and Michel A. Westenberg. A framework for trajectory segmentation by stable criteria. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’14, page 351–360, New York, NY, USA, 2014. Association for Computing Machinery. Google Scholar
  2. Xiang Bai, Longin Jan Latecki, and Wen-Yu Liu. Skeleton pruning by contour partitioning with discrete curve evolution. IEEE transactions on pattern analysis and machine intelligence, 29(3), 2007. Google Scholar
  3. Harry Blum. A transformation for extracting new descriptors of shape. Models for Perception of Speech and Visual Forms, 1967, pages 362-380, 1967. Google Scholar
  4. Harry Blum. Biological shape and visual science (part i). Journal of theoretical Biology, 38(2):205-287, 1973. Google Scholar
  5. Maike Buchin, Axel Mosig, and Leonie Selbach. Skeleton-based decomposition of simple polygons. In Abstracts of 35th European Workshop on Computational Geometry, 2019. URL: http://www.eurocg2019.uu.nl/papers/3.pdf.
  6. Maike Buchin and Leonie Selbach. Decomposition and partition algorithms for tissue dissection. In Computational Geometry: Young Researchers Forum, pages 24-27, 2020. URL: http://www.computational-geometry.org/YRF/cgyrf2020.pdf.
  7. Maike Buchin and Leonie Selbach. A polynomial-time partitioning algorithm for weighted cactus graphs, 2020. URL: http://arxiv.org/abs/2001.00204.
  8. Hyeong In Choi, Sung Woo Choi, and Hwan Pyo Moon. Mathematical theory of medial axis transform. pacific journal of mathematics, 181(1):57-88, 1997. Google Scholar
  9. Soma Datta, Lavina Malhotra, Ryan Dickerson, Scott Chaffee, Chandan K Sen, and Sashwati Roy. Laser capture microdissection: Big data from small samples. Histology and histopathology, 30(11):1255, 2015. Google Scholar
  10. Gabriella Sanniti di Baja and Edouard Thiel. (3, 4)-weighted skeleton decomposition for pattern representation and description. Pattern Recognition, 27(8):1039-1049, 1994. Google Scholar
  11. Klaus Drechsler and Cristina Oyarzun Laura. Hierarchical decomposition of vessel skeletons for graph creation and feature extraction. In Bioinformatics and Biomedicine (BIBM), 2010 IEEE International Conference on, pages 456-461. IEEE, 2010. Google Scholar
  12. Bastien Durix, Sylvie Chambon, Kathryn Leonard, Jean-Luc Mari, and Géraldine Morin. The propagated skeleton: A robust detail-preserving approach. In International Conference on Discrete Geometry for Computer Imagery, pages 343-354. Springer, 2019. Google Scholar
  13. Bastien Durix, Géraldine Morin, Sylvie Chambon, Jean-Luc Mari, and Kathryn Leonard. One-step compact skeletonization. In Eurographics (Short Papers), pages 21-24, 2019. Google Scholar
  14. Michael R Emmert-Buck, Robert F Bonner, Paul D Smith, Rodrigo F Chuaqui, Zhengping Zhuang, Seth R Goldstein, Rhonda A Weiss, and Lance A Liotta. Laser capture microdissection. Science, 274(5289):998-1001, 1996. Google Scholar
  15. Frederik Großerueschkamp, Thilo Bracht, Hanna C Diehl, Claus Kuepper, Maike Ahrens, Angela Kallenbach-Thieltges, Axel Mosig, Martin Eisenacher, Katrin Marcus, Thomas Behrens, et al. Spatial and molecular resolution of diffuse malignant mesothelioma heterogeneity by integrating label-free ftir imaging, laser capture microdissection and proteomics. Scientific reports, 7(1):1-12, 2017. Google Scholar
  16. J Mark Keil. Polygon decomposition. Handbook of Computational Geometry, 2:491-518, 2000. Google Scholar
  17. Yutaka Kondo, Yae Kanai, Michiie Sakamoto, Masashi Mizokami, Ryuzo Ueda, and Setsuo Hirohashi. Genetic instability and aberrant dna methylation in chronic hepatitis and cirrhosis—a comprehensive study of loss of heterozygosity and microsatellite instability at 39 loci and dna hypermethylation on 8 cpg islands in microdissected specimens from patients with hepatocellular carcinoma. Hepatology, 32(5):970-979, 2000. Google Scholar
  18. Kathryn Leonard, Geraldine Morin, Stefanie Hahmann, and Axel Carlier. A 2d shape structure for decomposition and part similarity. In Pattern Recognition (ICPR), 2016 23rd International Conference on, pages 3216-3221. IEEE, 2016. Google Scholar
  19. Martha L. Narro, Fan Yang, Robert Kraft, Carola Wenk, Alon Efrat, and Linda L. Restifo. Neuronmetrics: Software for semi-automated processing of cultured neuron images. Brain Research, 1138:57-75, 2007. Google Scholar
  20. Chin-Ann J Ong, Qiu Xuan Tan, Hui Jun Lim, Nicholas B Shannon, Weng Khong Lim, Josephine Hendrikson, Wai Har Ng, Joey WS Tan, Kelvin KN Koh, Seettha D Wasudevan, et al. An optimised protocol harnessing laser capture microdissection for transcriptomic analysis on matched primary and metastatic colorectal tumours. Scientific Reports, 10(1):1-12, 2020. Google Scholar
  21. Nikos Papanelopoulos, Yannis Avrithis, and Stefanos Kollias. Revisiting the medial axis for planar shape decomposition. Computer Vision and Image Understanding, 179:66-78, 2019. Google Scholar
  22. Dennie Reniers and Alexandru Telea. Skeleton-based hierarchical shape segmentation. In Shape Modeling and Applications, 2007. SMI'07. IEEE International Conference on, pages 179-188. IEEE, 2007. Google Scholar
  23. Punam K Saha, Gunilla Borgefors, and Gabriella Sanniti di Baja. A survey on skeletonization algorithms and their applications. Pattern Recognition Letters, 76:3-12, 2016. Google Scholar
  24. Martin R Schmuck, Thomas Temme, Katharina Dach, Denise de Boer, Marta Barenys, Farina Bendt, Axel Mosig, and Ellen Fritsche. Omnisphero: a high-content image analysis (hca) approach for phenotypic developmental neurotoxicity (dnt) screenings of organoid neurosphere cultures in vitro. Archives of toxicology, 91(4), 2017. Google Scholar
  25. Mirela Tănase and Remco C Veltkamp. Polygon decomposition based on the straight line skeleton. In Geometry, Morphology, and Computational Imaging, pages 247-268. Springer, 2003. Google Scholar
  26. Quoc Dang Vu, Simon Graham, Tahsin Kurc, Minh Nguyen Nhat To, Muhammad Shaban, Talha Qaiser, Navid Alemi Koohbanani, Syed Ali Khurram, Jayashree Kalpathy-Cramer, Tianhao Zhao, et al. Methods for segmentation and classification of digital microscopy tissue images. Frontiers in bioengineering and biotechnology, 7, 2019. Google Scholar
  27. Chaofeng Wang, Cai-Ping Gui, Hai-Kuan Liu, Dong Zhang, and Axel Mosig. An image skeletonization-based tool for pollen tube morphology analysis and phenotyping f. Journal of integrative plant biology, 55(2):131-141, 2013. Google Scholar
  28. Shidan Wang, Ruichen Rong, Donghan M Yang, Junya Fujimoto, Shirley Yan, Ling Cai, Lin Yang, Danni Luo, Carmen Behrens, Edwin R Parra, et al. Computational staining of pathology images to study the tumor microenvironment in lung cancer. Cancer Research, 2020. Google Scholar
  29. Franz-Erich Wolter. Cut locus and medial axis in global shape interrogation and representation, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact