Spring 2009 CAP6938: Special Topics in Computational Genomics

Instructor: Shaojie Zhang

Lectures: M/W 4:30-5:45pm HEC 118

Office hours: Shaojie Zhang, HEC 311, M/W 3:30-4:30pm or by appointment.


The course should be self-contained. However, a concise introduction to Biology can be found at the Bioinformatics Algorithms web-site (chapter 3). Also, the text of Mol. Biol. of the Cell can be searched online.

This course will summarize computational techniques for comparing genomes on the DNA and protein sequence levels. Topics include state of the art computational techniques and their applications: understanding of hereditary diseases and cancer, genetic mobile elements, genome rearrangements, genome evolution, and the identification of potential drug targets in microbial genomes.

This course is designed for the advanced level computer science graduate students. Graduate students with entry-level background in bioinformatics research (e.g. after taking CAP 5510 or equivalent courses) are welcome to take this course. Biological background students who are interested in comparative genomics are also welcome.


E. Koonin and M. Y. Galperin: Sequence-Evolution-Function: Computational Approaches in Comparative Genomics, Springer, 2002. (COMP). There is online version of this book:Link. We will also distribute complementary lecture notes and papers along the course for these topics.

Dan Gusfild Algorithms on strings, trees and sequences. (ALG) This book covers most of the algorithms we will discuss in the class.

Current research papers (2003-2009) from "Nature", "Science", "PLOS Biology", "Genome Research", "Bioinformatics", and etc. are distributed along the course for different research topics.

Grading: Assignment (15%), Paper presentations (30%), Term project (50%), Attendance (5%).

Summaries Guide Line (for Research Paper Reading and Presentation) Read the paper before lecture. Write a one-page summary of the paper that will be discussed on class. Make sure write down the biological problem and the computational problem hidden inside the paper. Send the summary by email to me before the lecture (3:00 pm sharp)

Paper Presentation Guide Line: Read paper first, meet with me 1-2 weeks before lecture to discuss the paper. Schedule a long meeting with me the day before lecture to discuss the slides. Slides due at noon (sharp) the lecture. Please make the appointments throught emails.

Topics and Tentative Schedule:

Date Topic Slides Book References/Papers Note
L1: 01/07 Course Introduction PDF
L2: 01/12 1. Genome Alignments
1.1 Overview of Sequence Alignment Algorithms
L3: 01/14 1.2 Overview of Sequence Alignment Algorithms (2) PDF COMP 4.4/ALG 11
Smith-Waterman Algorithm
Myers-Miller Algorithm (Linear Space Alignment)
01/19 No Class (Martin Luther King Jr. Day)
L4: 01/21 1.3 Overview of Sequence Alignment Algorithms (3) PDF ALG 14
L5: 01/26 1.4 Overview of Sequence Alignment Algorithms (4) PDF ALG 12.5.2
L6: 01/28 1.5 Genome Alignment Algorithms PDF LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA, Genome Research
L7: 02/022. Genome Rearrangements and Genome Evolutions
2.1 Whole genome duplicatins
PDF Proof and evolutionary analysis of ancient genome duplication in theyeast Saccharomyces cerevisiae, Nature
L8: 02/042.2 Cancer genomicsPDFReconstructing tumor genome architectures, Bioinformatics
L9: 02/092.3 Micro rearrangementsMicroinversions in mammalian evolution, PNAS
L10: 02/113. Whole Genome SequencingFragment assembly with short reads, Bioinformatics
De novo fragment assembly with short mate-paired reads: Does the read length matter?, Genome Research
L11: 02/164. Gene Prediction
L12: 02/185. Gene Regulation and Micro-array
L13: 02/23 6. Repeats in Genomes
6.1 Repeat Identifications
De novo identification of repea families inlarge genomes, Bioinformatics Dan Deblasio
L14: 02/25 6.2 Transposable Elements IdentificationsIdentification of transposable elements using multiple alignments of related genomes, Genome Research Matthew Finch
L15: 03/02 6.3 ALU EvolutionsWhole-genome analysis of Alu repeat elemen reveals complex evolutionary history, Genome Research Erik Ladewig
L16: 03/04 6.4 Genome EvolutionsEvolution's cauldron: Duplication, deletion, and rearrangement in the mouse and human genomes, PNAS Kristin Martin
03/09,11 Spring Break
L17: 03/16 6.5 Cir-regulatory Elements and RetroposonsA distal enhancer and an ultraconserved exon are derived from a novel retroposon
Supplementary Information, Nature
Bo Sun
L18: 03/18 7 Motifs Discovery in Genomes
7.1 Phylo_HMM
Evolutionarily conserved elements invertebrate, insect, worm, and yeast genomes, Genome ResearchGergana Tripoli
L19: 03/23 7.2 Motifs Discovery Through Comparative GenonicsSystematic discovery of regulatory motifs in human promoters and 3' UTRs by comparison of several mammals, NatureSandy Vanderbleek
L20: 03/25 8 Finding Non-coding RNAs in Genomes
8.1 Introduction and RNAz
1. Secondary Structure Prediction for Aligned RNA Sequences, Journal of Molecular Biology
2. Consensus Folding of Aligned Sequences as a New Measure for the Detection of Functional RNAs by Comparative Genomics, Journal of Molecular Biology
3. Fast and reliable prediction of noncoding RNAs, PNAS
4. Mapping of conserved RNA secondary structures predicts thousands of functional noncoding RNAs in the human genome, Nature Biotchnology
L21: 03/30 8.2 EvofoldIdentification and Classification of Conserved RNA Secondary Structures in the Human Genome, Plos Computational BiologyRichard Zhou
L22: 04/01 8.3 MicroRNA Target Prediction (TargetScan)Most mammalian mRNAs are conserved targets of microRNAs, Plos Computational BiologyBrian Williamson
L23: 04/06 8.4 MicroRNA Target Accessibility (Pita)The role of site accessibility in microRNA target recognition, Nature GeneticsYuan Li
L24: 04/08 8.5 RNA motifs in GenomesComputational prediction of RNA structural motifs involved in posttranscriptional regulatory processes, PNASGaoyang Yang
L25: 04/13 8.5 PI-RNAsDiscrete Small RNA-Generating Loci as Master Regulators of Transposon Activity in Drosophila, CellMao Ye
L26: 04/15 9.1 Gene Fusion
9.1 Gene Funsions in Bacterial Genomes
Genes linked by fusion events are generally of the same functional category: A systematic analysis of 30 microbial genomes, PNASCuncong Zhong
L27: 04/20 9.2 Evolution of gene fusionsEvolution of gene fusions: horizontal transfer versus independent events, Genome BiologyAlex Silva
L28: 04/22 No Lecture
L29: 04/27 Class Projects Presentations
05/03 Class Projects Reports Due (11:59pm)
05/04 HEC 118 4:00 pm - 7:00 pm Class Projects Presentations


We are always looking for motivated students. If you are looking for research projects, please get in touch.