Palindromic Decompositions with Gaps and Errors

Michal Adamczyk, Mai Alzamel, Panagiotis Charalampopoulos, Costas Iliopoulos, Jakub Radoszewski*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

5 Citations (Scopus)


Identifying palindromes in sequences has been an interest-ing line of research in combinatorics on words and also in computational biology, after the discovery of the relation of palindromes in the DNA sequence with the HIV virus. Effcient algorithms for the factorization of sequences into palindromes and maximal palindromes have been devised in recent years. We extend these studies by allowing gaps in decomposi-tions and errors in palindromes, and also imposing a lower bound to the length of acceptable palindromes. We first present an algorithm for obtaining a palindromic decompo-sition of a string of length n with the minimal total gap length in time O(n log n · g) and space O(n · g), where g is the number of allowed gaps in the decomposition. We then consider a decomposition of the string in maximal δ-palindromes (i.e. palindromes with δ errors under the edit or Hamming distance) and g allowed gaps. We present an algorithm to obtain such a decomposition with the minimal total gap length in time O(n · (g + δ)) and space O(n · g).

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
PublisherSpringer Verlag
Number of pages14
Volume10304 LNCS
ISBN (Print)9783319587462
Publication statusPublished - 2017
Event12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Russian Federation
Duration: 8 Jun 201712 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10304 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference12th International Computer Science Symposium in Russia, CSR 2017
Country/TerritoryRussian Federation


Dive into the research topics of 'Palindromic Decompositions with Gaps and Errors'. Together they form a unique fingerprint.

Cite this