Longest common prefixes with k-mismatches and applications

Hayam Alamro, Lorraine A.K. Ayad, Panagiotis Charalampopoulos*, Costas S. Iliopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We propose a new algorithm for computing the longest prefix of each suffix of a given string of length n over a constant-sized alphabet of size σ that occurs elsewhere in the string with Hamming distance at most k. Specifically, we show that the proposed algorithm requires time O(n(σR) klog log n(log k+ log log n)) on average, where R= ⌈ (k+ 2) (log σn+ 1) ⌉, and space O(n). This improves upon the state-of-the-art average-case time complexity for the case when k= 1 [23] by a factor of log n/ log 3log n. In addition, we show how the proposed technique can be adapted and applied in order to compute the longest previous factors under the Hamming distance model within the same complexities. In terms of real-world applications, we show that our technique can be directly applied to the problem of genome mappability.

Original languageEnglish
Title of host publicationSOFSEM 2018
Subtitle of host publicationTheory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
EditorsJirí Wiedermann, A Min Tjoa, Stefan Biffl, Ladjel Bellatreche, Jan van Leeuwen
PublisherSpringer Verlag
Pages636-649
Number of pages14
ISBN (Print)9783319731162
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes
Event44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Krems, Austria
Duration: 29 Jan 20182 Feb 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10706 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
CountryAustria
CityKrems,
Period29/01/182/02/18

Fingerprint

Dive into the research topics of 'Longest common prefixes with k-mismatches and applications'. Together they form a unique fingerprint.

Cite this