Faster Algorithms for 1-Mappability of a Sequence

Mai Alzamel, Panagiotis Charalampopoulos, Costas Iliopoulos, Solon Pissis, Jakub Radoszewski*, Wing Kin Sung

*Corresponding author for this work

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

5 Citations (Scopus)
115 Downloads (Pure)

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

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
PublisherSpringer Verlag
Pages109-121
Number of pages13
Volume10628 LNCS
ISBN (Electronic)978-3-319-71147-8
ISBN (Print)9783319711461
DOIs
Publication statusE-pub ahead of print - 16 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

Conference

Conference11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
Country/TerritoryChina
CityShanghai
Period16/12/201718/12/2017

Fingerprint

Dive into the research topics of 'Faster Algorithms for 1-Mappability of a Sequence'. Together they form a unique fingerprint.

Cite this