TY - JOUR
T1 - Faster algorithms for 1-mappability of a sequence
AU - Alzamel, Mai
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Sung, Wing-Kin
PY - 2019/5/23
Y1 - 2019/5/23
N2 - 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.
AB - 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.
KW - Algorithms on strings
KW - Hamming distance
KW - Sequence mappability
UR - http://www.scopus.com/inward/record.url?scp=85067179715&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2019.04.026
DO - 10.1016/j.tcs.2019.04.026
M3 - Article
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
TY - CHAP
T1 - A Brief Overview of Dead-Zone Pattern Matching Algorithms
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
AU - Watson, Richard T.
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.
AB - Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.
UR - http://www.scopus.com/inward/record.url?scp=85065921354&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_18
DO - 10.1007/978-3-030-19909-8_18
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 208
EP - 218
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Pimenidis, Elias
A2 - Iliadis, Lazaros
A2 - Maglogiannis, Ilias
A2 - MacIntyre, John
PB - Springer
ER -
TY - CHAP
T1 - On the Cyclic Regularities of Strings
AU - Ajala, Oluwole Ifeanyi
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Gao, Jia
AU - Iliopoulos, Costas
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.
AB - Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.
KW - Covers
KW - Cyclic regularities
KW - Periods
UR - http://www.scopus.com/inward/record.url?scp=85065922538&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_19
DO - 10.1007/978-3-030-19909-8_19
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 219
EP - 224
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Maglogiannis, Ilias
A2 - Iliadis, Lazaros
A2 - MacIntyre, John
A2 - Pimenidis, Elias
PB - Springer
ER -