Solon P. Pissis

TCS Journal 2026 Journal Article

Minimizing the minimizers via alphabet reordering

• Hilde Verbeek
• Lorraine A.K. Ayad
• Grigorios Loukides
• Solon P. Pissis

Minimizer sampling is one of the most widely-used mechanisms for sampling strings [Schleimer et al. , SIGMOD 2003; Roberts et al. , Bioinformatics 2004]. Let S = S [ 1 ] … S [ n ] be a string over a totally ordered alphabet Σ. Further let w ≥ 2 and k ≥ 1 be two integers. The minimizer of S [ i. . i + w + k − 2 ] is the smallest position in [ i, i + w − 1 ] where the lexicographically smallest length-k substring of S [ i. . i + w + k − 2 ] starts. The set of minimizers over all i ∈ [ 1, n − w − k + 2 ] is the set M w, k ( S ) of the minimizers of S. We consider the following basic problem: Given S, w, and k, can we efficiently compute a total order on Σ that minimizes | M w, k ( S ) |? We show that this is unlikely by proving that the problem is NP-hard for any w ≥ 2 and k ≥ 1. Our result provides theoretical justification as to why there exist no exact algorithms for minimizing the minimizer samples, while there exists a plethora of heuristics for the same purpose.

I&C Journal 2025 Journal Article

Elastic-degenerate string comparison

• Estéban Gabory
• Moses Njagi Mwaniki
• Nadia Pisanti
• Solon P. Pissis
• Jakub Radoszewski
• Michelle Sweering
• Wiktor Zuba

An elastic-degenerate (ED) string T is a sequence of n sets T [ 1 ], …, T [ n ] containing m strings in total whose cumulative length is N. We call n, m, and N the length, the cardinality and the size of T, respectively. The language of T is defined as L ( T ) = { S 1 ⋯ S n: S i ∈ T [ i ] for all i ∈ [ 1, n ] }. Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call this problem the ED String Intersection (EDSI) problem. For two ED strings T 1 and T 2 of lengths n 1 and n 2, cardinalities m 1 and m 2, and sizes N 1 and N 2, respectively, we show the following: • There is no O ( ( N 1 N 2 ) 1 − ϵ ) -time algorithm, for any ϵ > 0, for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. • There is no combinatorial O ( ( N 1 + N 2 ) 1. 2 − ϵ f ( n 1, n 2 ) ) -time algorithm, for any ϵ > 0 and any function f, for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. • An O ( N 1 log ⁡ N 1 log ⁡ n 1 + N 2 log ⁡ N 2 log ⁡ n 2 ) -time algorithm for outputting a compact representation of the intersection language of two unary ED strings. When T 1 and T 2 are given in a compact representation, we show that the problem is NP-complete. • An O ( N 1 m 2 + N 2 m 1 ) -time algorithm for EDSI. • An O ˜ ( N 1 ω − 1 n 2 + N 2 ω − 1 n 1 ) -time algorithm for EDSI, where ω is the matrix multiplication exponent; the O ˜ notation suppresses factors that are polylogarithmic in the input size.

TCS Journal 2025 Journal Article

Subsequence covers of words

• Panagiotis Charalampopoulos
• Solon P. Pissis
• Jakub Radoszewski
• Wojciech Rytter
• Tomasz Waleń
• Wiktor Zuba

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].

MFCS Conference 2024 Conference Paper

Approximate Suffix-Prefix Dictionary Queries

• Wiktor Zuba
• Grigorios Loukides
• Solon P. Pissis
• Sharma V. Thankachan

In the all-pairs suffix-prefix (APSP) problem [Gusfield et al. , Inf. Process. Lett. 1992], we are given a dictionary R of r strings, S₁, …, S_r, of total length n, and we are asked to find the length SPL_{i, j} of the longest string that is both a suffix of S_i and a prefix of S_j, for all i, j ∈ [1. .r]. APSP is a classic problem in string algorithms with applications in bioinformatics, especially in sequence assembly. Since r = |R| is typically very large in real-world applications, considering all r² pairs of strings explicitly is prohibitive. This is when the data structure variant of APSP makes sense; in the same spirit as distance oracles computing shortest paths between any two vertices given online. We show how to quickly locate k-approximate matches (under the Hamming or the edit distance) in R using a version of the k-errata tree [Cole et al. , STOC 2004] that we introduce. Let SPL^k_{i, j} be the length of the longest suffix of S_i that is at distance at most k from a prefix of S_j. In particular, for any k = 𝒪(1), we show an 𝒪(nlog^k n)-sized data structure to support the following queries: - One-to-One^k(i, j): output SPL^k_{i, j} in 𝒪(log^k nlog log n) time. - Report^k(i, d): output all j ∈ [1. .r], such that SPL^k_{i, j} ≥ d, in 𝒪(log^{k}n(log n/log log n+output)) time, where output denotes the size of the output. In fact, our algorithms work for any value of k not just for k = 𝒪(1), but the formulas bounding the complexities get much more complicated for larger values of k.

JBHI Journal 2022 Journal Article

Clustering Demographics and Sequences of Diagnosis Codes

• Haodi Zhong
• Grigorios Loukides
• Solon P. Pissis

A Relational-Sequential dataset (or RS-dataset for short) contains records comprised of a patient’s values in demographic attributes and their sequence of diagnosis codes. The task of clustering an RS-dataset is helpful for analyses ranging from pattern mining to classification. However, existing methods are not appropriate to perform this task. Thus, we initiate a study of how an RS-dataset can be clustered effectively and efficiently. We formalize the task of clustering an RS-dataset as an optimization problem. At the heart of the problem is a distance measure we design to quantify the pairwise similarity between records of an RS-dataset. Our measure uses a tree structure that encodes hierarchical relationships between records, based on their demographics, as well as an edit-distance-like measure that captures both the sequentiality and the semantic similarity of diagnosis codes. We also develop an algorithm which first identifies k representative records (centers), for a given k, and then constructs k clusters, each containing one center and the records that are closer to the center compared to other centers. Experiments using two Electronic Health Record datasets demonstrate that our algorithm constructs compact and well-separated clusters, which preserve meaningful relationships between demographics and sequences of diagnosis codes, while being efficient and scalable.

TCS Journal 2022 Journal Article

Internal shortest absent word queries in constant time and linear space

• Golnaz Badkobeh
• Panagiotis Charalampopoulos
• Dmitry Kosolobov
• Solon P. Pissis

Given a string T of length n over an alphabet Σ ⊂ { 1, 2, …, n O ( 1 ) } of size σ, we are to preprocess T so that given a range [ i, j ], we can return a representation of a shortest string over Σ that is absent in the fragment T [ i ] ⋯ T [ j ] of T. We present an O ( n ) -space data structure that answers such queries in constant time and can be constructed in O ( n log σ ⁡ n ) time.

I&C Journal 2021 Journal Article

Efficient pattern matching in elastic-degenerate strings

• Costas S. Iliopoulos
• Ritu Kundu
• Solon P. Pissis

Motivated by applications in bioinformatics and image searching, in what follows, we study the classic pattern matching problem in the context of elastic-degenerate strings: the generalised notion of gapped strings. An elastic-degenerate string can be seen as an ordered collection of k strings interleaved by k − 1 elastic-degenerate symbols, where each such elastic-degenerate symbol corresponds to a set of two or more variable-length strings. We present efficient algorithms for two variants of the pattern matching problem on elastic-degenerate strings: first, for a solid pattern and an elastic-degenerate text; second, for an elastic-degenerate pattern and a solid text. A proof-of-concept implementation of the former is provided.

TCS Journal 2021 Journal Article

Influence maximization in the presence of vulnerable nodes: A ratio perspective

• Huiping Chen
• Grigorios Loukides
• Solon P. Pissis
• Hau Chan

Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e. g. , predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.

I&C Journal 2020 Journal Article

Absent words in a sliding window with applications

• Maxime Crochemore
• Alice Héliou
• Gregory Kucherov
• Laurent Mouchard
• Solon P. Pissis
• Yann Ramusat

An absent word of a word y is a word that does not occur in y. It is then called minimal if all its proper factors occur in y. In fact, minimal absent words (MAWs) provide useful information about y and thus have several applications. In this paper, we propose an algorithm that maintains the set of MAWs of a fixed-length window sliding over y online. Our algorithm represents MAWs through nodes of the suffix tree. Specifically, the suffix tree of the sliding window is maintained using modified Senft's algorithm (Senft, 2005), itself generalizing Ukkonen's online algorithm (Ukkonen, 1995). We then apply this algorithm to the approximate pattern-matching problem under the Length Weighted Index distance (Chairungsee and Crochemore, 2012). This results in an online O ( σ | y | ) -time algorithm for finding approximate occurrences of a word x in y, | x | ≤ | y |, where σ is the alphabet size.

TCS Journal 2020 Journal Article

Approximate pattern matching on elastic-degenerate text

• Giulia Bernardini
• Nadia Pisanti
• Solon P. Pissis
• Giovanna Rosone

An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e. g. , pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O ( n m 1. 381 + N ) -time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O ( k 2 m G + k N ) -time and O ( m ) -space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O ( k m G + k N ) -time and O ( m ) -space algorithm for solving the problem under Hamming distance.

TCS Journal 2020 Journal Article

Faster algorithms for 1-mappability of a sequence

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

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 ( m n log ⁡ n / log ⁡ log ⁡ n ) using space O ( n ). Here we present two new algorithms that require worst-case time O ( m n ) and O ( n log ⁡ n log ⁡ log ⁡ n ), 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 ( k n ) and space O ( n ) if m = Ω ( k log σ ⁡ 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.

I&C Journal 2020 Journal Article

Indexing weighted sequences: Neat and efficient

• Carl Barton
• Tomasz Kociumaka
• Chang Liu
• Solon P. Pissis
• Jakub Radoszewski

A weighted sequence is a sequence of probability mass functions over a finite alphabet. A weighted index is a data structure constructed for a weighted sequence and a threshold 1 z that, given a string pattern, reports all positions where it occurs in the weighted sequence with probability at least 1 z. We present an O ( n z ) -time construction of an O ( n z ) -sized weighted index for a weighted sequence of length n that answers queries in optimal time. The previous solution by Amir et al. (2008) required O ( n z 2 log ⁡ z ) time and space. Our main tools are a construction of a family of ⌊ z ⌋ strings that carries the information about all the strings that occur in a weighted sequence and a more straightforward solution to so-called property indexing. We present applications of our weighted index, in particular in approximate and general scenarios that were introduced by Biswas et al. (2016), and provide its implementation.

TCS Journal 2020 Journal Article

Longest property-preserved common factor: A new string-processing framework

• Lorraine A.K. Ayad
• Giulia Bernardini
• Roberto Grossi
• Costas S. Iliopoulos
• Nadia Pisanti
• Solon P. Pissis
• Giovanna Rosone

We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1 < k ′ ≤ k and we are asked to find a longest periodic factor common to at least k ′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.

TCS Journal 2019 Journal Article

On overabundant words and their application to biological sequence analysis

• Yannis Almirantis
• Panagiotis Charalampopoulos
• Jia Gao
• Costas S. Iliopoulos
• Manal Mohamed
• Solon P. Pissis
• Dimitris Polychronopoulos

The observed frequency of the longest proper prefix, the longest proper suffix, and the longest infix of a word w in a given sequence x can be used for classifying w as avoided or overabundant. The definitions used for the expectation and deviation of w in this statistical model were described and biologically justified by Brendel et al. (1986) [1]. We have very recently introduced a time-optimal algorithm for computing all avoided words of a given sequence over an integer alphabet (2017) [2]. In this article, we extend this study by presenting an O ( n ) -time and O ( n ) -space algorithm for computing all overabundant words in a sequence x of length n over an integer alphabet. Our main result is based on a new non-trivial combinatorial property of the suffix tree T of x: the number of distinct factors of x whose longest infix is the label of an explicit node of T is no more than 3 n − 4. We further show that the presented algorithm is time-optimal by proving that O ( n ) is a tight upper bound for the number of overabundant words. Finally, we present experimental results, using both synthetic and real data, which justify the effectiveness and efficiency of our approach in practical terms.

I&C Journal 2019 Journal Article

On-line weighted pattern matching

• Panagiotis Charalampopoulos
• Costas S. Iliopoulos
• Solon P. Pissis
• Jakub Radoszewski

A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold 1 z, and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i − m + 1, …, i in X is at least 1 z. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O ( ( σ + log ⁡ z ) log ⁡ m ) or O ( σ log 2 ⁡ m ) time per arriving position; with the space requirement however being O ( m min ⁡ ( σ, z ) ). Our main result is a new algorithm that processes each arriving position of X in O ( z + σ ) time using O ( m + z ) extra space.

TCS Journal 2018 Journal Article

Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos)

• Maxime Crochemore
• Solon P. Pissis

I&C Journal 2018 Journal Article

Alignment-free sequence comparison using absent words

• Panagiotis Charalampopoulos
• Maxime Crochemore
• Gabriele Fici
• Robert Mercaş
• Solon P. Pissis

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as q-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an absent word of some sequence if it does not occur in the sequence. An absent word is minimal if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering all their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word x of length n, computes the largest integer for which all factors of x of that length occur in some minimal absent word of x in time and space O ( n ). Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight.

TCS Journal 2018 Journal Article

Efficient algorithms for shortest partial seeds in words

• Tomasz Kociumaka
• Solon P. Pissis
• Jakub Radoszewski
• Wojciech Rytter
• Tomasz Waleń

A factor u of a word w is a cover of w if every position in w lies within some occurrence of u in w. A factor u is a seed of w if it is a cover of a superstring of w. Covers and seeds extend the classical notions of periodicity. We introduce a new notion of α-partial seed, that is, a factor covering as a seed at least α positions in a given word. We use the Cover Suffix Tree, recently introduced in the context of α-partial covers (Kociumaka et al. , 2015, [13]); an O ( n log ⁡ n ) -time algorithm constructing such a tree is known. However, it appears that partial seeds are more complicated than partial covers—our algorithms require algebraic manipulations of special functions related to edges of the modified Cover Suffix Tree and the border array. We present a procedure for computing shortest α-partial seeds that works in O ( n ) time if the Cover Suffix Tree is already given. This is a full version, which includes all the proofs, of a paper that appeared at CPM 2014 [1].

TCS Journal 2016 Journal Article

Linear-time computation of prefix table for weighted strings & applications

• Carl Barton
• Chang Liu
• Solon P. Pissis

The prefix table of a string is one of the most fundamental data structures of algorithms on strings: it determines the longest factor at each position of the string that matches a prefix of the string. It can be computed in time linear with respect to the size of the string, and hence it can be used efficiently for locating patterns or for regularity searching in strings. A weighted string is a string in which a set of letters may occur at each position with respective occurrence probabilities. Weighted strings, also known as position weight matrices or uncertain strings, naturally arise in many biological contexts; for example, they provide a method to realise approximation among occurrences of the same DNA segment. In this article, given a weighted string x of length n and a constant cumulative weight threshold 1 / z, defined as the minimal probability of occurrence of factors in x, we present an O ( n ) -time algorithm for computing the prefix table of x. Furthermore, we outline a number of applications of this result for solving various problems on non-standard strings, and present some preliminary experimental results.

TCS Journal 2016 Journal Article

Linear-time superbubble identification algorithm for genome assembly

• Ljiljana Brankovic
• Costas S. Iliopoulos
• Ritu Kundu
• Manal Mohamed
• Solon P. Pissis
• Fatima Vayani

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble. In this paper, we propose an O ( n + m ) -time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O ( m log ⁡ m ) -time algorithm by Sung et al.

TCS Journal 2016 Journal Article

Order-preserving indexing

• Maxime Crochemore
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Marcin Kubica
• Alessio Langiu
• Solon P. Pissis
• Jakub Radoszewski
• Wojciech Rytter

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees.

TCS Journal 2015 Journal Article

Global and local sequence alignment with a bounded number of gaps

• Carl Barton
• Tomáš Flouri
• Costas S. Iliopoulos
• Solon P. Pissis

Pairwise sequence alignment techniques have gained renewed interest in recent years, primarily due to their applications in re-sequencing—the assembly of a genome directed by a reference sequence. In this article, we show that adding the flexibility of bounding the number of gaps inserted in an alignment strengthens the classical sequence alignment scheme of scoring matrices and affine gap penalty scores. We present GapsMis, an algorithm for pairwise global sequence alignment with a variable, but bounded, number of gaps. It is based on computing a variant of the traditional dynamic programming matrix for global sequence alignment. We also present GapsMis-L, the analogous algorithm for pairwise local sequence alignment with a variable, but bounded, number of gaps. To test the accuracy of GapsMis and GapsMis-L we performed millions of pairwise sequence alignments under realistic conditions, based on the properties of real full-length genomes. The results show that GapsMis and GapsMis-L can increase the accuracy of extending short-read alignments compared to the traditional approaches. The importance of our contribution is underlined by the fact that the provided algorithms may be seamlessly integrated into any biological pipeline. The open-source code of our implementation is freely available at http: //www. inf. kcl. ac. uk/research/projects/gapmis/.

TCS Journal 2014 Journal Article

Extending alignments with k -mismatches and ℓ -gaps

• Carl Barton
• Costas S. Iliopoulos
• Inbok Lee
• Laurent Mouchard
• Kunsoo Park
• Solon P. Pissis

Recently, the problem of extending an alignment with k-mismatches and a single gap for pairwise sequence alignment was introduced (Flouri et al. , 2011). The authors considered the problem of extending an alignment under the Hamming distance model by also allowing the insertion of a single gap; and presented a Θ ( m β ) -time algorithm to solve it, where m is the length of the shortest sequence to be extended, and β is the maximum allowed length of the single gap. Very recently, it was shown (Flouri et al. , 2012) that this problem is strongly and directly motivated by the next-generation re-sequencing application: aligning tens of millions of short DNA sequences against a reference genome. In this article, we consider an extension of this problem: extending an alignment with k-mismatches and two gaps; and present a Θ ( m β ) -time algorithm to solve it. This extension is proved to be fundamental in the next-generation re-sequencing application (Alachiotis et al. , 2012). In addition, we present a generalisation of our solution to solve the problem of extending an alignment with k-mismatches and ℓ-gaps in time Θ ( m β ℓ ). The presented solutions work provided that all gaps in the alignment must occur in one of the two sequences.

TCS Journal 2013 Journal Article

Enhanced string covering

• Tomáš Flouri
• Costas S. Iliopoulos
• Tomasz Kociumaka
• Solon P. Pissis
• Simon J. Puglisi
• W.F. Smyth
• Wojciech Tyczyński

A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border—both prefix and suffix—of y. If u is a cover of a superstring of y then u is a seed of y. Covers and seeds are two formalisations of quasiperiodicity, and there exist linear-time algorithms for computing all the covers and seeds of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string: the enhanced cover; the enhanced left cover; and the enhanced left seed.