King's College London

Research portal

Faster Algorithms for 1-Mappability of a Sequence

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
PublisherSpringer Verlag
Number of pages13
Volume10628 LNCS
ISBN (Electronic)978-3-319-71147-8
ISBN (Print)9783319711461
E-pub ahead of print16 Nov 2017
Event11th International Conference on Combinatorial Optimization and Applications, COCOA 2017 - Shanghai, China
Duration: 16 Dec 201718 Dec 2017

Publication series

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


Conference11th International Conference on Combinatorial Optimization and Applications, COCOA 2017


King's Authors


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

Download statistics

No data available

View graph of relations

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