Circular constrained alignment; Manhattan distanc; Application to brachytherapy
Abstract :
[en] 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 be-
tween these two words is minimal. We show that we can solve this problem in pseudo polynomial
time (polynomial time in practice) using dynamic programming.
Disciplines :
Mathematics
Author, co-author :
Blin, Guillaume; Université de Bordeaux > Laboratoire Bordelais de Recherche en Informatique (LaBRI)
Blondin Massé, Alexandre; Université du Québec à Montréal > Laboratoire de Combinatoire et d'Informatique Mathématique
Gasparoux, Marie; Université de Bordeaux > Laboratoire Bordelais de Recherche en Informatique (LaBRI)
Hamel, Sylvie; Université de Montréal - UdeM
Vandomme, Elise ; Université de Liège - ULiège > Département de mathématique > Probabilités et statistique mathématique
Language :
English
Title :
Nearest constrained circular words
Publication date :
2018
Event name :
29th Annual Symposium on Combinatorial Pattern Matching (CPM)
Event place :
Qingdao, China
Event date :
July 2-4, 2018
Audience :
International
Journal title :
Leibniz International Proceedings in Informatics
ISSN :
1868-8969
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Germany
Horst Bunke and Urs Bühler. Applications of approximate string matching to 2d shape recognition. Pattern Recognition, 26(12):1797-1812, 1993. doi: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. doi: 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. doi: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. doi: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. doi: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. doi:10.1017/CBO9780511566097.
Maurice Maes. On a cyclic string-to-string correction problem. Inf. Process. Lett., 35(2):73-78, 1990. doi: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. doi: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. doi: 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. doi: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. doi:10.1145/321796.321811.
