Faster algorithms for 1-mappability of a sequence

Mai Alzamel; Panagiotis Charalampopoulos; Costas S. Iliopoulos; Solon P. Pissis; Jakub Radoszewski; Wing Kin Sung

doi:10.1007/978-3-319-71147-8_8

Faster algorithms for 1-mappability of a sequence

Mai Alzamel
, Panagiotis Charalampopoulos
, Costas S. Iliopoulos
, Solon P. Pissis
, Jakub Radoszewski^*
, Wing Kin Sung

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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 language	English
Title of host publication	Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
Editors	Xiaofeng Gao, Hongwei Du, Meng Han
Publisher	Springer Verlag
Pages	109-121
Number of pages	13
ISBN (Print)	9783319711461
DOIs	https://doi.org/10.1007/978-3-319-71147-8_8
Publication status	Published - 1 Jan 2017
Externally published	Yes
Event	11th International Conference on Combinatorial Optimization and Applications, COCOA 2017 - Shanghai, China Duration: 16 Dec 2017 → 18 Dec 2017

Publication series

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

Conference

Conference	11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
Country/Territory	China
City	Shanghai
Period	16/12/17 → 18/12/17

Funding

M. Alzamel and C.S. Iliopoulos—Partially supported by the Onassis Foundation. J. Radoszewski—Supported by the “Algorithms for text processing with errors and uncertainties” project carried out within the HOMING programme of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund.

Access to Document

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

Persistent URL (handle)

Persistent link

Cite this

Alzamel, M., Charalampopoulos, P., Iliopoulos, C. S., Pissis, S. P., Radoszewski, J., & Sung, W. K. (2017). Faster algorithms for 1-mappability of a sequence. In X. Gao, H. Du, & M. Han (Eds.), Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings (pp. 109-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10628 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-71147-8_8

Alzamel, Mai ; Charalampopoulos, Panagiotis ; Iliopoulos, Costas S. et al. / Faster algorithms for 1-mappability of a sequence. Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. editor / Xiaofeng Gao ; Hongwei Du ; Meng Han. Springer Verlag, 2017. pp. 109-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a7a2aa6a970348caa7f9fdb0de2e9970,

title = "Faster algorithms for 1-mappability of a sequence",

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

author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, \{Costas S.\} and Pissis, \{Solon P.\} and Jakub Radoszewski and Sung, \{Wing Kin\}",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-71147-8\_8",

language = "English",

isbn = "9783319711461",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "109--121",

editor = "Xiaofeng Gao and Hongwei Du and Meng Han",

booktitle = "Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings",

address = "Germany",

note = "11th International Conference on Combinatorial Optimization and Applications, COCOA 2017 ; Conference date: 16-12-2017 Through 18-12-2017",

}

Alzamel, M, Charalampopoulos, P, Iliopoulos, CS, Pissis, SP, Radoszewski, J & Sung, WK 2017, Faster algorithms for 1-mappability of a sequence. in X Gao, H Du & M Han (eds), Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10628 LNCS, Springer Verlag, pp. 109-121, 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017, Shanghai, China, 16/12/17. https://doi.org/10.1007/978-3-319-71147-8_8

Faster algorithms for 1-mappability of a sequence. / Alzamel, Mai; Charalampopoulos, Panagiotis; Iliopoulos, Costas S. et al.
Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. ed. / Xiaofeng Gao; Hongwei Du; Meng Han. Springer Verlag, 2017. p. 109-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10628 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Faster algorithms for 1-mappability of a sequence

AU - Alzamel, Mai

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

AU - Sung, Wing Kin

PY - 2017/1/1

Y1 - 2017/1/1

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 - https://www.scopus.com/pages/publications/85038216754

UR - https://www.scopus.com/pages/publications/85038216754#tab=citedBy

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

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

M3 - Conference contribution

AN - SCOPUS:85038216754

SN - 9783319711461

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

A2 - Gao, Xiaofeng

A2 - Du, Hongwei

A2 - Han, Meng

PB - Springer Verlag

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

Y2 - 16 December 2017 through 18 December 2017

ER -

Alzamel M, Charalampopoulos P, Iliopoulos CS, Pissis SP, Radoszewski J, Sung WK. Faster algorithms for 1-mappability of a sequence. In Gao X, Du H, Han M, editors, Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. Springer Verlag. 2017. p. 109-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-71147-8_8

Faster algorithms for 1-mappability of a sequence

Abstract

Publication series

Conference

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this