TY - GEN
T1 - Quasi-Linear-Time Algorithm for Longest Common Circular Factor
AU - Alzamel, Mai
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kociumaka, Tomasz
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Straszynski, Juliusz
AU - Walen, Tomasz
AU - Zuba, Wiktor
PY - 2019/6/6
Y1 - 2019/6/6
N2 - 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.
AB - 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.
KW - Circular pattern matching
KW - Internal pattern matching
KW - Intersection of hyperrectangles
KW - Longest common factor
UR - http://www.scopus.com/inward/record.url?scp=85068064362&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2019.25
DO - 10.4230/LIPIcs.CPM.2019.25
M3 - Conference contribution
VL - 128
SP - 25:1–25:14
BT - 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019
A2 - Pisanti, Nadia
A2 - Pissis, Solon P.
PB - LIPIcs
ER -
TY - JOUR
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 - 2019/5/23
Y1 - 2019/5/23
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. 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.
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. 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.
KW - Algorithms on strings
KW - Hamming distance
KW - Sequence mappability
UR - http://www.scopus.com/inward/record.url?scp=85067179715&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2019.04.026
DO - 10.1016/j.tcs.2019.04.026
M3 - Article
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
TY - CHAP
T1 - A Brief Overview of Dead-Zone Pattern Matching Algorithms
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
AU - Watson, Richard T.
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85065921354&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_18
DO - 10.1007/978-3-030-19909-8_18
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 208
EP - 218
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Pimenidis, Elias
A2 - Iliadis, Lazaros
A2 - Maglogiannis, Ilias
A2 - MacIntyre, John
PB - Springer
ER -
TY - CHAP
T1 - On the Cyclic Regularities of Strings
AU - Ajala, Oluwole Ifeanyi
AU - Alshammary, Miznah Hizam
AU - Alzamel, Mai Abdulaziz M
AU - Gao, Jia
AU - Iliopoulos, Costas
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Watson, Bruce
PY - 2019/5/15
Y1 - 2019/5/15
N2 - 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.
AB - 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.
KW - Covers
KW - Cyclic regularities
KW - Periods
UR - http://www.scopus.com/inward/record.url?scp=85065922538&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19909-8_19
DO - 10.1007/978-3-030-19909-8_19
M3 - Conference paper
SN - 9783030199081
VL - 560
T3 - IFIP Advances in Information and Communication Technology
SP - 219
EP - 224
BT - Artificial Intelligence Applications and Innovations - AIAI 2019 IFIP WG 12.5 International Workshops
A2 - Maglogiannis, Ilias
A2 - Iliadis, Lazaros
A2 - MacIntyre, John
A2 - Pimenidis, Elias
PB - Springer
ER -
TY - JOUR
T1 - Off-line and on-line algorithms for closed string factorization
AU - Alzamel, Mai
AU - Iliopoulos, Costas S.
AU - Smyth, W.F.
AU - Sung, Wing-Kin
PY - 2018/10/30
Y1 - 2018/10/30
N2 - 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′.
AB - 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′.
KW - Closed string
KW - On-line
KW - Minimum factorization
U2 - 10.1016/j.tcs.2018.10.033
DO - 10.1016/j.tcs.2018.10.033
M3 - Article
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -
TY - CHAP
T1 - Recent Advances of Palindromic Factorization
AU - Alzamel, Mai
AU - Iliopoulos, Costas S.
PY - 2018/4/17
Y1 - 2018/4/17
N2 - This paper provides an overview of six particular problems of palindromic factorization and recent algorithmic improvements in solving them.
AB - This paper provides an overview of six particular problems of palindromic factorization and recent algorithmic improvements in solving them.
U2 - 10.1007/978-3-319-78825-8_4
DO - 10.1007/978-3-319-78825-8_4
M3 - Conference paper
VL - 10765
SP - 37
EP - 46
BT - 2018 Combinatorial Algorithms. Brankovic, L., Ryan, J. & Smyth, W. F. (eds.). Cham
PB - Springer International Publishing
ER -
TY - CHAP
T1 - Degenerate String Comparison and Applications
AU - Alzamel, Mai
AU - Ayad, Lorraine A. K.
AU - Bernardini, Giulia
AU - Grossi, Roberto
AU - Iliopoulos, Costas S.
AU - Pisanti, Nadia
AU - Pissis, Solon P.
AU - Rosone, Giovanna
PY - 2018
Y1 - 2018
U2 - 10.4230/LIPIcs.WABI.2018.21
DO - 10.4230/LIPIcs.WABI.2018.21
M3 - Conference paper
SN - 9783959770828
VL - 113
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 21:1-21:14
BT - 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)
A2 - Parida, Laxmi
A2 - Ukkonen, Esko
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY - Dagstuhl, Germany
ER -
TY - JOUR
T1 - Efficient Computation of Palindromes in Sequences with Uncertainties Extension Version
AU - Alzamel, Mai Abdulaziz M
AU - Liu, Chang
AU - Gao, Jia
AU - Iliopoulos, Costas
PY - 2018
Y1 - 2018
M3 - Article
VL - 163
SP - 253
EP - 266
JO - FUNDAMENTA INFORMATICAE
JF - FUNDAMENTA INFORMATICAE
SN - 0169-2968
IS - 3
ER -
TY - CONF
T1 - Efficient Computation of Sequence Mappability
AU - Alzamel, Mai Abdulaziz M
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas
AU - Kociumaka, Tomasz
AU - Pissis, Solon
AU - Radoszewski, Jakub
AU - Straszynski, Juliusz
PY - 2018
Y1 - 2018
U2 - 10.1007%2F978-3-030-00479-8_2
DO - 10.1007%2F978-3-030-00479-8_2
M3 - Paper
SP - 12
EP - 26
ER -
TY - CHAP
T1 - How Much Different Are Two Words with Different Shortest Periods
AU - Alzamel, Mai
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Kociumaka, Tomasz
AU - Kundu, Ritu
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Wale, Tomasz
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-319-92016-0_16
DO - 10.1007/978-3-319-92016-0_16
M3 - Chapter
SN - 9783319920160
SP - 168
EP - 178
BT - Artificial Intelligence Applications and Innovations
A2 - Iliadis, Lazaros
A2 - Maglogiannis, Ilias
A2 - Plagianakos, Vassilis
PB - Springer International Publishing
CY - Cham
ER -
TY - CHAP
T1 - How to Answer a Small Batch of RMQs or LCA Queries in Practice
AU - Alzamel, Mai
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
PY - 2018
Y1 - 2018
U2 - 10.1007/978-3-319-78825-8_28
DO - 10.1007/978-3-319-78825-8_28
M3 - Conference paper
VL - 10765
T3 - Lecture Notes in Computer Science
SP - 343
EP - 355
BT - Combinatorial Algorithms
A2 - Brankovic, Ljiljana
A2 - Ryan, Joe
A2 - Smyth, William F.
PB - Springer International Publishing
CY - Cham
ER -
TY - JOUR
T1 - The Future of Informatics in Biomedicine
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - https://www.aimspress.com/newsinfo/712.html
M3 - Editorial
JO - AIMS Journal
JF - AIMS Journal
SN - 1357-9657
ER -
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
ER -
TY - CHAP
T1 - Efficient Computation of Palindromes in Sequences with Uncertainties
AU - Alzamel, Mai
AU - Gao, Jia
AU - Iliopoulos, Costas S.
AU - Liu, Chang
AU - Pissis, Solon P.
PY - 2017/8/2
Y1 - 2017/8/2
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-319-65172-9_52
DO - 10.1007/978-3-319-65172-9_52
M3 - Other chapter contribution
SN - 978-3-319-65171-2
VL - 744
SP - 620
EP - 629
BT - Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings
A2 - Boracchi, Giacomo
A2 - Iliadis, Lazaros
A2 - Jayne, Chrisina
A2 - Likas, Aristidis
PB - Springer International Publishing Switzerland
CY - Cham
ER -
TY - CHAP
T1 - Efficient Identification of k-Closed Strings
AU - Alamro, Hayam
AU - Alzamel, Mai
AU - Iliopoulos, Costas S.
AU - Pissis, Solon P.
AU - Watts, Steven
AU - Sung, Wing-Kin
PY - 2017/8/2
Y1 - 2017/8/2
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-319-65172-9_49
DO - 10.1007/978-3-319-65172-9_49
M3 - Other chapter contribution
SN - 978-3-319-65171-2
VL - 744
SP - 583
EP - 595
BT - Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings
A2 - Boracchi, Giacomo
A2 - Iliadis, Lazaros
A2 - Jayne, Chrisina
A2 - Likas, Aristidis
PB - Springer International Publishing Switzerland
CY - Cham
ER -
TY - CHAP
T1 - Palindromic Decompositions with Gaps and Errors
AU - Adamczyk, Michal
AU - Alzamel, Mai
AU - Charalampopoulos, Panagiotis
AU - Iliopoulos, Costas
AU - Radoszewski, Jakub
PY - 2017
Y1 - 2017
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=85019261702&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-58747-9_7
DO - 10.1007/978-3-319-58747-9_7
M3 - Other chapter contribution
AN - SCOPUS:85019261702
SN - 9783319587462
VL - 10304 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 48
EP - 61
BT - Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
PB - Springer Verlag
ER -
TY - CHAP
T1 - Fast Fingerprint Recognition Using Circular String Pattern Matching Techniques
AU - Ajala, Oluwole Ifeanyi
AU - Aljamea, Mudhi Mohammed
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
PY - 2016/3/20
Y1 - 2016/3/20
N2 - 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.
AB - 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.
UR - http://www.iaria.org/conferences2016/PATTERNS16.html
M3 - Conference paper
BT - Patterns 2016
PB - IARIA
ER -
TY - CHAP
T1 - A Fast Fingerprint Identification Approach via Circular String Matching Filters
AU - Aljamea, Mudhi Mohammed
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
AU - Samir Uzzaman, Mohammad
PY - 2016
Y1 - 2016
M3 - Conference paper
BT - FTC 2016 - Future Technologies Conference 2016
PB - IEEE
ER -
TY - CHAP
T1 - Fast Fingerprint Rotation Recognition Technique Using Circular Strings in Lexicographical Order
AU - Ajala, Oluwole Ifeanyi
AU - Aljamea, Mudhi Mohammed
AU - Alzamel, Mai Abdulaziz M
AU - Iliopoulos, Costas
PY - 2016
Y1 - 2016
M3 - Conference paper
BT - SAI Intelligent Systems
PB - IEEE
ER -