2019-05-23

# Faster algorithms for 1-mappability of a sequence

## Publication

### Publication

*
Theoretical Computer Science
,
Volume 812
p. 2-
12
*

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.Additional Metadata | |
---|---|

, , | |

doi.org/10.1016/j.tcs.2019.04.026 | |

Theoretical Computer Science | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |

Alzamel, M., Charalampopoulos, P., Iliopoulos, C., Pissis, S., Radoszewski, J., & Sung, W.-K. (2019). Faster algorithms for 1-mappability of a sequence. Theoretical Computer Science, 812, 2–12. doi:10.1016/j.tcs.2019.04.026 |