Fundamental algorithms for Bioinformatics (2016/2017)



Course code
4S004550
Credits
12
Coordinator
Ferdinando Cicalese
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 sem. Ferdinando Cicalese
    Bioinformatics algorithms 6 II sem. Zsuzsanna Liptak

    Lesson timetable

    I sem.
    Activity Day Time Type Place Note
    Algorithm design Tuesday 8:30 AM - 10:30 AM lesson Lecture Hall G  
    Algorithm design Thursday 10:30 AM - 12:30 PM lesson Lecture Hall G from Oct 3, 2016  to Oct 7, 2016
    Algorithm design Thursday 10:30 AM - 12:30 PM lesson Lecture Hall G from Nov 12, 2016  to Jan 31, 2017
    Algorithm design Thursday 10:30 AM - 12:30 PM lesson Hall Verde from Oct 10, 2016  to Nov 11, 2016
    II sem.
    Activity Day Time Type Place Note
    Bioinformatics algorithms Monday 11:30 AM - 1:30 PM lesson Lecture Hall G from Mar 11, 2017  to Jun 9, 2017
    Bioinformatics algorithms Monday 2:30 PM - 4:30 PM lesson Lecture Hall C from May 8, 2017  to Jun 5, 2017
    Bioinformatics algorithms Thursday 8:30 AM - 10:30 AM lesson Lecture Hall G from Mar 9, 2017  to Jun 9, 2017

    Learning outcomes

    ------------------------
    MM: Algorithm design
    ------------------------
    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. This module focuses on general principles of advanced algorithm design, using examples taken from classical solutions of real-life bioinformatics problems. Within the overall goals of the Masters Course, the module Algorithm Design will provide the students with: a wealth of advanced techniques for tackling nontrivial problems in bioinformatics; the skill to design algorithmic solutions for typical problems in genome analysis; the ability to identify the structural elements that make a problem difficult or a solution inefficient; and the capability to propose appropriate approaches to the solution of hard problems in bioinformatics
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    To learn about some of the basic algorithmic problems and solutions behind common bioinformatics applications (sequence alignment, sequence similarity, sequence assembly, RNA folding).

    Syllabus

    ------------------------
    MM: Algorithm design
    ------------------------
    Fundamental notions of algorithmic analysis (brief recap): graph traversals; shortest paths in graphs; minimum spanning tree; dynamic programming. Elements of computational complexity and NP-completeness Models of Genome Rearrangement: (i) polynomial time algorithm for sorting signed permutations; (ii) approximation algorithms for sorting unsigned permutations; (iii) Synteny Distance Some Fundamental Graph Problems: (i) Graph tours: Hamiltonian Cycles and Eulerian Cycles; efficient algorithms for Eulerian path and Eulerian cycle; (ii) The Traveling Salesman Problem: relationships to the hamiltonian cycle problems; inapproximability of the symmetric TSP; 2 approximation algorithm for the metric TSP Models for Physical Map: (i) polynomial time algorithm for The Consecutive Ones Property (C1P); (ii) approximation algorithm for the gap minimisation based on the metric TSP Models for DNA assembly: The Shortest Common Superstring problem and the approximation of the the maximum compression via weighted matching. Network Flow: maximum flow and min cut problems; maximum matching; decomposition of flow into edge disjoint paths; polynomial time algorithm for the minimum/maximum weight perfect matching in bipartite graphs. Models for Motif Finding: (i) the Consensus String Problem; (ii) Polynomial Time Approximation Scheme. Models of Haplotyping: polynomial time algorithms for the haplotyping problem for single individual on gapless data; extensions and parameterisations in the presence of data with gaps.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    Here is an overview of the topics that will be covered. * Introduction Part I: Pairwise Sequence Comparison * Pairwise sequence alignment * String distances * Pairwise alignment in practice: BLAST, Scoring matrices Part II: Multiple sequence alignment * exact DP algorithm * Carillo-Lipman search space reduction * approximation algorithm, heuristics Part III: RNA folding * Nussinov and Zuker algorithms, * approximation algorithm Part IV: Sequence assembly algorithms * Shotgun sequencing: SCS and other models * Sequencing by Hybridization and NGS: de Bruijn graphs, Euler tours

    Assessment methods and criteria

    ------------------------
    MM: Algorithm design
    ------------------------
    The exam verifies that the students can 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. The exam consists of a written test with open questions. The test includes some mandatory exercises and a set of exercises among which the student can choose what to work on. The mandatory exercises are meant to evaluate the student's knowledge of classical algorithms and analysis tools as seen during the course. "Free-choice" exercises test the ability of students to model "new" toy problems and design and analyse algorithmic solutions for it. The grade for the module Algorithm Design is determined by the result of the written test and the result of homework to be solved periodically during the semester. The overall grade for "Fundamental Algorithms for Bioinformatics" is computed by averaging the grades awarded for the two modules.
    ------------------------
    MM: Bioinformatics algorithms
    ------------------------
    Written exam, followed by oral exam. You are only admitted to the oral if you have passed the written 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 exams.

    Reference books
    Activity Author Title Publisher Year ISBN Note
    Algorithm design J. Kleinberg, É. Tardos Algorithm Design (Edizione 1) Addison Wesley 2006 978-0321295354
    Algorithm design H.J. Böckenhauer, D. Bongartz Algorithmic Aspects of Bioinformatics Springer 2007
    Algorithm design Neil C. Jones, Pavel A. Pevzner An introduction to bioinformatics algorithms (Edizione 1) MIT Press 2004 0-262-10106-8
    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 Joao Setubal and Joao Meidanis Introduction to Computational Biology 1997

    STUDENT MODULE EVALUATION - 2016/2017