Advanced Algorithms for Bioinformatics

 

Course Title:  

Advanced Algorithms for Bioinformatics 

Instructor:  

István Miklós 

Duration: 

Weeks 8-14, 2x2 hours/week, 2 credits 

Short Description of the Course:

The course introduces the applications of discrete mathematics in bioinformatics. After a quick review of the most important discrete structures, especially graphs, the students will learn various algorithms for 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.

Aim of the Course: 

The aim of the course is to give an introduction to all important algorithmic and combinatorial concepts arising in bioinformatics. By the end of the course, students will be able to read and understand scientific papers on bioinformatics methods. 

The students will improve their programming skills. The aim is to learn how to represent combinatorial structures such as graphs and sequences, and how to implement efficient algorithms such as dynamic programming algorithms on them. 

Prerequisites: 

Knowledge of at least one programming language, preferably Java, C or C++ is required. Some experience with basic proof methods (e.g. proof by construction, contradiction and induction) is recommended. A very basic knowledge of combinatorics is helpful, but not absolutely necessary. No knowledge of biology or chemistry is required for this course.
 

Detailed Program and Class Schedule:

 

  1. Introduction

Genome rearrangement, transforming the biology problem into a mathematical model

 

  1. Sorting by DCJ operations

 

  1. The concept of the graph of desire and reality

Safe cycle-increasing reversals

 

  1. Hurdles, super hurdles, fortresses

The Hannenhalli-Pevzner theory

 

  1. Sorting by block-interchanges

 

  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

 

Method of instruction: 

Lectures, recitations, project-based works, computer assignments 

Textbook: 

István Miklós: Introduction to algorithms in bioinformatics
http://www.renyi.hu/~miklosi/AlgorithmsOfBioinformatics.pdf 

Instructor’s Bio: 

István Miklós (born 1974) is a research fellow at the Rényi Institute, Hungarian Academy of Sciences. He graduated from Eötvös Loránd University as a mathematics teacher and biology-chemistry teacher in 1998. In the same year he started his Ph.D. studies in the field of statistical alignment under the supervision of János Podani. He received his Ph.D. in 2002, and took a postdoctoral position at the Department of Statistics, University of Oxford. He returned to Hungary in 2004 and has been teaching various bioinformatics courses at several universities, including the Budapest Semesters in Mathematics and Central European University since 2001. His main research fields are Markov chain Monte Carlo methods, genome rearrangement and stochastic models in bioinformatics. He has 37 peer-reviewed publications, including four book chapters. His Erdős number is 2.

 

 Download in PDF

 

Back