Computational Biology (CS 515)
Course Title: Computational Biology (CS-515)
Quarter: Spring 2009
Analysis of Algorithms (CS-314)
Biological Principles (Bio-101): Recommended
Neil C. Jones, Pavel A Pevzner, An Introduction to Bio-informatics Algorithms, 2004,
The MIT Press (http:// www.bioalgorithms.info).
Instructor: Fatima W. Khwaja and M. Ashraf Iqbal
There has been a revolution in the field of Biology in the last ten years; it has
become a rich source of problems, the solution of which, require the design of smart
algorithms. This interaction between two historically diverse fields requires an
understanding of Biology to computer scientists and an understanding of design and
analysis of algorithms to biologists. The goal of this introductory course in
computational biology is to introduce students (primarily from CS or Mathematics)
to various problems and computational approaches in Biology. We shall discuss
fundamental algorithmic techniques in bioinformatics, including exhaustive search,
dynamic programming, greedy, graph theoretical, and pattern matching algorithms.
A background of an introductory course in Biology is recommended while a good
understanding of algorithms (Analysis of Algorithms (CS314)) is a pre-requisite of
Quizzes & Assignments : 20%
Lecture 1-2: Chapter 3 (Introduction; Molecular Biology Primer;
Programming project assignment)
DNA, Codons, Genes, Transcription, Translation, Proteins
Lecture 3: Chapter 3 (Molecular Biology Primer)
Mechanisms of mutation and evolution, Phylogeny, Species differentiation,
Metabolic pathways, Gene expression, Gene activation, Regulation, and Coregulation
Lecture 4: Project 1 presentations
Lecture 5-6: Chapter 2 (Problem set 1: Algorithms and Complexity)
Correctness, Efficiency, Complexity, & Algorithmic strategies, Tractable vs.
Lecture 7-8: Chapter 4 (Problem set 2: Exhaustive Search)
Tree searching, Restriction mapping, Motif finding.
Lecture 9-10: Chapter 5 (Greedy Algorithms)
Phylogeny, Reversal distance, Breakpoint distance
Lecture 11: Mid-Term
Lecture 12-14: Chapter 6 (Problem set 3: Dynamic Programming Algorithms)
Edit distances, Sequence alignments, Gene prediction
Lecture 15-17: Chapter 7 (Problem set 4: Divide and Conquer Algorithms)
Space-efficient alignment, Sub-quadratic alignment
Lecture 18-19: Chapter 8 (Graph Algorithms)
DNA sequencing, Genome sequencing, Protein sequencing, Spectrum graphs
10. Lecture 20: Revised programming project presentations.
NCBI: An excellent starting point for all sorts of genomic data. Includes the next
four listings below.
LocusLink: The best place to start for gene-specific information. Links to other
gene information: sequences, chromosomal locations, description of function,
homology to other species.
Entrez: Links to many databases: genes, protein structures, population studies.
OMIM: Online Mendelian Inheritance in Man. Detailed, curated text reviews
about diseases and the genes associated with them. Good bibliographic sources
for more references and information.
PubMed: Literature search engine. Gets new references in most biomedical
literature within a month of publication. Often includes links to online copies of
papers (when available).
Genome Browsers / Viewers: (all reachable from top of a LocusLink report)
Golden Path (UCSC) From the University of California at Santa Cruz.
NCBI map viewer Ensembl: From the European Molecular Biology Laboratory
(EMBL); the European counterpart to NCBI. Perhaps a slightly more userfriendly interface than NCBI genome browser. Also has gene structure
AceView: An alternative map viewer good at showing gene structure.
Links to Journals:
General biology journals:
o Nature (see also Nature Genetics, Nature Medicine, and Nature
o PNAS (Proceedings of the National Academy of Sciences)
o Journal of Biology
More specific "Genomics" journals that may have longer computational
o Genome Biology
o Genome Research
o Nucleic Acids Research
o Journal of Computational Biology
o Nucleic Acids Research
o IEEE/ACM Transactions on Computational Biology and Bioinformatics
Organism-Specific Web Resources
Human (Homo sapiens) : OMIM, Genes and Disease
Mouse (Mus musculus) : The Jax (Jackson Laboratories)
Rat (Rattus norvegicus) : Rat genome resource page
Fruit fly (Drosophila melanogaster) : BDGP: (Berkeley Drosophila
Worm (Caenorhabditis elegans) : Wormbase
Yeast (Saccharomyces cerevisiae) : SaccDB
Protein Data Bank (PDB) of solved protein structures.
SWISSPROT Protein sequence database.
SCOP a hierarchal classifier of solved protein structures from Chothia's group
CATH another hierarchical classifier of solved protein structures, from Thorton's
FASTA for sequence similarity and homology search.
BLAST for sequence similarity and homology search.