@inbook{ccf1e5d7c5e04ce49b405377c39b7b57, title = "Palindromic Decompositions with Gaps and Errors", abstract = "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).", author = "Michal Adamczyk and Mai Alzamel and Panagiotis Charalampopoulos and Costas Iliopoulos and Jakub Radoszewski", year = "2017", doi = "10.1007/978-3-319-58747-9_7", language = "English", isbn = "9783319587462", volume = "10304 LNCS", series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)", publisher = "Springer Verlag", pages = "48--61", booktitle = "Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings", address = "Germany", note = "12th International Computer Science Symposium in Russia, CSR 2017 ; Conference date: 08-06-2017 Through 12-06-2017", }