BMI 214 / CS 274 (Spring 2005)

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

Spring 2005

Note this is not the current year website, this is for archival purposes only. Click here for the current year's website.

Lectures: Tuesday and Thursdays 2:45pm-4pm in Thornton 102
Sections: Fridays 10:00am-10:50am in Skilling 193 (Live on E3)
Internet: BMI 214 Course by streamed Internet video online on Stanford Center for Professional Development

Table of Contents

Announcements

Homeworks

Class Schedule

General Course Information

Announcements

May 3:: The final will be available from noon, Monday, June 6 to midnight, Tuesday, June 7.
March 28:: The schedule and itinerary for Friday sections has been posted here
March 22:: We have a short guide to help you choose a language for the programming projects.
March 21:: Late Policy
April 15:: The extra credit assignment has been removed from the "Homeworks" list and is under consideration.

How to sign up for this course:: (1) If you decide to take BMI 214 this quarter, please sign up for this course on AXESS as soon as possible. This is the only way to join the class email list, which will be our primary method of communication!; (2) In addition, you will need a CWP account to access the on-line materials. Again, please sign up for the course on AXESS as soon as possible and we will set up a CWP account for you. You will need it by April 4th to complete Assignment 0. (Alternatively, you can sign up at CWP. Choose the "Apply for Account" option on the left, and make sure to note that your reason for interest is BMI214 / CS274). If you already have a CWP account that you would prefer to use, email the staff list and we will add that account.

Homeworks

Students will need to use CWP to complete homeworks. See "how to sign up for the course" above.

	Topic	Out	Due
Assignment 0	Class Survey	Tues., March 29, 2005	midnight, Mon., April 4, 2005
Assignment 1	Internet Resources	Tues., March 29, 2005	midnight, Wed., April 6, 2005
Assignment 2	Sequence Alignment and Classification	Wed., April 6, 2005	midnight, Wed., April 13, 2005
Project 1 (Instructions)	Sequence Alignment	Tues., March 29, 2005	midnight, Wed., April 20, 2005
Project 2 (Instructions)	K Nearest Neighbors	Tues., April 19, 2005	midnight, Wed., May 4, 2005
Assignment 3	HMMs, RNA folding, and 1D motif finding	Sun., May 8, 2005	midnight, Sun., May 15, 2005
Assignment 4	Phylogenetics and Gene Finding	Fri., May 20, 2005	midnight, Fri., May 27, 2005
Project 3 (Instructions)	3D Structure and Function	Wed., May 18, 2005	midnight, Wed., June 1, 2005

Class Schedule

Date	Topic	Lecturer	Lecture Notes	Required Readings and Other Info
Mar. 29, 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
Mar. 31, Thurs.	Dynamic Programming Sequence Alignment	Altman	b/w, color	Mount Readings: Chapter 3 & pp 122-147, 240-259 Smith-Waterman implemented in hardware (Kestrel) Brief Historical and Technical Review of BLAST BLAST search engine FASTA search engine Online collection of classic articles (optional): Gotoh, 1982; Gribskov &Devereux, 1994; Needleman & Wunsch, 1970
April 5, 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 7, Thur.	Microarrays, Clustering and Classification	Altman	b/w, color	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 Useful list of support vector machine applications in Bioinformatics Comprehensive tutorial on support vector machines by Burges (1998) Paper on correlation of spotted arrays and oligonucleotide arrays Introduction to logistic regression
April 12, 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 Distance Geometry Description Online collection of classic articles (optional): Gerstein & Levitt; Nussinov & Wolfson; Subbiah.
April 14, Thurs.	Multiple Sequence Alignment and Genome Alignment	Altman	b/w, color	Mount Readings: pp 163-188 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 Server for Gibbs Sampling Bioprospector paper by X. Liu, J.S. Liu & D. Brutlag Chip Lawrence page on Gibbs Sampling Comprehensive and detailed online GIBBS tutorial from Chip Lawrence 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)
April 19, Tues.	1D Motifs and Hidden Markov Models	Altman	b/w, color	Mount Readings: pp 189-214 Optional textbook: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield, 1997, Cambridge University Press. BLOCKS database Making BLOCK motifs PROSITE database Online collection of classic articles (optional): Henikoff & Henikoff, 1992 MEME system for motif definition and search Information about and examples of Sequence Logos The TRANSFAC database of transcription factors and their motifs Grant & Ewens excerpt. PDF will be emailed to student list. 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)
April 21, Thur.	HMM & Gibbs Sampling	Altman	b/w, color	Mount Readings: Chapter 11
April 26, Tues.	Genome analysis, Hapmap, SNPs, haplotypes	Altman	b/w, color	Mount Readings: Chapter 8 Hapmap Project Overview of Haplotype inferencing algorithms
April 28, Thurs.	RNA secondary structure	Altman	b/w, color	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 3, Tues.	Systems Biology	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
May 5, Thurs.	Molecular energetics and dynamics	Altman	b/w, color	Bower & Bolouri excerpt. PDF available here (password required). Online collection of classic articles (optional): Richards, 1991. 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 10, Tues.	Protein structure prediction I	Altman	b/w, color	Mount Readings: pp 410-434, 444-467 Bourne et al readings: Ch 25, 26, 27 Summary of 2002 CASP (Special issue devoted to CASP) CASP6 Web site Good review of homology modeling Special Issue of PROTEINS Devoted to CASP IV 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
May 12, Thurs.	Protein structure prediction II	Altman	b/w, color	Mount Readings: pp 468-487 Bourne et al readings: Ch 25, 26, 27 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
May 17, Tues.	Phylogenetics	Altman	b/w, color	Mount Readings: Chapter 7 Phylip: Phylogenetic Inference Package Tree of Life Web Project Samples from the Tree of Life Ribosomal Database Project MaClade program for analyzing character based trees Software for drawing phylogenetic trees Online collection of classic articles (optional): Doolittle et al. Online collection of classic articles (optional): Thorne et al. Paper on estimating sequence divergence by comparative analysis (Cooper et al)
May 19, Thurs.	Proteomics	Altman	b/w, color	Mount Readings: pp 511-515 Altman Lab WebFEATURE Introduction to Mass Spectrometry Another Introduction to Mass Spectrometry Mass Spectrometry Web Resources List of 2D PAGE Databases Swiss 2D PAGE Gel Database 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 Mutation-Tolerant Protein Identification by Mass Spectrometry Computational aspects of protein identification by mass spectrometry
May 24, Tues.	Natural Language Processing I	Altman	b/w, color	Nice description of Brill Part-of-Speech Tagger (postscript) Related Articles description in PubMED Unified Medical Language System Medical Entity Subject Heading (MESH) Browser List of words distinguishing malaria literature from yeast literature Documentation for PROSITE database (PRODOC) Natural Language Processing papers at PSB meeting 2000 Natural Language Processing papers at PSB meeting 2001 Natural Language Processing papers at PSB meeting 2002 Description of Porter Stemming algorithm Accomplishments and Challenges in Literature Data Mining for Biology. Password required. Text Mining for Metabolic Pathways, Signaling Cascades, and Protein Networks. Password required.
May 26, Thurs.	Natural Language Processing II	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
May 31, Tues.	Final Thoughts	Altman	b/w, color	Link to FDA overview of drug development and approval process 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

General Course Information

|| Staff

|| Discussion Groups

|| Description

|| Units

|| Grading

|| Exams

|| Late Policy

|| Partner Policy

|| Auditors

|| Prerequisites

|| Computer Resources

|| Textbook

|| Note on courses ||

Instructor:

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

Course Coordinator:

Tiffany Jung
Department of Genetics
Lane L301, MC: 5120
650-725-0659

Teaching Assistants:

Jessie Tenenbaum
Office Hours: Tuesday 1:30-2:30pm at MSOB (directions)
Diane Schroeder
Office Hours: Monday 3-4pm at MSOB (directions)

Discussion Groups:(top)

Mailing Lists

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

students: bmi214-spr05-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.

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 instructors.
A lecture-only, no assignment participation may be taken for 1 unit by arrangement with instructors. Students must attend all lectures, absences must be approved by the instructors. 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%, both take home, open book).

Exams: (top)

Midterm: available April 26-27; details to be announced.
Final: available from noon, Monday, June 6 to midnight, Tuesday, June 7.

Late Policy: (top)

Each student is granted 7 "free" late days that can be used as extensions for any project, assignment or exam (exceptions: Midterm Exam can have a max of 1 late day, Final Exam can have a max of 0 late days). 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. No late day is allowed after Final Exam.

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. Java, C, C++, Perl, Python, and Lisp have all been used successfully by students in the past.

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 and the Web to access assignments. All of these resources are available to Stanford students at Sweet Hall and elsewhere. Most course material will be placed on the WWW 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.

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.
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.