

 Computational complexity, efficient algorithms, and uniqueness issues for problems in Discrete Tomography;
 design of efficient algorithms for de novo peptide sequencing and for the scaffolding problem in Bioinformatics;
 protocols based on majorityrules in distributed systems, and dynamic multicolored monopolies
Area: Discrete Tomography Discrete Tomography focuses on the problem of reconstruction of binary images (or finite subsets of the integer lattice) from a small number of their projections. In general, tomography deals with the problem of determining shape and dimensional information of an object from a set of projections. In "continuous" tomography when a large number of projections is available, accurate reconstructions can be made by many different algorithms. It is typical for discrete tomography that only a few projections (line sums) are used. In this case, conventional techniques fail. A special case of discrete tomography deals with the problem of the reconstruction of a binary image from a small number of projections .Discrete tomography has strong connections with other mathematical fields, such as number theory, discrete mathematics, complexity theory and combinatorics.
 Study of reconstruction algorithms for special binary images
 Study of instability/stability problems
 Study of uniqueness from set of directions (for bounded sets)
Project: member of COST MP1207 (EXTREMA) Enhanced Xray tomographic reconstruction: experiment, modeling, and algorithms (20132016)
Area: Bioinformatics One of the key problems in Proteomics is the identification of peptides from mass spectrometry data. There are two fundamental approaches to this problem. One common approach is to search a database of mass spectra using various probabilistic methods. However, this approach has several limitations. A relatively new technique is de novo sequencing. This technique reconstructs the amino acidic sequence of a peptide from a given tandem mass spectra data without the use of database search techniques. The de novo assembly of shortread sequencing data usually leads to a fragmented set of genomic sequences (contigs). Ordering and orientating such contigs (scaffolding) represents the first, nontrivial step towards genome finishing and usually requires extensive processing and manual editing of large blocks of sequence.
Area: Distributed Algorithms We are studying extension of the setting of irreversible dynamic monopolies (or shortly, dynamos) from two to more than two colors. The distributed protocol can be described as follows: let G be a simple connected graph where every node has a color from a finite ordered set C={1,..., k} of colors. At each round, each node can increase its color according to the colors held by its neighbors. We are interested in the so called dynamos, that is, subsets of nodes initially having color k leading all the nodes to recolor by k under our protocol.
 Study of different models.
 Study of lower and upper bounds on the size of dynamos on specific topologies.
 Study of tradeoffs time/size and tradeoffs size/number of colors.


ERC Keywords PE1_15 Discrete mathematics and combinatorics PE6_13 Bioinformatics, biocomputing, and DNA and molecular computation PE6_4 Theoretical computer science, formal methods, and quantum computing Cryptology, security, privacy, quantum crypto PE6_6 Algorithms, distributed, parallel and network algorithms, algorithmic game theory 

People
Assistant Professors:
Sara Brunetti
External Collaborators:
Elena Lodi 




