@article{494a1cbddd84401e94ac745ec58e638e, 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. There exists an algorithm to solve this problem for k=1 requiring time O(mnlogn/loglogn) using space O(n). Here we present two new algorithms that require worst-case time O(mn) and O(nlognloglogn), respectively, and space O(n), thus greatly improving the previous result. 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=Ω(klog σn), assuming that the letters are independent and uniformly distributed random variables. Finally, we provide an experimental evaluation of our average-case algorithm demonstrating its competitiveness to the state-of-the-art implementation.", keywords = "Algorithms on strings, Hamming distance, Sequence mappability", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Jakub Radoszewski and Wing-Kin Sung", year = "2019", month = "5", day = "23", doi = "10.1016/j.tcs.2019.04.026", language = "English", journal = "Theoretical Computer Science", issn = "0304-3975", publisher = "Elsevier", }
@inbook{5528908b64004249819dac50dcda2c59, title = "Degenerate String Comparison and Applications", author = "Mai Alzamel and Ayad, {Lorraine A. K.} and Giulia Bernardini and Roberto Grossi and Iliopoulos, {Costas S.} and Nadia Pisanti and Pissis, {Solon P.} and Giovanna Rosone", year = "2018", doi = "10.4230/LIPIcs.WABI.2018.21", language = "English", isbn = "9783959770828", volume = "113", series = "Leibniz International Proceedings in Informatics (LIPIcs)", publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik", pages = "21:1--21:14", editor = "Laxmi Parida and Esko Ukkonen", booktitle = "18th International Workshop on Algorithms in Bioinformatics (WABI 2018)", }
@inbook{c21be3e905d942cb93ca15089fcc4e47, title = "How to Answer a Small Batch of RMQs or LCA Queries in Practice", author = "Mai Alzamel and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.}", year = "2018", doi = "10.1007/978-3-319-78825-8_28", language = "English", volume = "10765", series = "Lecture Notes in Computer Science", publisher = "Springer International Publishing", pages = "343--355", editor = "Ljiljana Brankovic and Joe Ryan and Smyth, {William F.}", booktitle = "Combinatorial Algorithms", }
@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 = "11", 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", }
@inbook{3dd3d839f29740c997c5e86bac917b11, title = "Efficient Computation of Palindromes in Sequences with Uncertainties", abstract = "In this work, we consider a special type of uncertain sequence called weighted string. In a weighted string every position contains a subset of the alphabet and every letter of the alphabet is associated with a probability of occurrence such that the sum of probabilities at each position equals 1. Usually a cumulative weight thresholdOpen image in new window is specified, and one considers only strings that match the weighted string with probability at least Open image in new window. We provide an O(nz)O(nz) -time and O(nz)O(nz) -space off-line algorithm, where n is the length of the weighted string and Open image in new window is the given threshold, to compute a smallest maximal palindromic factorization of a weighted string. This factorization has applications in hairpin structure prediction in a set of closely-related DNA or RNA sequences. Along the way, we provide an O(nz)O(nz) -time and O(nz)O(nz) -space off-line algorithm to compute maximal palindromes in weighted strings.", author = "Mai Alzamel and Jia Gao and Iliopoulos, {Costas S.} and Chang Liu and Pissis, {Solon P.}", year = "2017", month = "8", day = "2", doi = "10.1007/978-3-319-65172-9_52", language = "English", isbn = "978-3-319-65171-2", volume = "744", pages = "620--629", editor = "Giacomo Boracchi and Lazaros Iliadis and Chrisina Jayne and Aristidis Likas", booktitle = "Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings", publisher = "Springer International Publishing Switzerland", }
@inbook{58931e5cfeba44559177d4562c33b452, title = "Efficient Identification of k-Closed Strings", abstract = "A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying whether or not a given string of length n over an integer alphabet is k-closed and additionally specifying the border resulting in the string being k-closed. Specifically, we present an O(kn)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.", author = "Hayam Alamro and Mai Alzamel and Iliopoulos, {Costas S.} and Pissis, {Solon P.} and Steven Watts and Wing-Kin Sung", year = "2017", month = "8", day = "2", doi = "10.1007/978-3-319-65172-9_49", language = "English", isbn = "978-3-319-65171-2", volume = "744", pages = "583--595", editor = "Giacomo Boracchi and Lazaros Iliadis and Chrisina Jayne and Aristidis Likas", booktitle = "Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings", publisher = "Springer International Publishing Switzerland", }