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 -