Parameterized Complexity of the k-anonymity Problem (2009)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo, Pirola, Yuri
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach...
A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters (2009)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo
The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments. The problem consists of looking for a partition that best...
Anonymizing Binary Tables is APX-hard (2007)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo
The problem of publishing personal data without giving up privacy is increasingly important. An interesting formalization is the $k$-anonymization, where all rows in a table are clustered in sets of...
Exemplar Longest Common Subsequence (2007)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo, Fertin, Guillaume, Rizzi, Rafaella, Vialette, Stéphane
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common...
Exemplar Longest Common Subsequence (2007)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo, Fertin, Guillaume, Rizzi, Rafaella, Vialette, Stéphane
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common...
Approximating Clustering of Fingerprint Vectors with Missing Values (2005)
Bonizzoni, Paola, Della Vedova, Gianluca, Dondi, Riccardo
The problem of clustering fingerprint vectors is an interesting problem in Computational Biology that has been proposed in (Figureroa et al. 2004). In this paper we show some improvements in closing...
Towards a Theory of Conservative Computing (2002)
Cattaneo, Gianpiero, Della Vedova, Gianluca, Leporati, Alberto, Leporini, Roberto
We extend the notion of conservativeness, given by Fredkin and Toffoli in 1982, to generic gates whose input and output lines may assume a finite number d of truth values. A physical interpretation...
Optimal algorithms for local vertex quartet cleaning (2002)
Della Vedova, Gianluca, Wareham, H. Todd
Motivation: Reconstructing evolutionary trees is an important problem in biology. A response to the computational intractability of most of the traditional criteria for inferring evolutionary trees...
Probe selection algorithms with applications in the analysis of microbial communities (2001)
Borneman, James, Chrobak, Marek, Della Vedova, Gianluca, Figueroa, Andres, Jiang, Tao
We propose two efficient heuristics for minimizing the number of oligonucleotide probes needed for analyzing populations of ribosomal RNA gene (rDNA) clones by hybridization experiments on DNA...
Analysis of Bacterial Community Composition by Oligonucleotide Fingerprinting of rRNA Genes
Valinsky, Lea, Della Vedova, Gianluca, Scupham, Alexandra J., Alvey, Sam, Figueroa, Andres, Yin, Bei, ...
One of the first steps in characterizing an ecosystem is to describe the organisms inhabiting it. For microbial studies, experimental limitations have hindered the ability to depict diverse...
Oligonucleotide Fingerprinting of rRNA Genes for Analysis of Fungal Community Composition
Valinsky, Lea, Della Vedova, Gianluca, Jiang, Tao, Borneman, James
Thorough assessments of fungal diversity are currently hindered by technological limitations. Here we describe a new method for identifying fungi, oligonucleotide fingerprinting of rRNA genes (OFRG)....
Analysis of Bacterial Community Composition by Oligonucleotide Fingerprinting of rRNA Genes
Valinsky, Lea, Della Vedova, Gianluca, Scupham, Alexandra J., Alvey, Sam, Figueroa, Andres, Yin, Bei, ...
One of the first steps in characterizing an ecosystem is to describe the organisms inhabiting it. For microbial studies, experimental limitations have hindered the ability to depict diverse...
Oligonucleotide Fingerprinting of rRNA Genes for Analysis of Fungal Community Composition
Valinsky, Lea, Della Vedova, Gianluca, Jiang, Tao, Borneman, James
Thorough assessments of fungal diversity are currently hindered by technological limitations. Here we describe a new method for identifying fungi, oligonucleotide fingerprinting of rRNA genes (OFRG)....