29 citations · 45 across the 41 of their papers we have counts for
66 papers
Mining Correlated Motifs with Wildcards in PPI Networks: Exact and Optimal
Lucas P. Oliveira, Ben Bals, Aalt D. J. van Dijk +1
A protein-protein interaction (PPI) network is a graph whose nodes are protein sequences and whose edges represent physical interactions between proteins. Correlated Motif Mining (…
ZigZag Trie: A Novel Index for Contextual Queries
Ling Li, Daniel Gibney, Sharma V. Thankachan +3
There is increasing interest in queries about the context of a string in a longer text , i.e., the set of all string pairs , with , for a given , such t…
Text Indexing: From Reporting to Counting
Ben Bals, Panagiotis Charalampopoulos, Oded Lachish +2
We prove an elementary yet powerful combinatorial lemma: in any rooted tree with leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is…
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…
Faster Algorithms for Shortest Unique or Absent Substrings
Panagiotis Charalampopoulos, Manal Mohamed, Solon P. Pissis +2
We revisit two well-known algorithmic problems on strings: computing a shortest unique substring (SUS) and a shortest absent substring (SAS) of a string of length . Both pro…
Optimal Enumeration of Eulerian Trails in Directed Graphs
Ben Bals, Solon P. Pissis, Matei Tinca
The BEST theorem, due to de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte, is a classical tool from graph theory that links the Eulerian trails in a directed graph wit…
Maximal Palindromes in MPC: Simple and Optimal
Solon P. Pissis
In the classical longest palindromic substring (LPS) problem, we are given a string of length , and the task is to output a longest palindromic substring in . Gilbert, Ha…
Subtree Mode and Applications
Jialong Zhou, Ben Bals, Matei Tinca +4
The mode of a collection of values (i.e., the most frequent value in the collection) is a key summary statistic. Finding the mode in a given range of an array of values is thus of…
Subsequence Covers of Words
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3
We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word is an s-cover of a word if the occurrences of in as subsequences cover…
When is String Reconstruction using de Bruijn Graphs Hard?
Ben Bals, Sebastiaan van Krieken, Solon P. Pissis +2
The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly…
Testing Quasiperiodicity
Christine Awofeso, Ben Bals, Oded Lachish +1
A cover (or quasiperiod) of a string is a shorter string such that every position of is contained in some occurrence of as a substring. The notion of covers was int…
Text Indexing and Pattern Matching with Ephemeral Edits
Solon P. Pissis
A sequence of edit operations in a string is called ephemeral if operation constructing string , for all with , is reverted b…
Contextual Pattern Mining and Counting
Ling Li, Daniel Gibney, Sharma V. Thankachan +2
Given a string of length , a longer string of length , and two integers and , the context of in is the set of all string pairs , w…
Resilient Pattern Mining
Pengxin Bian, Panagiotis Charalampopoulos, Lorraine A. K. Ayad +3
Frequent pattern mining is a flagship problem in data mining. In its most basic form, it asks for the set of substrings of a given string of length that occur at least …
Indexing Strings with Utilities
Giulia Bernardini, Huiping Chen, Alessio Conte +5
Applications in domains ranging from bioinformatics to advertising feature strings that come with numerical scores (utilities). The utilities quantify the importance, interest, pro…
Faster ED-String Matching with Mismatches
Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak +2
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compac…
Minimizers in Semi-Dynamic Strings
Wiktor Zuba, Oded Lachish, Solon P. Pissis
Minimizers sampling is one of the most widely-used mechanisms for sampling strings. Let be a string over an alphabet . In addition, let and $k\ge…
U-index: A Universal Indexing Framework for Matching Long Patterns
Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp +4
Text indexing is a fundamental and well-studied problem. Classic solutions either replace the original text with a compressed representation, e.g., the FM-index and its variants, o…
Scalable Order-Preserving Pattern Mining
Ling Li, Wiktor Zuba, Grigorios Loukides +2
Time series are ubiquitous in domains ranging from medicine to marketing and finance. Frequent Pattern Mining (FPM) from a time series has thus received much attention. Recently, i…
Elastic-Degenerate String Comparison
Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti +4
An elastic-degenerate (ED) string is a sequence of sets containing strings in total whose cumulative length is . We call , , and the len…
Optimal prefix-suffix queries with applications
Solon P. Pissis
We revisit the classic border tree data structure [Gu, Farach, Beigel, SODA 1994] that answers the following prefix-suffix queries on a string of length over an integer alp…
Text Indexing for Long Patterns using Locally Consistent Anchors
Lorraine A. K. Ayad, Grigorios Loukides, Solon P. Pissis
In many real-world database systems, a large fraction of the data is represented by strings: sequences of letters over some alphabet. This is because strings can easily encode data…
Minimizing the Minimizers via Alphabet Reordering
Hilde Verbeek, Lorraine A. K. Ayad, Grigorios Loukides +1
Minimizers sampling is one of the most widely-used mechanisms for sampling strings [Roberts et al., Bioinformatics 2004]. Let be a string over a totally ordered…
Space-Efficient Indexes for Uncertain Strings
Esteban Gabory, Chang Liu, Grigorios Loukides +2
Strings in the real world are often encoded with some level of uncertainty. In the character-level uncertainty model, an uncertain string of length on an alphabet is a…