LIPIcs.CPM.2018.6.pdf
- Filesize: 0.59 MB
- 14 pages
Document
Nearest constrained circular words
Authors
-
Part of:
Volume:
29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-05-18
Cite AsGet BibTex
Guillaume Blin, Alexandre Blondin Massé, Marie Gasparoux, Sylvie Hamel, and Élise Vandomme. Nearest constrained circular words. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CPM.2018.6
https://doi.org/10.4230/LIPIcs.CPM.2018.6
Abstract
In this paper, we study circular words arising in the development of equipment using shields in brachytherapy. This equipment has physical constraints that have to be taken into consideration. From an algorithmic point of view, the problem can be formulated as follows: Given a circular word, find a constrained circular word of the same length such that the Manhattan distance between these two words is minimal. We show that we can solve this problem in pseudo polynomial time (polynomial time in practice) using dynamic programming.
Subject Classification
ACM Subject Classification
- Theory of computation → Dynamic programming
- Mathematics of computing → Combinatorics on words
- Applied computing → Bioinformatics
Keywords
- Circular constrained alignments
- Manhattan distance
- Application to brachytherapy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Horst Bunke and Urs Bühler. Applications of approximate string matching to 2d shape recognition. Pattern Recognition, 26(12):1797-1812, 1993. URL: http://dx.doi.org/10.1016/0031-3203(93)90177-X.
- Maxime Crochemore, Gabriele Fici, Robert Mercas, and Solon P. Pissis. Linear-time sequence comparison using minimal absent words & applications. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 334-346. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_25.
- Jens Gregor and Michael G. Thomason. Dynamic programming alignment of sequences representing cyclic patterns. IEEE Trans. Pattern Anal. Mach. Intell., 15(2):129-135, 1993. URL: http://dx.doi.org/10.1109/34.192484.
- Roberto Grossi, Costas S. Iliopoulos, Robert Mercas, Nadia Pisanti, Solon P. Pissis, Ahmad Retha, and Fatima Vayani. Circular sequence comparison: algorithms and applications. Algorithms for Molecular Biology, 11:12, 2016. URL: http://dx.doi.org/10.1186/s13015-016-0076-6.
- Taehyung Lee, Joong Chae Na, Heejin Park, Kunsoo Park, and Jeong Seop Sim. Finding consensus and optimal alignment of circular strings. Theor. Comput. Sci., 468:92-101, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.11.018.
-
V. I. Levenshtein. Binary codes capable of correcting insertions and reversals. Sov. Phys. Dokl., 10:707-710, 1966.
- M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. URL: http://dx.doi.org/10.1017/CBO9780511566097.
- Maurice Maes. On a cyclic string-to-string correction problem. Inf. Process. Lett., 35(2):73-78, 1990. URL: http://dx.doi.org/10.1016/0020-0190(90)90109-B.
- Andrés Marzal and Sergio Barrachina. Speeding up the computation of the edit distance for cyclic strings. In 15th International Conference on Pattern Recognition, ICPR'00, Barcelona, Spain, September 3-8, 2000., pages 2891-2894. IEEE Computer Society, 2000. URL: http://dx.doi.org/10.1109/ICPR.2000.906217.
- Ramón Alberto Mollineda, Enrique Vidal, and Francisco Casacuberta. Cyclic sequence alignments: Approximate versus optimal techniques. IJPRAI, 16(3):291-299, 2002. URL: http://dx.doi.org/10.1142/S0218001402001678.
- R. Pötter, C. Haie-Meder, E. Van Limbergen, I. Barillot, M. De Brabandere, J. Dimopoulos, I. Dumas, B. Erickson, S. Lang, A. Nulens, P. Petrow, J. Rownd, and C. Kirisits. Recommendations from gynaecological (GYN) GEC-ESTRO working group (ii): Concepts and terms in 3D image-based treatment planning in cervix cancer brachytherapy - 3D dose volume parameters and aspects of 3D image-based anatomy, radiation physics, radiobiology. Radiotherapy and Oncology, 78(1):67-77, 2006. URL: http://dx.doi.org/10.1016/j.radonc.2005.11.014.
- Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. J. ACM, 21(1):168-173, 1974. URL: http://dx.doi.org/10.1145/321796.321811.