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

    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
    4. Instructors






    István MIKLÓS




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


    Judit CSIMA




    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 :


    13. References, textbooks and resources Pevzner, Pavel: Computational Molecular Biology: An Algorithmic Approach (Computational Molecular Biology),




    Miklós, István: Algorithms of bioinformatics.



    14. Required learning hours and assignment
    Number of contact hours




    Preparation to the classes




    Preparation to the tests






    Assigned reading




    Preparation to the exam








    15. Syllabus prepared by






    István MIKLÓS




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