@inproceedings{3e0d268a3b974a5ab48030d3cc3ac92e, title = "Quasi-Linear-Time Algorithm for Longest Common Circular Factor", abstract = "We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings S and T of length at most n, we are to compute the longest factor of S whose cyclic shift occurs as a factor of T. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in O(nlog 4 n) time using O(nlog 2 n) space.", keywords = "Circular pattern matching, Internal pattern matching, Intersection of hyperrectangles, Longest common factor", author = "Mai Alzamel and Maxime Crochemore and Iliopoulos, {Costas S.} and Tomasz Kociumaka and Jakub Radoszewski and Wojciech Rytter and Juliusz Straszynski and Tomasz Walen and Wiktor Zuba", year = "2019", month = "6", day = "6", doi = "10.4230/LIPIcs.CPM.2019.25", language = "English", volume = "128", pages = "25:1–25:14", editor = "Nadia Pisanti and Pissis, {Solon P.}", booktitle = "30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019", publisher = "LIPIcs", }
@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{61e2e43714f941739c99b1b1f3642418, title = "A Brief Overview of Dead-Zone Pattern Matching Algorithms", abstract = "Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.", author = "Alshammary, {Miznah Hizam} and Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos and Watson, {Richard T.} and Bruce Watson", year = "2019", month = "5", day = "15", doi = "10.1007/978-3-030-19909-8_18", language = "English", isbn = "9783030199081", volume = "560", series = "IFIP Advances in Information and Communication Technology", publisher = "Springer", pages = "208--218", editor = "Elias Pimenidis and Lazaros Iliadis and Ilias Maglogiannis and John MacIntyre", booktitle = "Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops", }
@inbook{11a5ee11428646a9ac241349e1d75394, title = "On the Cyclic Regularities of Strings", abstract = "Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.", keywords = "Covers, Cyclic regularities, Periods", author = "Ajala, {Oluwole Ifeanyi} and Alshammary, {Miznah Hizam} and Alzamel, {Mai Abdulaziz M} and Jia Gao and Costas Iliopoulos and Jakub Radoszewski and Wojciech Rytter and Bruce Watson", year = "2019", month = "5", day = "15", doi = "10.1007/978-3-030-19909-8_19", language = "English", isbn = "9783030199081", volume = "560", series = "IFIP Advances in Information and Communication Technology", publisher = "Springer", pages = "219--224", editor = "Ilias Maglogiannis and Lazaros Iliadis and John MacIntyre and Elias Pimenidis", booktitle = "Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops", }
@article{a57e0f5cc48746efb0094195583ee140, title = "Off-line and on-line algorithms for closed string factorization", abstract = "A string X=X[1..n], n>1, is said to be closed if it has a nonempty proper prefix that is also a suffix, but that otherwise occurs nowhere else in X; for n=1, every X is closed. Closed strings were introduced by Fici in [1] as objects of combinatorial interest. Recently Badkobeh et al.[2] described a variety of algorithms to factor a given string into closed factors. In particular, they studied the Longest Closed Factorization (LCF) problem, which greedily computes the decomposition X=X1X2⋯Xk, where X1 is the longest closed prefix of X, X2 the longest closed prefix of X with prefix X1 removed, and so on. In this paper we present an O(logn) amortized per character algorithm to compute LCF on-line, where n is the length of the string. We also introduce the Minimum Closed Factorization (MCF) problem, which identifies the minimum number of closed factors that cover X. We first describe an off-line O(nlog2n)-time algorithm to compute MCF(X), then we present an on-line algorithm for the same problem. In fact, we show that MCF(X) can be computed in O(Llogn) time from MCF(X′), where X′=X[1..n−1], and L is the largest integer such that the suffix X[n−L+1..n] is a substring of X′.", keywords = "Closed string, On-line, Minimum factorization", author = "Mai Alzamel and Iliopoulos, {Costas S.} and W.F. Smyth and Wing-Kin Sung", year = "2018", month = "10", day = "30", doi = "10.1016/j.tcs.2018.10.033", language = "English", journal = "Theoretical Computer Science", issn = "0304-3975", publisher = "Elsevier", }
@inbook{41d11e93341a4a27b792da026f2dab52, title = "Recent Advances of Palindromic Factorization", abstract = "This paper provides an overview of six particular problems of palindromic factorization and recent algorithmic improvements in solving them.", author = "Mai Alzamel and Iliopoulos, {Costas S.}", year = "2018", month = "4", day = "17", doi = "10.1007/978-3-319-78825-8_4", language = "English", volume = "10765", pages = "37--46", booktitle = "2018 Combinatorial Algorithms. Brankovic, L., Ryan, J. & Smyth, W. F. (eds.). Cham", publisher = "Springer International Publishing", edition = "LNCS", }
@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)", }
@article{7930cd53f3664c09b011342b26c4e343, title = "Efficient Computation of Palindromes in Sequences with Uncertainties Extension Version", author = "Alzamel, {Mai Abdulaziz M} and Chang Liu and Jia Gao and Costas Iliopoulos", year = "2018", language = "English", volume = "163", pages = "253--266", journal = "FUNDAMENTA INFORMATICAE", issn = "0169-2968", publisher = "IOS Press", number = "3", }
@conference{3479fb4029c94581acc80dee8a15894e, title = "Efficient Computation of Sequence Mappability", author = "Alzamel, {Mai Abdulaziz M} and Panagiotis Charalampopoulos and Costas Iliopoulos and Tomasz Kociumaka and Solon Pissis and Jakub Radoszewski and Juliusz Straszynski", year = "2018", doi = "10.1007{\%}2F978-3-030-00479-8_2", language = "English", pages = "12--26", note = "25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018", }
@inbook{b3a81111a154435b901a03eef1e95859, title = "How Much Different Are Two Words with Different Shortest Periods", abstract = "Sometimes the difference between two distinct words of the same length cannot be smaller than a certain minimal amount. In particular if two distinct words of the same length are both periodic or quasiperiodic, then their Hamming distance is at least 2. We study here how the minimum Hamming distance dist (x,y)dist(x,y)between two words x, y of the same length n depends on their periods. Similar problems were considered in [1] in the context of quasiperiodicities. We say that a period p of a word x is primitive if x does not have any smaller period p'ptextasciiacutexwhich divides p. For integers p, n (pbackslashle np≤n) we define backslashmathcal Pp(n)Pp(n)as the set of words of length n with primitive period p. We show several results related to the following functions introduced in this paper for pbackslashne qp≠qand n backslashge backslashmax (p,q)n≥max(p,q). backslashbeginaligned backslashmathcal Dp,q(n) = backslashmin backslash,backslashbackslash, dist (x,y)backslash,:backslash; xbackslashin backslashmathcal Pp(n), backslash,ybackslashin backslashmathcal Pq(n)backslash,backslash, backslashbackslash Np,q(h) = backslashmax backslash,backslashbackslash, n backslash,:backslash; backslashmathcal Dp,q(n)backslashle hbackslash,backslash. backslashqquad backslashqquad backslashendalignedDp,q(n)=mindist(x,y):x∈Pp(n),y∈Pq(n),Np,q(h)=maxn:Dp,q(n)≤h.", author = "Mai Alzamel and Maxime Crochemore and Iliopoulos, {Costas S.} and Tomasz Kociumaka and Ritu Kundu and Jakub Radoszewski and Wojciech Rytter and Tomasz Wale", year = "2018", doi = "10.1007/978-3-319-92016-0_16", language = "Undefined/Unknown", isbn = "9783319920160", pages = "168--178", editor = "Lazaros Iliadis and Ilias Maglogiannis and Vassilis Plagianakos", booktitle = "Artificial Intelligence Applications and Innovations", publisher = "Springer International Publishing", }
@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", }
@article{29e5c911acbf412b9350a988fae9f05f, title = "The Future of Informatics in Biomedicine", abstract = "Future of Informatics in Biomedicine is a special issue to publish articles to reflect a commitment to high-quality original research papers, reviews, and commentaries on novel algorithms for biological sequence and structure analysis, phylogeny reconstruction, and combinatorial algorithms. Its main focus is on new developments in genome bioinformatics and computational biology. Areas of interest include but are not limited to: sequence analysis, big data, biostatistics, image analysis, network and graph models, scientific data management and data mining, machine learning, pattern recognition, computational evolutionary biology, computational genomics, and related areas.", author = "Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos", year = "2018", language = "English", journal = "AIMS Journal", issn = "1357-9657", }
@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", }
@inbook{ccf1e5d7c5e04ce49b405377c39b7b57, title = "Palindromic Decompositions with Gaps and Errors", abstract = "Identifying palindromes in sequences has been an interest-ing line of research in combinatorics on words and also in computational biology, after the discovery of the relation of palindromes in the DNA sequence with the HIV virus. Effcient algorithms for the factorization of sequences into palindromes and maximal palindromes have been devised in recent years. We extend these studies by allowing gaps in decomposi-tions and errors in palindromes, and also imposing a lower bound to the length of acceptable palindromes. We first present an algorithm for obtaining a palindromic decompo-sition of a string of length n with the minimal total gap length in time O(n log n · g) and space O(n · g), where g is the number of allowed gaps in the decomposition. We then consider a decomposition of the string in maximal δ-palindromes (i.e. palindromes with δ errors under the edit or Hamming distance) and g allowed gaps. We present an algorithm to obtain such a decomposition with the minimal total gap length in time O(n · (g + δ)) and space O(n · g).", author = "Michal Adamczyk and Mai Alzamel and Panagiotis Charalampopoulos and Costas Iliopoulos and Jakub Radoszewski", year = "2017", doi = "10.1007/978-3-319-58747-9_7", language = "English", isbn = "9783319587462", volume = "10304 LNCS", series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)", publisher = "Springer Verlag", pages = "48--61", booktitle = "Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings", address = "Germany", }
@inbook{56f80f07dfb54f758dcdaf6fd732ae08, title = "Fast Fingerprint Recognition Using Circular String Pattern Matching Techniques", abstract = "The performance of Automated Fingerprint Identification System (AFIS) heavily relies on how efficiently minutiae are extracted. Most, if not all, AFIS compare minutiae information (such as ridge endings and bifurcation position) in form of sets of coordinates for verification or identification. Surprisingly, research on alternative minutiae extraction schemes is scarce. This paper, proposes the implementation of the novel approach to fingerprint recognition based on the extraction of minutiae in form of circular strings, which are suitable for approximate circular string matching. In addition to that, the proposed solution is able to detect the exact location and rotation of the input fingerprint regardless of its location on the scan surface.", author = "Ajala, {Oluwole Ifeanyi} and Aljamea, {Mudhi Mohammed} and Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos", year = "2016", month = "3", day = "20", language = "English", booktitle = "Patterns 2016", publisher = "IARIA", }
@inbook{4232ec0928c94999ada03c9aa85df9b0, title = "A Fast Fingerprint Identification Approach via Circular String Matching Filters", author = "Aljamea, {Mudhi Mohammed} and Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos and {Samir Uzzaman}, Mohammad", year = "2016", language = "English", booktitle = "FTC 2016 - Future Technologies Conference 2016", publisher = "IEEE", }
@inbook{78ef5901e1df4765a7974f96fddd741c, title = "Fast Fingerprint Rotation Recognition Technique Using Circular Strings in Lexicographical Order", author = "Ajala, {Oluwole Ifeanyi} and Aljamea, {Mudhi Mohammed} and Alzamel, {Mai Abdulaziz M} and Costas Iliopoulos", year = "2016", language = "English", booktitle = "SAI Intelligent Systems", publisher = "IEEE", }