TY - GEN

T1 - Longest common prefixes with k-mismatches and applications

AU - Alamro, Hayam

AU - Ayad, Lorraine A.K.

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

PY - 2018/1/1

Y1 - 2018/1/1

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

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

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

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

U2 - 10.1007/978-3-319-73117-9_45

DO - 10.1007/978-3-319-73117-9_45

M3 - Conference contribution

AN - SCOPUS:85041830128

SN - 9783319731162

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

SP - 636

EP - 649

BT - SOFSEM 2018

A2 - Wiedermann, Jirí

A2 - Tjoa, A Min

A2 - Biffl, Stefan

A2 - Bellatreche, Ladjel

A2 - van Leeuwen, Jan

PB - Springer Verlag

T2 - 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018

Y2 - 29 January 2018 through 2 February 2018

ER -