Patterns and algorithms in high-throughput sequencing count data: Computational and biological challenges

Proteins interacting with the genome, such as histones and transcription factors, play a major role in the regulation of gene expression. Experimental techniques such as ChIP-seq provide a new type of digital sequences that quantify the presence of a protein along the genome. These are count signals: sequences as long as the genetic code, but with the natural numbers as an alphabet. The computational analysis of these sequences is challenging, as the biological patterns are complex and the datasets are large. This thesis presents 3 efficient algorithms for pattern detection problems in count signals. The first infers the genomic locations of positioned nucleosomes by using an appropriate wavelet and by integrating measurements from multiple ChIP-seq experiments. The second characterizes the regulatory processes acting on the chromatin and is based on an accurate probabilistic model for read counts. The third detects transcription factor binding sites from ChIP-exo data by simultaneously modelling the sequence and the read counts associated to a binding event. Overall, the thesis presents a general computational framework that is likely to be important for future challenges.

Alessandro Mammana graduated in Computer Science at the University of Padua and at the Scuola Galileiana di Studi Superiori. He obtained his doctoral degree at the Max Planck Institute for Molecular Genetics, Berlin, where he developed algorithms for Bioinformatics. He currently works on genome sequencing products at Illumina, in Cambridge (UK).