Paola Bonizzoni

Paola Bonizzoni is full professor in Computer Science at the Università di Milano-Bicocca.

Main research areas:  computational complexity, algorithms on graphs, algorithms for computational biology  and bioinformatics.
Her contributions include the solution of combinatorial problems in bioinformatics related to sequence analysis, haplotypying, phylogenetic reconstruction and comparison and alternative splicing prediction. Her most recent interests are on algorithms and data structures for next generation sequencing data.

She contributed to the investigation of mathematical models for the recombination of linear and circular DNA and on the computational power of splicing systems for regular  languages.


  • CIE (Computability In Europe)
  • ELIXIR Life Science Information
  • BITS (Bioinformatics Italian Society)


Managing editor of Computability, the Journal of the Association CiE (IOS Press)

Editor of CIE book series Theory and Application of Computability

President of  the Association CiE

Member of the Program Committee (2016- 2017) of

  • IWOCA 2015,  26th International Workshop on Combinatorial Algorithms
  • ISBRA 2016 12th International Symposium on Bioinformatics Research and Applications
  • WABI017, Workshop on Algorithms in Bioinformatics 2017
  • ACM-BCB17 8th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics
  • CIE 2017, Computability in Europe 2017

Past services

Chair of

  • CIE 2013, Computability in Europe 2013

Other services

Recent Invited talks:

What is a gene? How and why computer science helps in answering this Question? (Joined keynote ACM-Conference on Bioinformatics, Computational Biology BCB  and Workshop on Algorithms in Bioinformatics  (WABI) 2015 )

 The Holy Grail: Finding the Genetic Bases of Phenotypic Characters (Unconventional Computation and Natural Computation  (UCNC)2012)

A novel perspective in algorithmic combinatorial methods for phasing populations in a coalescent model (International Conference on Computational Advances in Bio and Medical Sciences ICCABS 2011)

Discrete and Topological Models in Mathematical Biology, satellite workshop of the annual conference of the American Mathematical Society, University of Florida, Tampa, USA, March 2012.


CARIPLO 2013-0955 “Modulation of anti-cancer immune response by regulatory non-coding RNAs”

  • PIntron, intron prediction software
  • ASPIC-DB, alternative splicing prediction database
  • MIUR PRIN 2010-2011 grant “Automi e Linguaggi Formali: Aspetti Matematici e Applicativi” H41J12000190001
  • PPH, software for haplotype inference by perfect phylogeny
  • FIRB ’08 Bioinformatics: genomics and proteomics


NEW: Beyond Perfect Phylogeny: Multisample Phylogeny Reconstruction via ILP (ACM-BCB 2017)

Mapping RNA-seq Data to a Transcript Graph via Approximate Pattern Matching to a Hypertext. AlCoB 2017: 49-61

An External-Memory Algorithm for String Graph Construction. Algorithmica 78(2): 394-424 (2017)
HapCol: accurate and memory-efficient haplotype assembly from long reads.
Pirola Y., Zaccaria S., Dondi R., Klau GW., Pisanti N., Bonizzoni P. Bioinformatics. 2015 Aug
Haplotype assembly is the computational problem of reconstructing haplotypes in diploid organisms and is of fundamental importance for characterizing the effects of single-nucleotide polymorphisms on the expression of phenotypic traits. Haplotype assembly highly benefits from the advent of ‘future-generation’ sequencing technologies and their capability to produce long reads at increasing coverage. Existing methods are not able to deal with such data in a fully satisfactory way, either because accuracy or performances degrade as read length and sequencing coverage increase or because they are based on restrictive assumptions.
By exploiting a feature of future-generation technologies-the uniform distribution of sequencing errors-we designed an exact algorithm, called HapCol, that is exponential in the maximum number of corrections for each single-nucleotide polymorphism position and that minimizes the overall error-correction score. We performed an experimental analysis, comparing HapCol with the current state-of-the-art combinatorial methods both on real and simulated data. On a standard benchmark of real data, we show that HapCol is competitive with state-of-the-art methods, improving the accuracy and the number of phased positions. Furthermore, experiments on realistically simulated datasets revealed that HapCol requires significantly less computing resources, especially memory. Thanks to its computational efficiency, HapCol can overcome the limits of previous approaches, allowing to phase datasets with higher coverage and without the traditional all-heterozygous assumption.
Our source code is available under the terms of the GNU General Public License at
On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem.

Paola Bonizzoni, Riccardo Dondi, Gunnar W. Klau, Yuri Pirola, Nadia Pisanti, Simone Zaccaria
CPM 2015, 100-113, Springer-Verlag

Transcriptome Assembly and Alternative Splicing Analysis
Paola Bonizzoni, Gianluca Della Vedova, Graziano Pesole, Ernesto Picardi, Yuri Pirola, and Raffaella Rizzi, in RNA Bioinformatics, Methods in Molecular Biology, vol. 1269, Springer-Verlag 2015

Modeling Alternative Splicing Variants from RNA-Seq Data with Isoform Graphs  Journal of Computational Biology Journal of Computational Biology 21(1): 16-40 (2014)  S. Beretta, P. Bonizzoni, G.D. Vedova, Y. Pirola, and R. Rizzi

When and how the Perfect Phylogeny model explains Evolution (review) In  Discrete and Topological Models in Molecular Biology in preparation, Springer-Verlag  2013 editors N. Jonoska, M. Saito.

Further Steps in TANGO: Improved Taxonomic Assignment in Metagenomics.  Bioinformatics 30(1): 17-23 (2014)

Existence of Constants in Regular Splicing Languages Information and Computation (2015), pp. 340-353 DOI information: 10.1016/j.ic.2015.04.001

The binary perfect phylogeny with persistent characters. Theor. Comput. Sci. 454: 51-63 (2012)


Dipartimento di Informatica Sistemistica e Comunicazione
Università Degli Studi di Milano-Bicocca
Viale Sarca 336 Milano, 20126 (ITALY)
email: bonizzoni at disco dot unimib dot it, tel. (+39) 02-64487814, fax: (+39) 02-64487839


see a  list at DBLP

PhD students

see past and present

Computer science and women: