{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T21:06:00Z","timestamp":1761253560395,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009591","name":"Ministerium f\u00fcr Innovation, Wissenschaft und Forschung des Landes Nordrhein-Westfalen","doi-asserted-by":"publisher","award":["111.08.03.05-133974"],"award-info":[{"award-number":["111.08.03.05-133974"]}],"id":[{"id":"10.13039\/501100009591","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006254","name":"Ruhr-Universit\u00e4t Bochum","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006254","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>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. For the extraction to be successful, these regions have to satisfy certain constraints in size and shape and thus have to be decomposed into feasible fragments.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>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. We evaluate our algorithm on lung tissue samples in comparison to a heuristic decomposition approach. Our method achieved a success rate of over 95% in the microdissection and tissue yield was increased by 10\u201330%.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>We present a novel approach for constrained shape decomposition by demonstrating its advantages for the application in the microdissection of tissue samples. In comparison to the previous decomposition approach, the proposed method considerably increases the amount of successfully dissected tissue.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s13015-021-00193-6","type":"journal-article","created":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T10:03:12Z","timestamp":1625738592000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Shape decomposition algorithms for laser capture microdissection"],"prefix":"10.1186","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6401-7157","authenticated-orcid":false,"given":"Leonie","family":"Selbach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Kowalski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Gerwert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maike","family":"Buchin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Axel","family":"Mosig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"issue":"5289","key":"193_CR1","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1126\/science.274.5289.998","volume":"274","author":"MR Emmert-Buck","year":"1996","unstructured":"Emmert-Buck MR, Bonner RF, Smith PD, Chuaqui RF, Zhuang Z, Goldstein SR, Weiss RA, Liotta LA. Laser capture microdissection. Science. 1996;274(5289):998\u20131001.","journal-title":"Science"},{"issue":"1","key":"193_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/srep44829","volume":"7","author":"F Gro\u00dferueschkamp","year":"2017","unstructured":"Gro\u00dferueschkamp F, Bracht T, Diehl HC, Kuepper C, Ahrens M, Kallenbach-Thieltges A, Mosig A, Eisenacher M, Marcus K, Behrens T, et al. Spatial and molecular resolution of diffuse malignant mesothelioma heterogeneity by integrating label-free ftir imaging, laser capture microdissection and proteomics. Sci Rep. 2017;7(1):1\u201312.","journal-title":"Sci Rep"},{"issue":"5","key":"193_CR3","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1053\/jhep.2000.19797","volume":"32","author":"Y Kondo","year":"2000","unstructured":"Kondo Y, Kanai Y, Sakamoto M, Mizokami M, Ueda R, Hirohashi S. 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. 2000;32(5):970\u20139.","journal-title":"Hepatology"},{"issue":"11","key":"193_CR4","first-page":"1255","volume":"30","author":"S Datta","year":"2015","unstructured":"Datta S, Malhotra L, Dickerson R, Chaffee S, Sen CK, Roy S. Laser capture microdissection: Big data from small samples. Histol Histopathol. 2015;30(11):1255.","journal-title":"Histol Histopathol"},{"issue":"1","key":"193_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-019-56847-4","volume":"10","author":"C-AJ Ong","year":"2020","unstructured":"Ong C-AJ, Tan QX, Lim HJ, Shannon NB, Lim WK, Hendrikson J, Ng WH, Tan JW, Koh KK, Wasudevan SD, et al. An optimised protocol harnessing laser capture microdissection for transcriptomic analysis on matched primary and metastatic colorectal tumours. Sci Rep. 2020;10(1):1\u201312.","journal-title":"Sci Rep"},{"key":"193_CR6","doi-asserted-by":"publisher","first-page":"188","DOI":"10.3389\/fbioe.2019.00053","volume":"7","author":"QD Vu","year":"2019","unstructured":"Vu QD, Graham S, Kurc T, To MNN, Shaban M, Qaiser T, Koohbanani NA, Khurram SA, Kalpathy-Cramer J, Zhao T, et al. Methods for segmentation and classification of digital microscopy tissue images. Front Bioeng Biotechnol. 2019;7:188.","journal-title":"Front Bioeng Biotechnol"},{"key":"193_CR7","first-page":"548","volume":"7","author":"S Wang","year":"2020","unstructured":"Wang S, Rong R, Yang DM, Fujimoto J, Yan S, Cai L, Yang L, Luo D, Behrens C, Parra ER, et al. Computational staining of pathology images to study the tumor microenvironment in lung cancer. Cancer Res. 2020;7:548.","journal-title":"Cancer Res"},{"key":"193_CR8","doi-asserted-by":"crossref","unstructured":"Selbach L, Kowalski T, Gerwert K, Buchin M, Mosig A. Shape Decomposition Algorithms for Laser Capture Microdissection. In: 20th International workshop on algorithms in bioinformatics (WABI 2020). Leibniz international proceedings in informatics (LIPIcs), 2020, p 13:1\u201313:17.","DOI":"10.1186\/s13015-021-00193-6"},{"key":"193_CR9","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/B978-044482537-7\/50012-7","volume-title":"Polygon decomposition. Handbook of computational geometry","author":"JM Keil","year":"2000","unstructured":"Keil JM. Polygon decomposition. Handbook of computational geometry. Berlin: Springer; 2000. p. 491\u2013518."},{"key":"193_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.patrec.2015.04.006","volume":"76","author":"PK Saha","year":"2016","unstructured":"Saha PK, Borgefors G, di Baja GS. A survey on skeletonization algorithms and their applications. Pattern Recogn Lett. 2016;76:3\u201312.","journal-title":"Pattern Recogn Lett"},{"key":"193_CR11","doi-asserted-by":"crossref","unstructured":"Drechsler K, Laura CO. Hierarchical decomposition of vessel skeletons for graph creation and feature extraction. In: 2010 IEEE international conference On Bioinformatics and biomedicine (BIBM). 2010, p 456\u201361.","DOI":"10.1109\/BIBM.2010.5706609"},{"issue":"2","key":"193_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1111\/j.1744-7909.2012.01184.x","volume":"55","author":"C Wang","year":"2013","unstructured":"Wang C, Gui C-P, Liu H-K, Zhang D, Mosig A. An image skeletonization-based tool for pollen tube morphology analysis and phenotyping F. J Integr Plant Biol. 2013;55(2):131\u201341.","journal-title":"J Integr Plant Biol"},{"key":"193_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.brainres.2006.10.094","volume":"1138","author":"ML Narro","year":"2007","unstructured":"Narro ML, Yang F, Kraft R, Wenk C, Efrat A, Restifo LL. Neuronmetrics: Software for semi-automated processing of cultured neuron images. Brain Res. 2007;1138:57\u201375.","journal-title":"Brain Res"},{"key":"193_CR14","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/s00204-016-1852-2","volume":"91","author":"MR Schmuck","year":"2017","unstructured":"Schmuck MR, Temme T, Dach K, de Boer D, Barenys M, Bendt F, Mosig A, Fritsche E. Omnisphero: a high-content image analysis (HCA) approach for phenotypic developmental neurotoxicity (DNT) screenings of organoid neurosphere cultures in vitro. Archiv Toxicol. 2017;91:4.","journal-title":"Archiv Toxicol"},{"key":"193_CR15","doi-asserted-by":"crossref","unstructured":"Reniers D, Telea A. Skeleton-based hierarchical shape segmentation. In: SMI\u201907. IEEE international conference on shape modeling and applications, 2007, p 179\u2013188.","DOI":"10.1109\/SMI.2007.33"},{"key":"193_CR16","doi-asserted-by":"crossref","unstructured":"Leonard K, Morin G, Hahmann S, Carlier A. A 2d shape structure for decomposition and part similarity. In: 2016 23rd international conference on pattern recognition (ICPR). IEEE. 2016, p 3216\u20133221","DOI":"10.1109\/ICPR.2016.7900130"},{"key":"193_CR17","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.cviu.2018.10.007","volume":"179","author":"N Papanelopoulos","year":"2019","unstructured":"Papanelopoulos N, Avrithis Y, Kollias S. Revisiting the medial axis for planar shape decomposition. Comput Vision Image Understand. 2019;179:66\u201378.","journal-title":"Comput Vision Image Understand"},{"issue":"8","key":"193_CR18","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1016\/0031-3203(94)90143-0","volume":"27","author":"GS di Baja","year":"1994","unstructured":"di Baja GS, Thiel E. (3, 4)-weighted skeleton decomposition for pattern representation and description. Pattern Recogn. 1994;27(8):1039\u201349.","journal-title":"Pattern Recogn"},{"key":"193_CR19","series-title":"Geometry morphology, and computational imaging","first-page":"247","volume-title":"Polygon decomposition based on the straight line skeleton","author":"M T\u0103nase","year":"2003","unstructured":"T\u0103nase M, Veltkamp RC. Polygon decomposition based on the straight line skeleton. Geometry morphology, and computational imaging. Berlin: Springer; 2003. p. 247\u201368."},{"key":"193_CR20","first-page":"362","volume":"1967","author":"H Blum","year":"1967","unstructured":"Blum H. A transformation for extracting new descriptors of shape. Models Percep Speech Visual Forms. 1967;1967:362\u201380.","journal-title":"Models Percep Speech Visual Forms"},{"issue":"2","key":"193_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-5193(73)90175-6","volume":"38","author":"H Blum","year":"1973","unstructured":"Blum H. Biological shape and visual science (part I). J Theor Biol. 1973;38(2):205\u201387.","journal-title":"J Theor Biol"},{"issue":"1","key":"193_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.2140\/pjm.1997.181.57","volume":"181","author":"H.I Choi","year":"1997","unstructured":"Choi H.I, Choi S.W, Moon H.P. Mathematical theory of medial axis transform. Pac J Math. 1997;181(1):57\u201388.","journal-title":"Pac J Math"},{"key":"193_CR23","volume-title":"Cut locus and medial axis in global shape interrogation and representation","author":"F-E Wolter","year":"1993","unstructured":"Wolter F-E. Cut locus and medial axis in global shape interrogation and representation. Sea Grant College Program: Massachusetts Institute of Technology; 1993."},{"issue":"2","key":"193_CR24","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1006\/cviu.1997.0598","volume":"69","author":"D Shaked","year":"1998","unstructured":"Shaked D, Bruckstein AM. Pruning medial axes. Comput Vision Image Understand. 1998;69(2):156\u201369.","journal-title":"Comput Vision Image Understand"},{"issue":"4","key":"193_CR25","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.gmod.2005.01.002","volume":"67","author":"F Chazal","year":"2005","unstructured":"Chazal F, Lieutier A. The \u201c$$\\lambda$$-medial axis\u2019\u2019. Graph Models. 2005;67(4):304\u201331.","journal-title":"Graph Models"},{"key":"193_CR26","doi-asserted-by":"crossref","unstructured":"Sud A, Foskey M, Manocha D. Homotopy-preserving medial axis simplification. In: Proceedings of the 2005 ACM symposium on solid and physical modeling. 2005, p 39\u201350","DOI":"10.1145\/1060244.1060250"},{"key":"193_CR27","doi-asserted-by":"crossref","unstructured":"Durix B, Chambon S, Leonard K, Mari J.-L, Morin G. The propagated skeleton: a robust detail-preserving approach. In: International conference on discrete geometry for computer imagery. Berlin: Springer; 2019, p 343\u2013354","DOI":"10.1007\/978-3-030-14085-4_27"},{"key":"193_CR28","first-page":"21","volume":"5","author":"B Durix","year":"2019","unstructured":"Durix B, Morin G, Chambon S, Mari J-L, Leonard K. One-step compact skeletonization. Eurographics. 2019;5:21\u20134.","journal-title":"Eurographics"},{"key":"193_CR29","doi-asserted-by":"crossref","unstructured":"Bai X, Latecki LJ, Liu W-Y. Skeleton pruning by contour partitioning with discrete curve evolution. IEEE transactions on pattern analysis and machine intelligence. 2007;29:3.","DOI":"10.1109\/TPAMI.2007.59"},{"key":"193_CR30","doi-asserted-by":"crossref","unstructured":"Bai X, Latecki L.J. Discrete skeleton evolution. In: International workshop on energy minimization methods in computer vision and pattern recognition. Springer; 2007, p 362\u2013374.","DOI":"10.1007\/978-3-540-74198-5_28"},{"key":"193_CR31","unstructured":"Buchin M, Mosig A, Selbach L. Skeleton-based decomposition of simple polygons. In: Abstracts of 35th European workshop on computational geometry. 2019."},{"issue":"4","key":"193_CR32","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0925-7721(99)00059-0","volume":"15","author":"A Efrat","year":"2000","unstructured":"Efrat A, Katz MJ, Nielsen F, Sharir M. Dynamic data structures for fat objects and their applications. Comput Geomet. 2000;15(4):215\u201327.","journal-title":"Comput Geomet"},{"issue":"1","key":"193_CR33","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.comgeo.2004.01.004","volume":"28","author":"M Damian","year":"2004","unstructured":"Damian M. Exact and approximation algorithms for computing optimal fat decompositions. Comput Geomet. 2004;28(1):19\u201327.","journal-title":"Comput Geomet"},{"key":"193_CR34","doi-asserted-by":"publisher","first-page":"2159","DOI":"10.1016\/j.phpro.2012.02.317","volume":"24","author":"W Sui","year":"2012","unstructured":"Sui W, Zhang D. Four methods for roundness evaluation. Phys Proc. 2012;24:2159\u201364.","journal-title":"Phys Proc"},{"key":"193_CR35","doi-asserted-by":"crossref","unstructured":"Alewijnse S.P.A, Buchin K, Buchin M, K\u00f6lzsch A, Kruckenberg H, Westenberg M.A. A framework for trajectory segmentation by stable criteria. In: Proceedings of the 22nd ACM SIGSPATIAL international conference on advances in geographic information systems. SIGSPATIAL \u201914. 2014, p 351\u2013360","DOI":"10.1145\/2666310.2666415"},{"key":"193_CR36","unstructured":"Buchin M, Selbach L. Decomposition and partition algorithms for tissue dissection. In: Computational geometry: young researchers forum. 2020, p 24\u201327"},{"key":"193_CR37","unstructured":"Buchin M, Selbach L. Partitioning algorithms for weighted cactus graphs, 2020;.arXiv:2001.00204v2"},{"key":"193_CR38","unstructured":"Cacciola F. A CGAL implementation of the straight skeleton of a simple 2D polygon with holes. In: 2nd CGAL user workshop. 2004, p 1"},{"issue":"11","key":"193_CR39","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1002\/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B","volume":"30","author":"A Fabri","year":"2000","unstructured":"Fabri A, Giezeman G.-J, Kettner L, Schirra S, Sch\u00f6nherr S. On the design of CGAL a computational geometry algorithms library. Softw Pract Exp. 2000;30(11):1167\u2013202.","journal-title":"Softw Pract Exp"},{"issue":"9","key":"193_CR40","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1016\/j.patrec.2010.09.002","volume":"32","author":"J Chaussard","year":"2011","unstructured":"Chaussard J, Couprie M, Talbot H. Robust skeletonization using the discrete $$\\lambda$$-medial axis. Pattern Recogn Lett. 2011;32(9):1384\u201394.","journal-title":"Pattern Recogn Lett"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00193-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00193-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00193-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T09:43:28Z","timestamp":1672739008000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00193-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,8]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["193"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00193-6","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2021,7,8]]},"assertion":[{"value":"3 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"15"}}