Spring 2012 CAP6517: Computational Genomics

Instructor: Shaojie Zhang

Lectures: Tu/Th 3:00-4:15pm BA 220

Office hours: Shaojie Zhang, HEC 311, Tu/Th 2:00 pm - 3:00 pm and 4:30 pm - 5:30 pm 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-2011) on computational genomics are distributed along the course for different research topics.

Paper Summaries and Participations (30%), Paper presentations and Projects (70%).

Paper Summary Guide Line (for Research Paper Reading and Presentations):
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 through UCF webcourese website (2:00 pm sharp).

Paper Presentation Guide Line:
Read paper first, meet with me two weeks before lecture to discuss the paper. Meet with me one week before the lecture to discuss the slides. Slides are due at noon (sharp) before the lecture.

Ethics Statement and Academic Honesty:
As reflected in the UCF creed, integrity and scholarship are core values that should guide our conduct and decisions as members of the UCF community. Plagiarism and cheating contradict these values, and so are very serious academic offenses. Penalties can include a failing grade in an assignment or in the course, or suspension or expulsion from the university.

Some lecture slides are from Serafim Batzoglou of Stanford University (http://ai.stanford.edu/~serafim/courses.html).

Topics and Tentative Schedule:

Date Topic Slides Book References/Papers Note
L1: 01/10 Course Introduction PDF    
L2: 01/12 1 Genome Alignments
1.1 Overview of Sequence Alignment Algorithms
PDF COMP 4.3/ALG 11  
L3: 01/17 1.2 Overview of Sequence Alignment Algorithms (2) PDF COMP 4.4/ALG 11
Smith-Waterman Algorithm
Myers-Miller Algorithm (Linear Space Alignment)
L4: 01/19 1.3 Overview of Sequence Alignment Algorithms (3) PDF ALG 14  
L5 : 01/24
L6: 01/26
1.4 Overview of Sequence Alignment Algorithms (4) PDF ALG 12.5.2  
L7: 01/31 1.5 Genome Alignment Algorithms PDF LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA, Genome Research  
L8: 02/02 2. Genome Rearrangements and Genome Evolutions
2.1 Genome Rearrangements
PDF Towards a Computational Theory of Genome Rearrangements  
L9: 02/07 2.2 Cancer genomics PDF Reconstructing tumor genome architectures, Bioinformatics  
L10: 02/09 2.3 Whole genome duplications PDF Paper 1: Proof and evolutionary analysis of ancient genome duplication in theyeast Saccharomyces cerevisiae, Nature  
L11: 02/14 2.4 Micro rearrangements   Paper 2:Microinversions in mammalian evolution, PNAS  
L12: 02/16 3. Genome Sequencing   Paper 3:De novo fragment assembly with short mate-paired reads: Does the read length matter?, Genome Research  
L13: 02/21 4 Gene Prediciton and Motifs Discovery Through Comparative Genomics   Paper 4:Systematic discovery of regulatory motifs in human promoters and 3' UTRs by comparison of several mammals,Nature  
L14: 02/23 5. RNA-Seq and Splicing
5.1 RNA-Seq
L15: 02/28 5.2 Alternative Splicing   Paper 5:Conservation of an RNA regulatory map between Drosophila and mammals, Genome Research Shawn Hendricks (02/21 4:30pm, 02/23 2:00pm )
L16: 03/01 5.3 Alternative Splicing   Paper 6:Analysis and design of RNA sequencing experiments for identifying isoform regulation, Nature Methods Gregory Morse (02/21 5:00pm, 02/28 4:30pm)
L17: 03/13 5.4 Alternative Splicing   Paper 7:A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome, Science Kevin Pfeil (03/01 2:00pm, 03/08 2:00pm)
L18: 03/15 6 Other NGS applications
6.1 Shape-Seq
  Paper 8:Multiplexed RNA structure characterization with selective 2'-hydroxyl acylation analyzed by primer extension sequencing (SHAPE-Seq),PNAS Gene Sher (03/06 2:00pm, 03/13 2:00pm)
L19: 03/20 6.2 Copy Number   Paper 9: Mapping copy number variation by population-scale genome sequencing, Nature Albert Steppi (03/15 2:30pm, 03/18 3:00pm)
L20: 03/22 6.3 Structural Variation   Paper 10: Simultaneous structural variation discovery in multiple paired-end sequenced genomes, RECOMB 2011 Kecong Tang (03/13 4:30pm, 03/20 4:30pm)
L21: 03/27 7 Metagenomics
7.1 Taxonomic Assignment
  Paper 11: Accurate and fast estimation of taxonomic profiles from metagenomic shotgun sequences, BMC Genomics Qingming Tang (03/20 5:00pm, 03/25 3:00pm)
L22: 03/29 7.2 Metabolic Pathways in Metagenomics   Paper 12:Quantifying environmental adaptation of metabolic pathways in metagenomics, PNAS Shawn Hendricks (03/22 2:30pm, 03/27 2:30pm)
L23: 04/03 7.3 Comparative Metagenomics   Paper 13:UniFrac: a New Phylogenetic Method for Comparing Microbial Communities , AEM Greg Morse (03/27 4:30pm, 03/29 4:30pm)
L24: 04/05 7.4 Targeted Metagenomics   Paper 14:Functional Characterization of the Antibiotic Resistance Reservoir in the Human Microflora, Science Kevin Pfeil (03/25 4:00 pm, 03/29 2:00 pm)
L25: 04/10 7.5 Metagenomics and Energy   Paper 15:Metagenomic Discovery of Biomass-Degrading Genes and Genomes from Cow Rumen, Science Gene Sher (04/05 2:00pm, 04/08 3:00pm)
L26: 04/12 7.6 Gene Prediction   Paper 16:Gene prediction with Glimmer for metagenomic sequences augmented by classification and clustering, NAR Albert Steppi (04/05 2:30pm, 04/10 2:30pm)
L27: 04/17 7.7 Metatranscriptomics   Paper 17: Metatranscriptomics reveals unique microbial small RNAs in the ocean's water column, Nature Kecong Tang (04/10 4:30pm,04/15 3:00pm)
L28: 04/19 8 Population Genetics   Paper 18:Genome-wide patterns of population structure and admixture among Hispanic/Latino populations, PNAS Qingming Tang (04/12 2:30pm,04/17 2:30pm)


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