King's College London

Research portal

Palindromic Decompositions with Gaps and Errors

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

Michal Adamczyk, Mai Alzamel, Panagiotis Charalampopoulos, Costas Iliopoulos, Jakub Radoszewski

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
PublisherSpringer Verlag
Pages48-61
Number of pages14
Volume10304 LNCS
ISBN (Print)9783319587462
DOIs
Publication statusPublished - 2017
Event12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Russian Federation
Duration: 8 Jun 201712 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10304 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference12th International Computer Science Symposium in Russia, CSR 2017
CountryRussian Federation
CityKazan
Period8/06/201712/06/2017

King's Authors

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

View graph of relations

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