Palindromic Decompositions with Gaps and Errors

TY - CHAP

T1 - Palindromic Decompositions with Gaps and Errors

AU - Adamczyk, Michal

AU - Alzamel, Mai

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas

AU - Radoszewski, Jakub

PY - 2017

Y1 - 2017

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85019261702&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-58747-9_7

DO - 10.1007/978-3-319-58747-9_7

M3 - Other chapter contribution

AN - SCOPUS:85019261702

SN - 9783319587462

VL - 10304 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 48

EP - 61

BT - Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings

PB - Springer Verlag

T2 - 12th International Computer Science Symposium in Russia, CSR 2017

Y2 - 8 June 2017 through 12 June 2017

ER -