Spring 2011 CAP6938: Special Topics in Computational Genomics

Instructor: Shaojie Zhang

Lectures: M/W 12:00-1:15pm HPA 117

Office hours: Shaojie Zhang, HEC 311, M/W 2:00 pm - 3: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-2010) from "Nature", "Science", "PLOS Biology", "Genome Research", "Bioinformatics", and etc. are distributed along the course for different research topics.

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

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 by email to me before the lecture (12:00 pm sharp)

Paper Presentation Guide Line:
Read paper first, meet with me 2 weeks before lecture to discuss the paper. Meet with me 3-5 days before the lecture to discuss the slides. Slides are due at noon (sharp) before the lecture. Please make the appointments through emails.

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.

Topics and Tentative Schedule:

Date Topic Slides Book References/Papers Note
L1: 01/10 Course Introduction PDF
L2: 01/12 1.1 Genome Alignments
1.1 Overview of Sequence Alignment Algorithms
01/17 No Class (MLK Day)
L3: 01/19 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/24 1.3 Overview of Sequence Alignment Algorithms (3) PDF ALG 14
L5,L6 : 01/27 and 01/31 1.4 Overview of Sequence Alignment Algorithms (4) PDF ALG 12.5.2
L7: 02/02 1.5 Genome Alignment Algorithms PDF LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA, Genome Research
L8: 02/072. Genome Rearrangements and Genome Evolutions
2.1 Genome Rearrangements
PDF Towards a Computational Theory of Genome Rearrangements
L9: 02/092.2 Cancer genomicsPDFReconstructing tumor genome architectures, Bioinformatics
L10: 02/142.3 Whole genome duplications PDF Paper 1: Proof and evolutionary analysis of ancient genome duplication in theyeast Saccharomyces cerevisiae, Nature
L11: 02/162.4 Micro rearrangementsPaper 2:Microinversions in mammalian evolution, PNAS
L12: 02/213. Whole Genome SequencingPaper 3:De novo fragment assembly with short mate-paired reads: Does the read length matter?, Genome Research
L13: 02/23 4 Gene Prediciton and Motifs Discovery Through Comparative GenomicsPaper 4:Systematic discovery of regulatory motifs in hu man promoters and 3' UTRs by comparison of several mammals, Nature
L14: 02/284.2 Gene PredictionPaper 5:Sequencing and comparison of yeast species to identify genes and regulatory elements Akanksha Baharani
L15: 03/025. Repeats in Genomes
5.1 Repeat Identifications
Paper 6:De novo identification of repea families inlarge genomes, Bioinformatics Susmita Biswas
L16: 03/145.2 Segmental DulicationsPaper 7:DupMasker: A tool for annotating primate segmental duplications, Genome ResearchUrmi Chakraborty
L17: 03/165.3 TransposonsPaper 8:Next-generation VariationHunter: combinatorial algorithms for transposon insertion discovery BioinformaticsNandita Dhatrika
L18: 03/21 6. RNA-Seq and Splicing
6.1 RNA-Seq
L19: 03/23 6.2 Alternative SplicingPaper 9:Conservation of an RNA regulatory map between Drosophila and mammals, Genome Research Jun Ding
L20: 03/28 6.3 Alternative SplicingPaper 10:Analysis and design of RNA sequencing experiments for identifying isoform regulation, Nature Methods Claire Ferguson
L21: 03/30 6.4 Splicing MotifPaper 11: Ab initio identification of functionally interacting pairs of cis-regulatory elements , Genome Research Michelle Fox
L22: 04/04 7 Noncoding RNA
7.1 Introduction
L23: 04/06 7.2 LincRNAPaper 12:Ab initio reconstruction of cell type specific transcriptomes in mouse reveals the conserved multi-exonic structure of lincRNAs, Nature Biotechnology Andrew Miller
L24: 04/11 7.3 ncRNAPaper 13: Prediction and characterization of non-coding RNAs in C. elegans by integrating conservation, secondary structure and high throughput sequencing and array data , Genome Research Stephen Raabe
L25: 04/13 7.4 miRNAPaper 14:Deep annotation of Drosophila melanogaster microRNAs yields insights into their processing, modification, and emergence, Genome Research Amy Hoover
L26: 04/18 7.5 Chop-SeqPaper 15: Genome-wide measurement of RNA secondary structure in yeast, Nature Ying Wang
L27: 04/20 7.6 RNA Elements Paper 16:Premature terminator analysis sheds light on a hidden world of bacterial transcriptional attenuation, Genome Biology Lingfei Zhi
L28: 04/25 8 Population GenomicsPaper 17: A map of human genome variation from population-scale sequencing, Nature Group Discussion


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