BMI 214 / CS 274 (Spring 2006)

Biomedical Informatics 214 (also listed as Computer Science 274)
Representations and Algorithms for Computational Molecular Biology

Spring 2006

Lectures: Tuesdays and Thursdays 2:45pm-4pm in Thornton 102
Sections: Fridays 10:00am-10:50am in Skilling 193 (Live on E3). Sections will not be held every week. Watch the schedule below and the class emails for information on sections dates and topics.
Internet: BMI 214 Course by streamed Internet video online on Stanford Center for Professional Development

Table of Contents

General Course Information

Announcements

June 1:: Please note room change.
Final: Monday, June 12 7-8:30pm in Gates B03, open notes, but no Internet allowed.

May 30:: Biomedical Informatics Industry Night
Wednesday, May 31, 6-8PM
Only 30 spaces available, so RSVP to peiting@stanford.edu ASAP! First come, first served.
Click here for more information.
Announcement Archive

Homeworks

E-mail all questions about projects and assignments to the staff list: biomedin214-spr0506-staff@lists.stanford.edu

The dropbox, where you can pick up graded assignments if you missed getting them at class, is located at X-215, on the second floor of MSOB (Medical School Office Building).

	Topic	Out	Due
Assignment 0	Questionnaire	Tues., April 4, 2006	5pm, Mon., April 10, 2006
Assignment 1	Exploring information on the Internet PDF Word file	Tues., April 4, 2006	5pm, Mon., April 10, 2006
Project 1	Sequence Alignment Instructions Alignment files: examples, for quiz Quiz: pdf, doc Grading point breakdown	Thurs, April 6, 2006	5pm, Mon, April 17, 2006
Project 2	Microarray Clustering/Classification Instructions Quiz: pdf, doc	Friday, April 14, 2006	5pm, Wed, April 26, 2006
Assignment 2	Weka and Genotype-Phenotype: pdf, doc Data files	Friday, April 21, 2006	5pm, Wed, May 3, 2006
Project 3	3D Structure and Function Instructions \| Files Quiz (doc \| PDF)	Thurs, April 27, 2006	5pm, Mon, May 15, 2006
Assignment 3	Sequence Analysis Algorithms: pdf, doc Sequence file	Tues, May 9, 2006	5pm, Mon, May 22, 2006
Project 4	Molecular Dynamics: Instructions \| Files Quiz ( doc \| PDF) Survey ( doc \| PDF)	Monday, May 15, 2006	5pm, Wed, May 31, 2006

Class Schedule

Date	Topic	Lecturer	Lecture Notes	Required Readings and Other Info
April 4, Tues.	Introduction to Bioinformatics and Computational Genomics	Altman	b/w, color	Mount Readings: Chapter 1 & pp 30-40 Short paper on CS & Bioinformatics Databases mentioned in lecture: GenBank, Swiss-Prot, PDB, PubMed, Microarray DB Human Genome Browsers: Ensembl, UC Santa Cruz, NCBI Introductory Biology Resources: 1. Basic Biology Primer (short intro to sequence in biology); 2. Introduction to Biology for Computer Scientist (especially first chapter of Hunter book); 3. Protein Architecture; 4. Introduction to DNA structure (Web tutorial); 5. Introduction to Genetics; 6. Glossary of Genetic Terms; 7. Overview of Human Genome Project goals The field of bioinformatics: Curriculum for Bioinformatics; Bioinformatics and Molecular Medicine Kinemages for biological structure (need MAGE software) DNA kinemage; Protein Backbone Kinemage; Betasheet Kinemage Kinemages from Lecture: proteinbbone.kin, foo.kin, helix.kin, bar.kin, HBlesson.kin, protour1.kin, pdb1rbp2.kin, protour2.kin, protour4.kin, protour5.kin, dna.kin, NATour1.kin Amino Acid Properties Web Page Studying statistical properties of regulatory DNA sequences, and their use in predicting regulatory regions in the eukaryotic genomes
April 6, Thurs.	Dynamic Programming Sequence Alignment	Altman	b/w, color	Mount Readings: Chapter 3 & pp 122-147, 240-259 Needleman-Wunsch global aignment (1970) Gotoh alignment speedup article (1982) Gribskov and Devereux's Sequence Analysis Primer (1994). Password required. We will email this information to the class; if you do not receive it, please email biomedin214-spr0506-staff@lists.stanford.edu. Smith-Waterman implemented in hardware (Kestrel) Brief Historical and Technical Review of BLAST (paper). Password required. BLAST search engine FASTA search engine Online collection of classic articles (optional): Gotoh, 1982; Gribskov &Devereux, 1994; Needleman & Wunsch, 1970 Database searching with DNA and protein sequences: An introduction
April 11, Tues.	Intro to Microarrays	Altman	b/w, color	Mount Readings: Chapter 13 Stanford Microarray Database Whole-genome expression analysis: challenges beyond clustering (paper) Basic microarray analysis: grouping and feature reduction (paper) Paper on lung cancer
April 13, Thur.	Microarrays, Clustering and Classification	Altman	b/w, color	Mount Readings: p 519-525 Gene Ontology Site GO Termfinder (also see HELP) Hypergeometric Distribution Information Weka machine learning software Paper on estimating missing values in microarray data Eisen Hierarchical Clustering paper Tamayo Self-Organizing Maps paper Brown Support Vector Machine paper Comprehensive tutorial on support vector machines by Burges (1998) (PDF) Paper on correlation of spotted arrays and oligonucleotide arrays Machine learning in bioinformatics Putting microarrays in a context: Integrated analysis of diverse biological data
April 18, Tues.	Basic 3D computation, and structural alignment	Altman	b/w, color	Mount Readings: pp 435-444 Recent Review on Structural Genomics Arun, Huang, and Blostein article (optional) SCOP Server DALI Server LOCK Server MUSTA algorithm for geometric hashing and multiple alignment NMR Structure Determination Xray Crystallography Structure Determination Online collection of classic articles (optional): Gerstein & Levitt; Nussinov & Wolfson; Subbiah.
April 20, Thurs.	Genome, Hapmap, SNPs, Phenotypes	Altman	b/w, color	Mount Readings: Chapter 8 Hapmap Project Overview of Haplotype inferencing algorithms dbSNP PharmGKB Bioinformatics approaches and resources for single nucleotide polymorphism functional analysis Linkage disequilibrium for different scales and applications
April 25, Tues.	Multiple sequence alignment	Altman	b/w, color	Mount Readings: pp 163-188 and pp 189-214 Optional textbook: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield, 1997, Cambridge University Press. Boehringer Metabolic Chart (online) Short and useful discussion of sequence weighting MSA algorithm descriptions Multiple Sequence Alignement server (ClustalW) at EBI ClustalW server Another ClustalW server BLOCKS database Making BLOCK motifs PROSITE database Online collection of classic articles (optional): Henikoff & Henikoff, 1992 Information about and examples of Sequence Logos The TRANSFAC database of transcription factors and their motifs The many faces of sequence alignment
April 27, Thurs.	1D motifs, Gibbs Sampling	Altman	b/w, color	Mount Readings: Chapter 11 Grant & Ewens excerpt. PDF available here (password required). Other Tutorial Material on HMMs from Bioinformatics Conference ISMB Excellent Introduction Tutorial by Rachel Karchin on HMMs PFam resource for protein family classification Profile Hidden Markov Models (HMMer from Eddy lab)
May 2, Tues.	Hidden Markov Models	Altman	See notes from April 27.	Mount Readings: Chapter 11 Grant & Ewens excerpt. PDF available here (password required). Other Tutorial Material on HMMs from Bioinformatics Conference ISMB Excellent Introduction Tutorial by Rachel Karchin on HMMs PFam resource for protein family classification Profile Hidden Markov Models (HMMer from Eddy lab) HMM-based databases in InterPro
May 4, Thurs.	3D motifs & Proteomics	Altman	b/w, color	Mount Readings: pp 511-515 Paper on Fuzzy Functional Forms Paper on TESS Altman Lab WebFEATURE Description of basic 3D motif techniques 3D motifs used for creating a sequence alignment match matrix 3D motifs used for recognizing sites in proteins 3D motifs used to compare amino acid environments Paper on recognizing calcium binding in structure decoys Database of Interacting Proteins Automated protein function prediction--the genomic challenge. PubMed 16772267 Inferring network interactions within a cell Extraction of biological interaction networks from scientific literature Biomolecular Interaction Network Database High-quality protein knowledge resource: SWISS-PROT and TrEMBL PROSITE: A documented database using patterns and profiles as motif descriptors InterPro: An integrated documentation resource for protein families, domains and functional sites
May 9, Tues.	RNA secondary structure & Phylogenetics	Altman	b/w, color	M. Kanehisa, Post-Genome Informatics, (Cary, NC: Oxford University Press, March 15, 2000), 104-120. PDF available here (password required). Modeling and Simulation of Genetic Regulatory Systems Pacific Symposium on Biocomputing, session on Gene Networks 1998 Pacific Symposium on Biocomputing, session on Gene Networks 1999 Pacific Symposium on Biocomputing, session on Gene Networks 2000 KEGG database of genes and gene pathways/networks EcoCYC database of metabolic pathways in E. Coli Recent Review of EGF-signal pathway modeling Example Bayes Net approach to modeling in cell signalling Optional Reading, Durbin & Eddy, Chapters 9 & 10 on grammars and RNA. VMD display software The RNA World Michael Zuker's RNA Folding Server Structural Classification of RNA
May 11, Thurs.	Systems biology: qualitative networks	Altman	b/w, color	SBML Description Article SBML.org Systems Biology Markup Language Site Systems Biology Model Repository, CellDesigher Software, SBML Models Biological Pathways Exchange: BioPAX Biomodels collection at EBI "Pathblast" paper by Kelley, Sharan, et al. Password required. M. Kanehisa, Post-Genome Informatics, (Cary, NC: Oxford University Press, March 15, 2000), 104-120. PDF available here (password required). Modeling and Simulation of Genetic Regulatory Systems Pacific Symposium on Biocomputing, session on Gene Networks 1998 Pacific Symposium on Biocomputing, session on Gene Networks 1999 Pacific Symposium on Biocomputing, session on Gene Networks 2000 KEGG database of genes and gene pathways/networks EcoCYC database of metabolic pathways in E. Coli Recent Review of EGF-signal pathway modeling Example Bayes Net approach to modeling in cell signalling Computational aspects of systematic biology Unsupervised pattern recognition: An introduction to the whys and wherefores of clustering microarray data Clustering-based approaches to discovering and visualising microarray data patterns
May 16, Tues.	Molecular energetics and dynamics	Altman	b/w, color	Bower & Bolouri excerpt. PDF available here (password required). Online collection of classic articles (optional): Richards, 1991. Vijay Pande's Folding@Home project Reference: Branden & Tooze book " Introduction to Protein Structure" MPEG of DNA/protein complex molecular dynamics MPEG of closeup of DNA/protein complex, with hydrogen bonds. Online review of protein energetics Lattice models of proteins (Pande Group, Stanford) IBM "Blue Gene" computer for protein folding Advanced reviews of molecular dynamics: Computer Simulations with Explicit Solvent and Molecular Dynamics Simulations of Biomolecules Gallery of molecular dynamics movies
May 18, Thurs.	Protein structure prediction I	Altman	b/w, color	Mount Readings: pp 410-434, 444-467 Bourne et al readings: Ch 25, 26, 27 Special issue of PROTEINS devote to CASP6 CASP6 Web site Good review of homology modeling CASP Web site for protein structure prediction EMBL protein structure prediction server UCLA protein structure prediction server Modeller Program for structure prediction Web site Guide to protein structure prediction for biologists Review of the Rosetta Method for ab initio prediction Description of Rosetta method for assembly fragments into rough structures Protein 3D structural data — where it is, and why we need it ProDom: Automated clustering of homologous domains
May 23, Tues.	Protein structure prediction II	Altman	Please see slides from Thursday, May 18.	Mount Readings: pp 468-487 Bourne et al readings: Ch 25, 26, 27
May 25, Thurs.	Comparative genomics	Altman	b/w, color	PSB 2002 Session on Comparative Genomics PSB 2003 Session on Comparative Genomics Comparative genomics "fact sheet" from Human Genome Project Letter on incorrect use of the term "synteny" Batzoglou et al paper on large scale alignment (GLASS) and comparative gene finding (ROSETTA) Kent et al paper describing WABA for large scale alignment Pellegrini et al paper on protein phylogenetic profiles Marcotte et al paper on protein fusion method for function prediction Mayor et al paper on VISTA visualization of genome comparisons VISTA tool for browsing comparative genomes Marcotte et al paper on combining multiple types of protein-protein interaction evidence LAGAN and MLAGAN for genome alignment Link to Stanford LAGAN and MLAGAN Programs (Batzoglou group)
May 30, Tues.	NLP in biology	Altman	b/w, color	Abstract of review by Stevens R, Goble CA, Bechhofer S. PDF of full report is available here. Password required. Gene Ontology Web site The Tambis Project Original paper introducing Gene Ontology (GO) Paper describing GO translation into Frame-based System Freely available frame-based system for building ontologies (Protege-2000) Overview of RiboWEB Project EcoCYC knowledge base of E. Coli metabolism Description of UMLS Semantic Network International Society for Computational Biology ISMB 2003 Conference (Brisbane, Australia) ISMB/ECCB 2004 Conference (Glasgow, Scotland) RECOMB 2004 Conference (San Diego, California) Pacific Symposium on Biocomputing 2005 (Maui) Bioinformatics Journal J. Computational Biology Briefings in Bioinformatics Stanford BITS Faculty BCATS Conference for 2004 Russ' links to some bioinformatics books Biomedical Informatics Training Program Trec Genomics Track (CASP-like eval) Nature blog on OTIM OTIM sample file What makes a gene name? Named entity recognition in the biomedical literature Evaluation of biomedical text-mining systems: Lessons learned from information retrieval
June 1, Thurs.	NLP in biology con't	Altman	b/w, color
June 6, Tues.	Final wrap up	Altman	b/w, color	Followup on Genghis Khan BioMOBY: An open source biological web services proposal

Section

Sections are held on Fridays, 10-11AM in Skilling 193 . Sections are scheduled as needed; they will not be held every week. The schedule below will be updated with dates and topics throughout the quarter.

Date	Topic	TA	Notes
April 7	Python tutorial	Lucy Southworth	Python notes
April 14	Introduction to biology	Shirley Wu	Lecture slides
April 21	General Q&A (not televised)	Maureen Hillenmeyer
June 9	Final exam review	All

General Course Information

|| Staff

|| Discussion Groups

|| FAQ

|| Description

|| Units

|| Grading

|| Exams

|| Late Policy

|| Partner Policy

|| Auditors

|| Prerequisites

|| Computer Resources

|| Code Policy

|| Textbook

|| Note on courses ||

Instructor:

Russ B. Altman
Professor of Genetics, Bioengineering, & Medicine (and Computer Science by courtesy)
russ.altman at stanford.edu

Course Coordinator:

Tiffany Murray (tiffany.murray at stanford.edu)
Department of Genetics
Lane L301, MC: 5120
650-725-0659

Teaching Assistants:

Maureen Hillenmeyer (maureenh at stanford.edu)
Office Hours: Thursday, 4:15-5:15pm, Lusted Library, MSOB X-215 (directions)
Lucinda Southworth (lucindas at stanford.edu)
Office Hours: Wednesday, 3-4pm, BMI student lounge, MSOB X-215 (directions)
Shirley Wu (shwu19 at stanford.edu)
Office Hours: Monday, 1-2pm, BMI student lounge, MSOB X-215 (directions)

Discussion Groups:(top)

Mailing Lists

staff: biomedin214-spr0506-staff@lists.stanford.edu
(This is the best way to reach us.)

students: biomedin214-spr0506-students@lists.stanford.edu
This list is automatically populated nightly with the list of students currently registered on Axess. You will be automatically added to the list after you have registered on Axess. It will be used by staff to send course-related announcements.

Newsgroup
To subscribe to the class newsgroup, su.class.biomedin214, log on to the news server nntp.stanford.edu. This is a great way to communicate with your peers, set up study groups, etc.

FAQ: (top)

Please read the Frequently Asked Questions prior to sending questions to the course staff.

Description: (top)

This course will introduce the basic computational issues and methods used in molecular biology, combining core lectures, programming assignments, with midterm and final. The course will introduce and use biological data sources available on the World Wide Web. Topics will include basic algorithms for alignment of biological sequences and structures, as well as more advanced representational and algorithmic issues in structure and sequence computation. These include, for example, dynamic programming algorithms for alignment, structural superposition algorithms, computing with distance information, 3D motif definition and computation, hidden Markov models, phylogenetic trees, statistical feature detection, genetic algorithms, design of data resources, automated analysis of biological literature, database integration, and collaborative environments for supporting biology.

Units:(top)

This course is normally taken for 4 units.
It can be taken for 3 units by arrangement with instructor.
A lecture-only, no assignment participation may be taken for 1 unit by arrangement with instructor. Students must attend all lectures, absences must be approved by the instructor. Enroll in BMI 216.

Grading: (top)

The course will be graded by performance on short homeworks (approximately 30%), long projects (approximately 50%), midterm and final (approximately 20%).

Exams: (top)

Midterm: Monday, May 8 8-9:30pm in Thornton 102, open notes, but no Internet allowed.
Final: Monday, June 12 7-8:30pm in Gates B03, open notes, but no Internet allowed.

Late Policy: (top)

Each student is granted 7 "free" late days that can be used as extensions for any project or assignment. Late days will be measured in 24-hour/day calendar days with no distinction for weekends or holidays, and will be rounded UP to the nearest integer (thus, 10 minutes late = 23 hours late = 1 day late). After you use up all your free days, your grade on late projects/assignments/exams will be reduced 10% for each late day. Extensions beyond the 7 free days may be granted at the discretion of the instructor (not the TAs) and must be requested prior to the due date.

Partner Policy: (top)

For assignments:
Students may discuss and work on problems in groups but must write up their own solutions. When writing up the solutions, students must write the names of people with whom they discussed the assignment.
For programming projects:
Students may discuss ideas with others. However, programs are to be completed independently and should be original work. Code may not be shared. Names of students with whom programming ideas were discussed should be included with assignment.

Auditors: (top)

Auditors for the course should take it for one unit as BMI 216. This course requires attendance at lectures, sign-in at each lecture (approval for missing a lecture), but does not require completion of homeworks or tests. It is for one unit, received for attending all lectures.
Auditors who want to sit-in on the course but not be officially signed up for 1 unit of credit should get approval from Dr. Altman, and will also be asked to attend all lectures, sign-in, and not do the homeworks or tests.

Prerequisites: (top)

Programming skills are required at the level of CS106A/CS106B or CS106X. This course has a significant component of programming, and so students should enter it with ability to create moderately complex data structures, and implement algorithms using these data structures. Acceptable languages are outlined in the code policy.

Biology 40 or equivalent is recommended, since we will quickly move through many biology topics. It may be useful to have a textbook of molecular biology for reference during the course, for those who do not think about biology very much. We will have TA sessions devoted to biology brush-up.

Computer Resources: (top)

You will need to have access to email (be sure you're registered on Axess so that you get email announcements sent to the course list), the course website, and the Stanford elaine machines. All of these resources are available to Stanford students at Sweet Hall and elsewhere. (See http://www.stanford.edu/services/cluster/ and http://www.stanford.edu/services/cluster/which.html for more information on various campus machines.) Most course material will be placed on the course website in *.pdf (Adobe Acrobat) format, which allows the documents to be read on multiple platforms. Readers are available for free for Windows, Macintosh and many Unix platforms at the Adobe website.

Code / Language Policy: (top)

Familiarize yourself with the Code/Language Policy before choosing a language and starting the first programming assignment.

Recommended Course Textbook: (top)

Mount, D.W., Bioinformatics : sequence and genome analysis. 2nd edition (July, 2004), Cold Spring Harbor Laboratory Press. ISBN: 0879696877.
Optional readings will be suggested from this textbook throughout the course, and it covers approximately 70% of the material in the course. Available at the Stanford Bookstore. Copies on reserve at the Lane Medical Library and Math/CS library.
Other Recommended books that are more focused:
Kohane, I.S., Kho, A., Butte, A.J., Microarrays for an Integrative Genomics (Computational Molecular Biology). 2002, MIT Press. ISBN: 026211271X.
Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G., Biological Sequence Analysis : Probabilistic Models of Proteins and Nucleic Acids. 1999, Cambridge Univ Pr. ISBN: 0521629713
Bourne, P.E., Weissig, H. (editors), Structural Bioinformatics. 2004, John Wiley & Sons. ISBN: 0471201995. This book is also available from the Wiley Interscience website at http://www3.interscience.wiley.com/cgi-bin/homepage/?isbn=0471721204 via the campus network.
We also suggest students to read through the classic articles available at http://hrst.mit.edu/hrs/bioinformatics/public/PrimarySite.html. Click on the link to "Classic Papers in the field of Bioinformatics Collection, curated by Russ B. Altman."

Note on courses in computational biology: (top)

BMI 214 (also listed as CS 274) is this course. It has been taught since 1996 and is an introduction to representations and algorithms for analysis of sequence, structure and function. It requires programming skills and aims to give an understanding of the biological problems that arise, and how algorithms are developed to address them. It does not train students to be expert users of tools, but gives them an in-depth knowledge of some tools and a broad introduction to the technical issues in analysis of biological data. It is taught live on Tuesdays/Thursdays and is also on Stanford Online. Section is taught on Friday mornings.
Biochem 218 (also listed as BMI 231) is Doug Brutlag's course introducing computational molecular biology, also a number of years old. It is more geared towards gaining an expert understanding of existing tools and databases, and as such complements BMI 214 very nicely. There is no programming required. Most students take both eventually and learn a lot--even the areas where there is overlap are presented differently enough to round out one's understanding. For logistical reasons this course is also being taught on Tuesday/Thursday, and is on Stanford Online.
CS 262 (Computational Genomics) is Serafim Batzoglou's course. It focuses principally on algorithms for sequence assembly, analysis and comparison. It will have a strong CS algorithms and data structures component, probably with an element of software engineering as well. It is likely to complement both courses, although in the future, about 1/3 of BMI 214 may overlap sufficiently to require coordination--the part about sequence and string analysis. The coordination has not been done as of now, however. It does not contain much on 3D structure computation and functional computing, judging from the syllabus. The course will be taught live. You should ask Prof. Batzoglou about his plans to offer it via Stanford Online.