Advanced Algorithms and Models for Computational Biology

10-810, Spring 2006

School of Computer Science, Carnegie-Mellon University


Syllabus and Course Schedule

Module

Material covered

Online material and links

Dates and Instructor

Introduction
A primer of molecular biology, cell biology and genetics

Lecture 0 (1/18):

Outline

Intro to molecular biology

Lecture1 (1/23):

Intro to cell biology, functional genomics, and developmental biology
Jan 18: Ziv Bar-Joseph
and Eric Xing

Jan 23: Eric Xing

Biological Sequence Analysis
Basic probability

Gene finding

gene scan via HMM

coupled HMM

Hierarchical HMM

phylogenetic HMM

Motif/CRM finding

The MEME model

Bayesian motif models

Dictionary models

CRM structural models

Micro-RNA identification

Lecture 3 (1/25):

Sequence alignment

Lecture 4 (1/30):

HMM and Gene finding

Lecture 5 (2/1):

Extensions of HMMs

Lecture 6 (2/6):

Motif detection model and EM algorithm

Lecture 7 (2/8):

Micro RNA

Lecture 8 (2/13):

Bayesian motif detection, Gibbs sampling, and cis-regulatory module detection

Jan 25: Eric Xing

Jan 30: Eric Xing

Feb 1: Eric Xing

Feb 6: Eric Xing

Feb 8: Ziv Bar-Joseph

Feb 13: Eric Xing

Gene Expression Analysis
Overview
Normalization and differentially expressed genes
Clustering
Classification
Gene expression Dynamics

Lecture 9 (2/15):

Microarray overview

Lecture 10 (2/20):

Normalization

Lecture 11 (2/22):

Analyzing differentially expressed genes

Lecture 12 (2/27):

Clustering expression data

Lecture 13 (3/1):

Leaf ordering and classification

Lecture 14 (3/6):

Classification and time series

Feb 15: Ziv Bar-Joseph
Feb 20: Ziv Bar-Joseph
Feb 22: Ziv Bar-Joseph
Feb 27: Ziv Bar-Joseph
Mar 1: Ziv Bar-Joseph
Mar 6: Ziv Bar-Joseph

Guest lecture

Guest Lecture (3/22):

Motif detection and gene regulation

Mar 22: Takis Benos

Population Genetics
Meiosis and recombination
Linkage analysis
QTL mapping
SNPS and haplotype inference
pedigree and population inference
The coalescent process

Lecture 15 (3/8):

Meiosis and recombination

Lecture 16 (3/20):

Pedigree and linkage analysis

Lecture 17 (3/22 & 3/27):

Quantitative trait locus mapping

Lecture 18 (3/27):

Haplotype inference

Lecture 19 (3/29):

Coalescent processe, multi-population phasing, and haplotype blocks

Mar 8: Eric Xing
Mar 20: Eric Xing
Mar 27: Eric Xing
Mar 29: Eric Xing

Evolution and Phylogeny
Molecular evolution

Nucleotide substitution models, continuous-time Markov model

Phylogenetic tree building

Ancestral inference

Network evolution

scale-free network

network dynamics

Lecture 20 (4/3):

nucleotide substitution models

Lecture 21 (4/5):

Phylogenetic inference and comparative genomics

Lecture 22 (4/10):

Biological networks and network evolution

Apr 3: Eric Xing
Apr 5: Eric Xing
Apr 10: Eric Xing

Systems Biology
Bayesian Networks
MRF and active learning
Topology and network motifs
Cross-species network alignment
Protein-protein interactions

Lecture 23 (4/13):
networks algorithms

Lecture 24 (4/17):

Models for gene regulatory networks

Lecture 25 (4/19):

Graphical models and Bayesian networks

Lecture 26 (4/24):

Physical network models

Lecture 27 (4/26):

Computational discovery of gene modules and regulatory networks

Lecture 28 (5/1):

Rich probabilistic models for gene expression

Lecture 29 (5/3):

Comparative assessment of large-scale data sets of protein-protein interactions
Apr 12: Eric Xing
Apr 17: Eric Xing
Apr 19: Eric Xing
Apr 24: Ziv Bar-Joseph
Apr 26: Ziv Bar-Joseph
May 01:Ziv Bar-Joseph
May 03:Ziv Bar-Joseph
May 08:Ziv Bar-Joseph

Project presentation

May 10

Module	Material covered	Online material and links	Dates and Instructor
Introduction	A primer of molecular biology, cell biology and genetics	Lecture 0 (1/18): Outline Intro to molecular biology Lecture1 (1/23): Intro to cell biology, functional genomics, and developmental biology	Jan 18: Ziv Bar-Joseph and Eric Xing Jan 23: Eric Xing
Biological Sequence Analysis	Basic probability Gene finding gene scan via HMM coupled HMM Hierarchical HMM phylogenetic HMM Motif/CRM finding The MEME model Bayesian motif models Dictionary models CRM structural models Micro-RNA identification	Lecture 3 (1/25): Sequence alignment Lecture 4 (1/30): HMM and Gene finding Lecture 5 (2/1): Extensions of HMMs Lecture 6 (2/6): Motif detection model and EM algorithm Lecture 7 (2/8): Micro RNA Lecture 8 (2/13): Bayesian motif detection, Gibbs sampling, and cis-regulatory module detection	Jan 25: Eric Xing Jan 30: Eric Xing Feb 1: Eric Xing Feb 6: Eric Xing Feb 8: Ziv Bar-Joseph Feb 13: Eric Xing
Gene Expression Analysis	Overview Normalization and differentially expressed genes Clustering Classification Gene expression Dynamics	Lecture 9 (2/15): Microarray overview Lecture 10 (2/20): Normalization Lecture 11 (2/22): Analyzing differentially expressed genes Lecture 12 (2/27): Clustering expression data Lecture 13 (3/1): Leaf ordering and classification Lecture 14 (3/6): Classification and time series	Feb 15: Ziv Bar-Joseph Feb 20: Ziv Bar-Joseph Feb 22: Ziv Bar-Joseph Feb 27: Ziv Bar-Joseph Mar 1: Ziv Bar-Joseph Mar 6: Ziv Bar-Joseph
Guest lecture		Guest Lecture (3/22): Motif detection and gene regulation	Mar 22: Takis Benos
Population Genetics	Meiosis and recombination Linkage analysis QTL mapping SNPS and haplotype inference pedigree and population inference The coalescent process	Lecture 15 (3/8): Meiosis and recombination Lecture 16 (3/20): Pedigree and linkage analysis Lecture 17 (3/22 & 3/27): Quantitative trait locus mapping Lecture 18 (3/27): Haplotype inference Lecture 19 (3/29): Coalescent processe, multi-population phasing, and haplotype blocks	Mar 8: Eric Xing Mar 20: Eric Xing Mar 27: Eric Xing Mar 29: Eric Xing
Evolution and Phylogeny	Molecular evolution Nucleotide substitution models, continuous-time Markov model Phylogenetic tree building Ancestral inference Network evolution scale-free network network dynamics	Lecture 20 (4/3): nucleotide substitution models Lecture 21 (4/5): Phylogenetic inference and comparative genomics Lecture 22 (4/10): Biological networks and network evolution	Apr 3: Eric Xing Apr 5: Eric Xing Apr 10: Eric Xing
Systems Biology	Bayesian Networks MRF and active learning Topology and network motifs Cross-species network alignment Protein-protein interactions	Lecture 23 (4/13): networks algorithms Lecture 24 (4/17): Models for gene regulatory networks Lecture 25 (4/19): Graphical models and Bayesian networks Lecture 26 (4/24): Physical network models Lecture 27 (4/26): Computational discovery of gene modules and regulatory networks Lecture 28 (5/1): Rich probabilistic models for gene expression Lecture 29 (5/3): Comparative assessment of large-scale data sets of protein-protein interactions	Apr 12: Eric Xing Apr 17: Eric Xing Apr 19: Eric Xing Apr 24: Ziv Bar-Joseph Apr 26: Ziv Bar-Joseph May 01:Ziv Bar-Joseph May 03:Ziv Bar-Joseph May 08:Ziv Bar-Joseph
Project presentation			May 10


Recitation Schedule


Date	Time	Place	Topic


Additional Readings:

Review of statistical methods for QTL mapping in experimental crosses, Broman KW.

Multiple Interval Mapping for Quantitative Trait Loci, Kao, et al.

General formulas for obtaining the MLEs and the asymptotic variance-covariance matrix in mapping quantitative trait loci when using the EM algorithm, Kao CH, Zeng ZB

Multiple regression approach to mapping of quantitative trait loci (QTL) based on sib-pair data: a theoretical analysis, Sunwei Guo and Momiao Xiong

Interval Mapping of Multiple Quantitative Trait Loci (1993), Ritsert C. Jansen

Mar 27: Additional readings for lectures 18
Stephens, M., Smith, N., and Donnelly, P. (2001). A new statistical method for haplotype reconstruction from population data. American Journal of Human Genetics, 68, 978--989.

T. Niu, Z.S. Qin, X. Xu, and J. Liu (2002) Bayesian Haplotype Inference for Multiple Linked Single Nucleotide Polymorphisms. Am. J. Hum. Genet

Stephens, M., and Donnelly, P. (2003). A comparison of Bayesian methods for haplotype reconstruction from population genotype data. American Journal of Human Genetics, 73:1162-1169.

Apr 10: Additional readings for lectures 22
Network biology: understanding the cell's functional organization. Barabasi AL, Oltvai ZN.

Apr 17: Additional readings for lectures 24-25

Using Bayesian Networks to Analyze Expression Data with M. Linial, I.
Nachman, and D. Pe'er. In Proc. Fourth Annual Inter. Conf. on Computational Molecular Biology RECOMB, 2000

Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data.
Segal E, Shapira M, Regev A, Pe'er D, Botstein D, Koller D, Friedman N.

Adrian Dobra, Beatrix Jones, Chris Hans, Joseph R. Nevins and Mike West, Sparse graphical models for exploring gene expression data, 2004, J. Mult. Analysis, 90, 196-212.

More Additional readings

Class Monday, April 24:
Physical network models
http://people.csail.mit.edu/tommi/papers/YeaIdeJaa-jcb04.pdf

Class Wednesday, April 26
<http://www.cs.cmu.edu/%7Ezivbj/compBio/modules.pdf>Computational discovery 
of gene modules and regulatory networks
http://www.cs.cmu.edu/~zivbj/compBio/modules.pdf

Class Monday, May 1
Rich Probabilistic Models for Gene Expression
http://ai.stanford.edu/~erans/publications/ismb01.pdf

Class Wednesday, May 3
<http://www-2.cs.cmu.edu/%7Ezivbj/class04/comparative.pdf>Comparative 

assessment of large-scale data sets of protein protein interactions
http://www-2.cs.cmu.edu/~zivbj/class04/comparative.pdf

Syllabus and Course Schedule

Module

Material covered

Online material and links

Dates and Instructor