6 citations · 7 across the 3 of their papers we have counts for
7 papers
The Complexity of Approximate Pattern Matching on De Bruijn Graphs
Daniel Gibney, Sharma V. Thankachan, Srinivas Aluru
Aligning a sequence to a walk in a labeled graph is a problem of fundamental importance to Computational Biology. For finding a walk in an arbitrary graph with edges that exa…
Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism
Daniel Gibney, Gary Hoppenworth, Sharma V. Thankachan
The CNF formula satisfiability problem (CNF-SAT) has been reduced to many fundamental problems in P to prove tight lower bounds under the Strong Exponential Time Hypothesis (SETH).…
On the Complexity of BWT-runs Minimization via Alphabet Reordering
Jason Bentley, Daniel Gibney, Sharma V. Thankachan
The Burrows-Wheeler Transform (BWT) has been an essential tool in text compression and indexing. First introduced in 1994, it went on to provide the backbone for the first encoding…
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
Daniel Gibney, Sharma V. Thankachan
In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these index structures far more complex than a sing…
On Computing Average Common Substring Over Run Length Encoded Sequences
Sahar Hooshmand, Neda Tavakoli, Paniz Abedin +1
The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS can be computed in O(n) space and time, where n=x+y is the inp…
Parameterized Pattern Matching -- Succinctly
Arnab Ganguly, Rahul Shah, Sharma V. Thankachan
We consider the problem, where a pattern matches some location in a text iff there is a one-to-one correspondence between the…