Algoritmi per la bioinformatica

Nadia Pisanti        Tel. 0502213152

Knowledge requirements:
A basic course on algorithmic.

Learning goals:
This course has the goal to give the student an overview of algorithmic methods that have been conceived for the analysis of genomic sequences, and to be able to critically observe the practical impact of algorithmic design on real problems with relevant applications.
The exam (see below for its description) has the goal to evaluate the students understanding of the problems and the methods described in the course. Moreover, the exam is additionally meant as a chance to learn how a scientific paper is like, and how to make an oral presentation on scientific/technical topics, that is designed for a specific audience.

Conoscenze.

Since 2012 this Master Program is no longer in italian.

Description of the course:
The course focuses both on theoretical and combinatorial aspects of algorithmical problems that raise from applications in molecular biology, as well as on practical issues such as whole genomes sequencing and the consequent assembly task, sequences alignments, the inference of repeated patterns and of long approximated repetitions, and several biologically relevant problems for the management and investigation of genomic data.

Contents:
A brief introduction to molecular biology: DNA, proteins, the cell, the synthesis of a protein.
Motifs Extraction: KMR Algorithm for the extracion of exact motifs and its modifications for the inference of approximate motifs.
Finding Repetitions: Algorithms for the inference of long approximate repetitions. Filters for preprocessing.
Sequences Alignments: Dynamic Programming methods for local, global, and semi-local alignments. Computing the Longest Common Subsequences. Multiple Alignments.
Fragment Assembly: Genomes sequencing: some history, scientific opportunities, and practical problems. Some possible approaches for the problem of assembling sequenced fragments. Link with the “Shortest common superstring” problem, the greedy solution. Data structures for representing and searching sequencing data.
New Generation Sequencing: Applications of High Throughput Sequencing and its algorithmic problems and challenges. Investigating data types resulting from the existing biotechnologies, and the possible data structures and algorithms for their storage and analysis.

References:

• JEWELS OF STRINGOLOGY, M.Crochemore and W.Rytter, World Scientific, 2002.
• INTRODUCTION TO COMPUTATIONAL MOLECULAR BIOLOGY, J.Setubal and J.Meidanis, PWS, 1997. 
• More course material given by the lecturer.