TY - CHAP

T1 - Faster Algorithms for 1-Mappability of a Sequence

AU - Alzamel, Mai

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas

AU - Pissis, Solon

AU - Radoszewski, Jakub

AU - Sung, Wing Kin

PY - 2017/11/16

Y1 - 2017/11/16

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

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

UR - http://www.scopus.com/inward/record.url?scp=85038216754&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-71147-8_8

DO - 10.1007/978-3-319-71147-8_8

M3 - Other chapter contribution

AN - SCOPUS:85038216754

SN - 9783319711461

VL - 10628 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 121

BT - Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings

PB - Springer Verlag

T2 - 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017

Y2 - 16 December 2017 through 18 December 2017

ER -