DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE
E SCIENZE MATEMATICHE

UNIVERSITA' DEGLI STUDI DI SIENA
 
 Webmail
Home |  Home Education |  Contacts |  UniSi   Privacy e Cookie policy

Research Groups


Algorithms
Research area: Computer Science


  • 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 majority-rules 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 X-ray tomographic reconstruction: experiment, modeling, and algorithms (2013-2016)


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 short-read sequencing data usually leads to a fragmented set of genomic sequences (contigs). Ordering and orientating such contigs (scaffolding) represents the first, non-trivial 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 trade-offs time/size and trade-offs size/number of colors.
 
Keywords ERC
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




Username:
Password:


Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche - Via Roma, 56 53100 SIENA - Italy