29 citations · 45 across the 41 of their papers we have counts for
6 papers · 1 filter
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…