Fundamental algorithms for Bioinformatics (2020/2021)



Course code
4S004550
Credits
12
Coordinator
Zsuzsanna Liptak
Other available courses
Other available courses
    Academic sector
    INF/01 - INFORMATICS
    Language of instruction
    English
    Teaching is organised as follows:
    Activity Credits Period Academic staff Timetable
    Algorithm design 6 I semestre Ferdinando Cicalese, Zsuzsanna Liptak

    Go to lesson schedule

    Bioinformatics algorithms 6 II semestre Zsuzsanna Liptak

    Go to lesson schedule

    Learning outcomes

    Students will acquire a wealth of advanced analytic tools which constitute the foundational basis of the algorithmic solution of important problems in bioinformatics Knowledge and understanding The aim of the course is to provide the student with the necessary skills and know-how for the design and analysis of algorithmic solutions to fundamental bioinformatics problems. Applying knowledge and understanding The students will acquire the ability to design algorithmic solutions for typical problems in bioinformatics and computational biology, e.g., analysis of “omics”-data. Making judgements The students will be able to identify the critical structural elements of a problem and the most appropriate approaches to tackle complex problems in bioinformatics. Communication The students will acquire the ability to describe with appropriate precision and clarity, to both experts and non-specialists: a bioinformatics problem, its mathematical model and the corresponding solution. Lifelong learning skills The students will be able to deepen their know-how in bioinformatics autonomously. Based on the topics studied and the knowledge acquired, they will be able to read, understand, and apply material from advanced text-books and scientific article.

    Syllabus

    ------------------------
    MM: Algorithm design
    ------------------------
    1. Fundamental notions of algorithmic analysis and complexity: Brief recap on graph traversals; shortest path problem; minimum spanning tree algorithms; elements of computational complexity and NP-completeness 2. Models for Genome Rearrangement: (i) approximation algorithms for reversal distance model (sorting unsigned permutations); (ii) the Doble Cut and Join model; (iii) Synteny Distance approximation algorithms 3. Models for DNA assembly: (i) The Shortest Common Superstring problem (SCS), connections to maximum cost TSP, approximation of the maximum compression via weighted matching; (ii) Assembly based on Eulerian Cycles and de Bruijn graphs; efficient algorithms for the Eulerian path and Eulerian cycle problem. 4. Distance measures for biological sequences: (i) edit distance, (ii) LCS-distance, (iii) q-gram distance, (iv) possibly further distances. 5. Introduction to data structures for genomic sequences: (i) Basics of Suffix trees and Suffix arrays; (ii) some applications.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    1. Pairwise Sequence Comparison (i) Pairwise sequence alignment (global, local) (ii) variants: optimal alignment in linear space, semiglobal, affine gap penalties, (iii) similarity vs. distance (iv) Pairwise alignment in practice: dotplots, BLAST, Scoring matrices 2. Multiple sequence alignment: (i) exact DP algorithm, (ii) Carillo-Lipman search space reduction, (iii) approximation algorithms, heuristics 3. RNA secondary structure prediction 4. Phylogenetic reconstruction: (i) distance based data: ultrametric trees and UPGMA, (ii) distance based data: additive trees and Neighbor Joining (iii) character based data: Perfect phylogeny (PP); (iv) character based data: Small Parsimony, Fitch' algorithm (v) heuristics for Large Parsimony.

    Assessment methods and criteria

    ------------------------
    MM: Algorithm design
    ------------------------
    The exam checks the capacity of the student to master the fundamental tools and techniques for the analysis and design of algorithms and that they understand how these techniques are employed in the solution of some classical computational problems arising in bioinformatics. To pass the exam, it is necessary to take a written test, consisting of open questions and/or multiple choice questions. The exercises are meant to evaluate the student's knowledge of classical algorithms and analysis tools as seen during the course, as well as their ability to model "new" toy problems and design and analyse algorithmic solutions for it. A student who reaches a grade of over 25 in the written test has to take an additional oral exam. The overall grade for "Fundamental Algorithms for Bioinformatics" is the average of the grades for the two modules.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    To pass the exam, it is necessary to take a written test. A student who reaches a grade of over 25 in the written test has to take an additional oral exam. The written exam consists of theoretical questions (problems studied, analysis of algorithms studied, mathematical properties, which algorithms exist for a problem etc.), as well as applications of algorithms to concrete examples (computing a pairwise alignment with the DP algorithm etc.) In the oral exam, the student will explain in detail their solutions to the written exam, and show to what extent they have mastered the topics. Students of the Masters in Molecular and medical biotechnology will have separate questions. (The exam is the same for students who follow the course during the semester and those who do not: frequentanti e no.)

    Reference books
    Activity Author Title Publisher Year ISBN Note
    Algorithm design H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Algorithm design Enno Ohlebusch Bioinformatics Algorithms 2013 978-3-00-041316-2
    Algorithm design Stein, Drysdale, Bogart Discrete Mathematics for Computer Scientists Pearson 2011 978-0-13-137710-3
    Algorithm design V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu Genome Scale Algorithm Design (Edizione 1) Cambridge University Press 2015 ISBN 978-1-107-07853-6
    Algorithm design J.C. Setubal, J. Meidanis Introduction to Computational Biology Pws Pub Co 1997
    Bioinformatics algorithms H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Bioinformatics algorithms Enno Ohlebusch Bioinformatics Algorithms 2013 978-3-00-041316-2
    Bioinformatics algorithms V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu Genome Scale Algorithm Design (Edizione 1) Cambridge University Press 2015 ISBN 978-1-107-07853-6
    Bioinformatics algorithms Joao Setubal and Joao Meidanis Introduction to Computational Biology 1997