Document Open Access Logo

Nearest constrained circular words

Authors Guillaume Blin, Alexandre Blondin Massé, Marie Gasparoux, Sylvie Hamel, Élise Vandomme

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2018.6.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Guillaume Blin
  • LaBRI, Université de Bordeaux, CNRS UMR 5800, Talence, France
Alexandre Blondin Massé
  • Dép. d'informatique, Université du Québec à Montréal, QC, Canada
Marie Gasparoux
  • LaBRI, Université de Bordeaux, CNRS UMR 5800, Talence, France, Dép. d'informatique et de recherche opérationnelle, Université de Montréal, QC, Canada
Sylvie Hamel
  • Dép. d'informatique et de recherche opérationnelle, Université de Montréal, QC, Canada
Élise Vandomme
  • LaCIM, Université du Québec à Montréal, QC, Canada

Funding

  • Blondin Massé, Alexandre: Suppported by the Individual Discovery Grant RGPIN-417269-2013 from National Sciences and Engineering Research Council of Canada (NSERC).
  • Gasparoux, Marie: Partially supported by PoPRA project funded by Conseil Régional d'Aquitaine and European FEDER and IdEx Bordeaux.
  • Hamel, Sylvie: Supported by the Individual Discovery Grant RGPIN-2016-04576 from National Sciences and Engineering Research Council of Canada (NSERC).

Supplementary Materials

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. V. I. Levenshtein. Binary codes capable of correcting insertions and reversals. Sov. Phys. Dokl., 10:707-710, 1966. Google Scholar
  7. M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. URL: http://dx.doi.org/10.1017/CBO9780511566097.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact