**
Introduction to Bioinformatics Algorithms
**

COMP130167.01

Lecture : 7/16 - 7/27 , Room: Z2103

Instructors: Haixu Tang
; Yuzhen Ye
; Shanfeng Zhu

TA: Zihan Zhang (17210240027@fudan.edu.cn)

**Final: 7/27/2018 **

**Synopsis:**
In the past few decades, modern biology has become a critical resource
of new computational problems inspiring the development of novel algorithmic ideas. A
preeminent example is the development of efficient string pattern matching algorithms based on
suffix trees and suffix arrays emerging from the comparison of long genomic sequences,
which are later applied to other fields such as text searching and mining.
The course will introduce the algorithmic ideas used for addressing real-world biological questions,
including brute-force search, greedy algorithms, dynamic programming, randomized algorithms, graph algorithms,
clustering algorithms and Hidden Markov Models (HMMs), etc.
For each algorithmic idea, we will start with an important biological question, such as
“*Which DNA Patterns Play the Role of Molecular Clocks*?” and “*How Did Yeast Become a Wine Brewer*?”, and
then gradually present algorithms to answer this question. In addition to algorithmic ideas,
the course will concentrate on the useful intuition to formulate the right algorithmic problem from a biological question.
We hope to motivate an algorithmic thinking through the solutions of modern biological problems, which will help to
develop problem-solving skills for not only the students interested in bioinformatics, but also the students interested in other fields.

Textbooks:

1.
Bioinformatics Algorithms: an Active Learning Approach, Volume I and II, 2nd Edition, by Phillip Compeau and Pavel Pevzner
,2015

2.
生物信息学算法导论 N.C.琼斯 ，P.A.帕夫纳 化学工业出版社,2007

** Lab/programming exercise: ** ROSALIND

Slides & Course Videos

Assignments:

HW1 due 7/19

HW2 due 7/23

Grading:

Assignments 20 %

Lab/programming exercise 20 %

Final exam 60 %

**Prerequisites**: One programming class or equivalent programming experience in C/C++, Java or Python required. No biology background is assumed.

**Learning outcomes:**

1. Understand basic principles of computational biology and commonly used bioinformatics algorithms;

2. Develop algorithmic thinking to address practical problems through computational formulation;

3. Develop programming skills to implement efficient algorithms to solve computational problems such as biological problems.

** Preliminary syllabus:**

1.Basic molecular biology （1 school hour）

2.Algorithm warm-up: where in the genome does DNA start to replicate? （3 school hours）

3.Greedy and randomized algorithms: how do we find regulatory patterns in DNA?（3 school hours）

4.Graph algorithms: how do we assemble genomes?（3 school hours）

5.Brute-force algorithms: how do we sequence antibiotics?（3 school hours）

6.Dynamic programming: how do we compare biological sequences?（3 school hours）

7.Combinatorial algorithms:are there fragile regions in human genome?（3 school hours）

8.Evolutionary tree reconstruction: which animal gives us SARS?（3 school hours）

9.Clustering algorithms: how did yeast become a wine maker?（3 school hours）

10.Combinatorial patten matching: how do we locate disease-causing mutations?（3 school hours）

11.Hidden Markov Models (HMMs): why have biologists still not developed an HIV vaccine?（3 school hours）

12.Final exam（3 school hours）

** Timetable:**

Mon | Tue | Wed | Thu | Fri | Sat | Sun | |

1 | |||||||

2 | Introduction to Bioinformatics Algorithms 2-3,Z2103 |
Introduction to Bioinformatics Algorithms 2-3,Z2103 |
Introduction to Bioinformatics Algorithms 2-3,Z2103 |
Introduction to Bioinformatics Algorithms 2-3,Z2103 |
Introduction to Bioinformatics Algorithms 2-3,Z2103 |
||

3 | |||||||

4 | |||||||

5 | |||||||

6 | Introduction to Bioinformatics Algorithms 2-3,Z计算机学院机房(1) |
Introduction to Bioinformatics Algorithms 2-3,Z计算机学院机房(1) |
Introduction to Bioinformatics Algorithms 2-3,Z计算机学院机房(1) |
Introduction to Bioinformatics Algorithms 2-3,Z计算机学院机房(1) |
Introduction to Bioinformatics Algorithms 2,Z计算机学院机房(1) |
||

7 | |||||||

8 | |||||||

9 |

Last updated : 7/13/2018