King's College London

Research portal

Palindromic Decompositions with Gaps and Errors

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Standard

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

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); Vol. 10304 LNCS).

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Harvard

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

APA

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

Vancouver

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

Author

Adamczyk, Michal ; Alzamel, Mai ; Charalampopoulos, Panagiotis ; Iliopoulos, Costas ; Radoszewski, Jakub. / Palindromic Decompositions with Gaps and Errors. Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings. Vol. 10304 LNCS Springer Verlag, 2017. pp. 48-61 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Bibtex Download

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

}

RIS (suitable for import to EndNote) Download

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 -

View graph of relations

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