Faster Algorithms for 1-Mappability of a Sequence

Mai Alzamel; Panagiotis Charalampopoulos; Costas Iliopoulos; Solon 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 Iliopoulos, Solon Pissis, Jakub Radoszewski^*, Wing Kin Sung

^*Corresponding author for this work

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

5 Citations (Scopus)

122 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 language	English
Title of host publication	Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
Publisher	Springer Verlag
Pages	109-121
Number of pages	13
Volume	10628 LNCS
ISBN (Electronic)	978-3-319-71147-8
ISBN (Print)	9783319711461
DOIs	https://doi.org/10.1007/978-3-319-71147-8_8
Publication status	E-pub ahead of print - 16 Nov 2017
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)	03029743
ISSN (Electronic)	16113349

Conference

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

Access to Document

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

Faster algorithms for 1-mappability_ALZAMEL_Firstonline16November2017_GREEN AAMAccepted author manuscript, 501 KB

Cite this

Alzamel, M., Charalampopoulos, P., Iliopoulos, C., Pissis, S., Radoszewski, J., & Sung, W. K. (2017). Faster Algorithms for 1-Mappability of a Sequence. In Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings (Vol. 10628 LNCS, 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. Advance online publication. https://doi.org/10.1007/978-3-319-71147-8_8

Alzamel, Mai ; Charalampopoulos, Panagiotis ; Iliopoulos, Costas et al. / Faster Algorithms for 1-Mappability of a Sequence. Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. Vol. 10628 LNCS Springer Verlag, 2017. pp. 109-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{61452460f3ae4171ba16189d85b9c78e,

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 Costas Iliopoulos and Solon Pissis and Jakub Radoszewski and Sung, {Wing Kin}",

year = "2017",

month = nov,

day = "16",

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

language = "English",

isbn = "9783319711461",

volume = "10628 LNCS",

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

publisher = "Springer Verlag",

pages = "109--121",

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, C , Pissis, S, Radoszewski, J & Sung, WK 2017, Faster Algorithms for 1-Mappability of a Sequence. in Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. vol. 10628 LNCS, 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/2017. 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 et al.
Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. Vol. 10628 LNCS 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 › Other chapter contribution › peer-review

TY - CHAP

T1 - Faster Algorithms for 1-Mappability of a Sequence

AU - Alzamel, Mai

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas

AU - Pissis, Solon

AU - Radoszewski, Jakub

AU - Sung, Wing Kin

PY - 2017/11/16

Y1 - 2017/11/16

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 - http://www.scopus.com/inward/record.url?scp=85038216754&partnerID=8YFLogxK

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

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

M3 - Other chapter contribution

AN - SCOPUS:85038216754

SN - 9783319711461

VL - 10628 LNCS

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

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 C , Pissis S, Radoszewski J, Sung WK. Faster Algorithms for 1-Mappability of a Sequence. In Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings. Vol. 10628 LNCS. Springer Verlag. 2017. p. 109-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2017 Nov 16. doi: 10.1007/978-3-319-71147-8_8

Faster Algorithms for 1-Mappability of a Sequence

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this