CSE 836 

Probabilistic Models and Algorithms

in Computational Biology


Fall, 2017


Time: Tue & Thur 10:20-11:40AM


Location: 1300 Engineering Building


Instructor: Yanni Sun yannisun@cse.msu.edu


Office Hours (EB3134): 1:45-3:45 Thursday, and by appointment

Please find more about this course here.



Schedule (depending our progress, this schedule is subject to change. DEKM represents the recommended reference book: biological sequence analysis by R. Durbin, S. Eddy, A. Krogh, and G. Mitchison)

Homework submission guidelines: all the source codes should be submitted via Handin (https://www.secure.cse.msu.edu/handin/). Please make sure your programs can compile and run on arctic.cse.msu.edu, where I am going to test your program. Please write a "readme" file to tell me how to compile your source codes. For non-programming problems, bring your answers to class. 

Acknowledgements: some of the source codes and homework problems are provided by Dr. Sean Eddy and Dr. Jeremy Buhler.


All notes are posted here






Introduction to Bioinformatics, sequence alignment

9/5, 9/7

Global alignment, local alignment, affine gap functions

9/12, 9/14

Exact pattern search. Large-scale sequence comparison using minHash

9/19, 9/21

Locality Sensitivity Hashing (LSH)

9/26, 9/28

Suffix Trie, Suffix tree

10/3, 10/5

Suffix array, applications. Paper presentation topic: minHash and LSH

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4937194/ (minimap)

https://www.ncbi.nlm.nih.gov/pubmed/26006009  (MHAP)

10/10, 10/12

BWT and FM indexing for read mapping

10/17, 10/19

De novo assembly. Paper presentation topic: BWT and FM.

De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer”

https://genomebiology.biomedcentral.com/articles/10.1186/gb-2009-10-3-r25  (Bowtie)

10/24, 10/26

Assembly using overlap graph

10/31, 11/2

Assembly using de Bruijn graph

11/7, 11/9

Scaffolding, approximate match. Paper presentation topic: assembly algorithms/tools.



https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881401/  (use BWT for overlap detection)

11/14, 11/16


11/21, Thanksgiving


11/28, 11/30

Paper presentation topic:

12/5, 12/7