@article{494a1cbddd84401e94ac745ec58e638e, title = "Faster algorithms for 1-mappability of a sequence", abstract = "In the k-mappability problem, we are given a string x of length n and integers m and k, and we are asked to count, for each length-m factor y of x, the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where k=1. There exists an algorithm to solve this problem for k=1 requiring time O(mnlogn/loglogn) using space O(n). Here we present two new algorithms that require worst-case time O(mn) and O(nlognloglogn), respectively, and space O(n), thus greatly improving the previous result. Moreover, we present another algorithm that requires average-case time and space O(n) for integer alphabets of size σ if m=Ω(log σn). Notably, we show that this algorithm is generalizable for arbitrary k, requiring average-case time O(kn) and space O(n) if m=Ω(klog σn), assuming that the letters are independent and uniformly distributed random variables. Finally, we provide an experimental evaluation of our average-case algorithm demonstrating its competitiveness to the state-of-the-art implementation.", keywords = "Algorithms on strings, Hamming distance, Sequence mappability", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Jakub Radoszewski and Wing-Kin Sung", year = "2019", month = "5", day = "23", doi = "10.1016/j.tcs.2019.04.026", language = "English", journal = "Theoretical Computer Science", issn = "0304-3975", publisher = "Elsevier", }
@conference{3479fb4029c94581acc80dee8a15894e, title = "Efficient Computation of Sequence Mappability", author = "Alzamel, {Mai Abdulaziz M} and Panagiotis Charalampopoulos and Costas Iliopoulos and Tomasz Kociumaka and Solon Pissis and Jakub Radoszewski and Juliusz Straszynski", year = "2018", doi = "10.1007{\%}2F978-3-030-00479-8_2", language = "English", pages = "12--26", note = "25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018", }
@inbook{c21be3e905d942cb93ca15089fcc4e47, title = "How to Answer a Small Batch of RMQs or LCA Queries in Practice", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.}", year = "2018", doi = "10.1007/978-3-319-78825-8_28", language = "English", volume = "10765", series = "Lecture Notes in Computer Science", publisher = "Springer International Publishing", pages = "343--355", editor = "Ljiljana Brankovic and Joe Ryan and Smyth, {William F.}", booktitle = "Combinatorial Algorithms", }
@inbook{61452460f3ae4171ba16189d85b9c78e, title = "Faster Algorithms for 1-Mappability of a Sequence", abstract = "In the k-mappability problem, we are given a string x of length n and integers m and k, and we are asked to count, for each length-m factor y of x, the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where k= 1. The fastest known algorithm for k= 1 requires time O(mnlog n/ log log n) and space O(n). We present two new algorithms that require worst-case time O(mn) and O(nlog nlog log n), respectively, and space O(n), thus greatly improving the state of the art. Moreover, we present another algorithm that requires average-case time and space O(n) for integer alphabets of size σ if m = Ω(log σn). Notably, we show that this algorithm is generalizable for arbitrary k, requiring average-case time O(kn) and space O(n) if m = Ω(k logσn).", author = "Mai Alzamel and Panagiotis Charalampopoulos and Costas Iliopoulos and Solon Pissis and Jakub Radoszewski and Sung, {Wing Kin}", year = "2017", month = "11", day = "16", doi = "10.1007/978-3-319-71147-8_8", language = "English", isbn = "9783319711461", volume = "10628 LNCS", series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)", publisher = "Springer Verlag", pages = "109--121", booktitle = "Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings", address = "Germany", }
@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", }