2 citations · 2 across the 6 of their papers we have counts for
9 papers · 1 filter
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…
Fast Exact String to D-Texts Alignments
Njagi Moses Mwaniki, Erik Garrison, Nadia Pisanti
In recent years, aligning a sequence to a pangenome has become a central problem in genomics and pangenomics. A fast and accurate solution to this problem can serve as a toolkit to…
Pattern Masking for Dictionary Matching
Panagiotis Charalampopoulos, Huiping Chen, Peter Christen +4
In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a dictionary of strings, each of length , a query string of length , a…
Combinatorial Algorithms for String Sanitization
Giulia Bernardini, Huiping Chen, Alessio Conte +6
String data are often disseminated to support applications such as location-based service provision or DNA sequence analysis. This dissemination, however, may expose sensitive patt…
Elastic-Degenerate String Matching via Fast Matrix Multiplication
Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti +2
An elastic-degenerate (ED) string is a sequence of sets of strings of total length , which was recently proposed to model a set of similar sequences. The ED string matching…
Longest Property-Preserved Common Factor
Lorraine A. K Ayad, Giulia Bernardini, Roberto Grossi +4
In this paper we introduce a new family of string processing problems. We are given two or more strings and we are asked to compute a factor common to all strings that preserves a…
Detecting Mutations by eBWT
Nicola Prezza, Nadia Pisanti, Marinella Sciortino +1
In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides…
Optimal Listing of Cycles and st-Paths in Undirected Graphs
Rui Ferreira, Roberto Grossi, Andrea Marino +3
We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time ta…
MADMX: A Novel Strategy for Maximal Dense Motif Extraction
Roberto Grossi, Andrea Pietracaprina, Nadia Pisanti +3
We develop, analyze and experiment with a new tool, called MADMX, which extracts frequent motifs, possibly including don't care characters, from biological sequences. We introduce…