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