Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Algorithms in Bioinformatics

    A tantárgy neve magyarul / Name of the subject in Hungarian: Bioinformatikai algoritmusok

    Last updated: 2010. november 11.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics

    Mérnök informatikus szak

    BSc képzés

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA077   0/0/2/f 2  
    3. Course coordinator and department Dr. Csima Judit,
    Web page of the course www.cs.bme.hu/....
    4. Instructors
    Name

     

    		Position

     

    		Department

     

    István MIKLÓS

     

    		Lecturer

     

    		Alfréd Rényi Institute of Mathematics, Hungarian Academy of Science

     

    Judit CSIMA

     

    		Assoc.professor

     

    		Department of Computer Science and Information Theory

     

    7. Objectives, learning outcomes and obtained knowledge The objective of this course is to give an introduction to discrete mathematics and algorithms related to bioinformatics. The most important discrete structures: trees, sequences, graphs describing the biological entries will be introduced. The students will learn dynamic programming algorithms that are used to sequence comparison, likelihood calculations, RNA structure prediction (finding the most stable RNA structure), and other optimization problems. The course also covers genome rearrangement algorithms, which are mathematically beautiful and also very important in the age of genomics when millions of genomes are going to be sequenced. The student will learn skills necessary to read and understand scientific papers in the introduced topics.

     
    8. Synopsis
    1. Introduction

       

    Genome rearrangement, transforming the biology problem into a mathematical model

     

    The concept of the graph of desire and reality

     

    Safe cycle-increasing reversals

     

     
    1. Hurdles, superhurdles, fortresses

       

    The Hannenhalli-Pevzner theory

     

     
    1. Sorting by block interchanges

       

    Sorting by DCJ operations

     

     
    1. 2-approximation and 1.5 approximation for sorting by transpositions

       

     
    1. Multiple Genome Rearrangement problems

       

    The complexity of rearrangement problems. Reversal medians, DCJ medians

     

     
    1. Student presentations based on selected scientific papers

       

     
    1. Introduction to dynamic programming: longest common subsequence, pairwise sequence alignment, examples

       

     
    1. Sophisticated sequence alignment algorithms: aligning with affine gap penalty, local alignment, Hirschberg’s algorithm for aligning sequences in linear space

       

     
    1. Dynamic programming on trees: The small parsimony problem, Felsenstein’s algorithms, the Noah’s ark problem

       

     
    1. RNA structure prediction: Nussinov algorithm. Introduction of the Zuker-Tinoco energy model and the Zuker-Sankoff algorithm

       

     
    1. RNA secondary structures as context-free grammars. Parsing algorithms for context-free grammars.

       

     
    1. Student presentations based on selected scientific papers

       

    9. Method of instruction Lectures, recitations, project-based computer assignments

     
    10. Assessment The students are required to present read scientific papers in live PowerPoint presentations and/or chalk-talk, to be challenged by the instructor in front of the class.

     

     

    The presentations will illustrate students’ ability to explain an algorithm/idea/other scientific work to the audience.

     

     

    The student will also get exercises for homework. They have to handle in the solutions, and have to present the solutions at blackboard.

     

     

    Critical element of the grading will be the homework, presentations and two tests, one in the middle of the course, and one at the end of the course

     

     

    Grading will be based on the following criteria:

     

    - Homework                                                                            25 points

     

    - First student presentation                                                      15 points

     

    - Second student presentation                                                  15 points

     

    - Mid-term test                                                                         15 points

     

    - Final test                                                                                30 points

     

    12. Consultations You can reach the instructor at the following e-mail address for consultation:

     

    István MIKLÓS : miklosi@renyi.hu

     
    13. References, textbooks and resources Pevzner, Pavel: Computational Molecular Biology: An Algorithmic Approach (Computational Molecular Biology), http://www.amazon.com/Computational-Molecular-Biology-Algorithmic-Approach/dp/0262161974/ref=cm_cr_pr_product_top

     

     

     

    Miklós, István: Algorithms of bioinformatics. http://ramet.elte.hu/~miklosi/Bioinf-23May2007.pdf

     

     
    14. Required learning hours and assignment
    Number of contact hours

     

    		 28

     

    Preparation to the classes

     

    		   8

     

    Preparation to the tests

     

     

    Homework

     

     

    Assigned reading

     

    		   8

     

    Preparation to the exam

     

    		 16

     

    Total

     

    		 60

     

    15. Syllabus prepared by
    Name

     

    		Position

     

    		Department

     

    István MIKLÓS

     

    		lecturer

     

    		Alfréd Rényi Institute of Mathematics, Hungarian Academy of Science