Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution

**Palindromic Decompositions with Gaps and Errors.** / Adamczyk, Michal; Alzamel, Mai; Charalampopoulos, Panagiotis; Iliopoulos, Costas; Radoszewski, Jakub.

Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution

Adamczyk, M, Alzamel, M, Charalampopoulos, P, Iliopoulos, C & Radoszewski, J 2017, Palindromic Decompositions with Gaps and Errors. in *Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings.* vol. 10304 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10304 LNCS, Springer Verlag, pp. 48-61, 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russian Federation, 8/06/2017. https://doi.org/10.1007/978-3-319-58747-9_7

Adamczyk, M., Alzamel, M., Charalampopoulos, P., Iliopoulos, C., & Radoszewski, J. (2017). Palindromic Decompositions with Gaps and Errors. In *Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings *(Vol. 10304 LNCS, pp. 48-61). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10304 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-58747-9_7

Adamczyk M, Alzamel M, Charalampopoulos P, Iliopoulos C, Radoszewski J. Palindromic Decompositions with Gaps and Errors. In Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Vol. 10304 LNCS. Springer Verlag. 2017. p. 48-61. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-58747-9_7

@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",

}

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

ER -

King's College London - Homepage

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454