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:
|L1: 01/07||Course Introduction|
|L2: 01/12||1. Genome Alignments|
1.1 Overview of Sequence Alignment Algorithms
|COMP 4.3/ALG 11|
|L3: 01/14||1.2 Overview of Sequence Alignment Algorithms (2)|| COMP 4.4/ALG 11 |
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)||ALG 14|
|L5: 01/26||1.4 Overview of Sequence Alignment Algorithms (4)||ALG 12.5.2|
|L6: 01/28||1.5 Genome Alignment Algorithms||LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA, Genome Research|
|L7: 02/02||2. Genome Rearrangements and Genome Evolutions|
2.1 Whole genome duplicatins
|Proof and evolutionary analysis of ancient genome duplication in theyeast Saccharomyces cerevisiae, Nature|
|L8: 02/04||2.2 Cancer genomics||Reconstructing tumor genome architectures, Bioinformatics|
|L9: 02/09||2.3 Micro rearrangements||Microinversions in mammalian evolution, PNAS|
|L10: 02/11||3. Whole Genome Sequencing||Fragment assembly with short reads, Bioinformatics |
De novo fragment assembly with short mate-paired reads: Does the read length matter?, Genome Research
|L11: 02/16||4. Gene Prediction|
|L12: 02/18||5. 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 Identifications||Identification of transposable elements using multiple alignments of related genomes, Genome Research||Matthew Finch|
|L15: 03/02||6.3 ALU Evolutions||Whole-genome analysis of Alu repeat elemen reveals complex evolutionary history, Genome Research||Erik Ladewig|
|L16: 03/04||6.4 Genome Evolutions||Evolution'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 Retroposons||A distal enhancer and an ultraconserved exon are
derived from a novel retroposon|
Supplementary Information, Nature
|L18: 03/18||7 Motifs Discovery in Genomes |
|Evolutionarily conserved elements invertebrate, insect, worm, and yeast genomes, Genome Research||Gergana Tripoli|
|L19: 03/23||7.2 Motifs Discovery Through Comparative Genonics||Systematic discovery of regulatory motifs in human promoters and 3' UTRs by comparison of several mammals, Nature||Sandy 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 Evofold||Identification and Classification of Conserved RNA Secondary Structures in the Human Genome, Plos Computational Biology||Richard Zhou|
|L22: 04/01||8.3 MicroRNA Target Prediction (TargetScan)||Most mammalian mRNAs are conserved targets of microRNAs, Plos Computational Biology||Brian Williamson|
|L23: 04/06||8.4 MicroRNA Target Accessibility (Pita)||The role of site accessibility in microRNA target recognition, Nature Genetics||Yuan Li|
|L24: 04/08||8.5 RNA motifs in Genomes||Computational prediction of RNA structural motifs involved in posttranscriptional regulatory processes, PNAS||Gaoyang Yang|
|L25: 04/13||8.5 PI-RNAs||Discrete Small RNA-Generating Loci as Master Regulators of Transposon Activity in Drosophila, Cell||Mao 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, PNAS||Cuncong Zhong|
|L27: 04/20||9.2 Evolution of gene fusions||Evolution of gene fusions: horizontal transfer versus independent events, Genome Biology||Alex 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.