Fall 2018 / DM847
Introduction to Bioinformatics

General Information

Course introduction

The purpose of this course is to give an understanding of computational problems in modern biomedical research. We will start with concrete medical questions, develop a formal problem description, setup an algorithmic/statistical model, solve it and subsequently derive real-world answers from within the solved model. The course aims for giving a basic understanding of which problems arise in modern molecular biology and clinical research, and how these problems can be solved with appropriate computational tools. It is a class that needs regular attendance. Precondition for admittance to the exam will be the preparation of exercise sheets as well as the course project.

Expected learning outcome

• Explain and understand the central dogma of molecular biology, central aspects of gene regulation, the basic principle of epigenetic DNA modifications, and specialties w.r.t. bacteria & phage genetics
• Model ontologies for biomedical data dependencies
• Design of systems biology databases
• Explain and implement DNA & amino acid sequence analysis methods (HMMs, scoring matrices, and efficient statistics with them on data structures like suffix arrays)
• Explain and implement statistical learning methods on biological networks (network enrichment)
• Explain the specialties of bacterial genetics (the operon prediction trick)
• Explain and implement methods for suffix trees, suffix arrays, and the Burrows-Wheeler transformation
• Explain de novo sequence pattern screening with EM algorithm and entropy models.
• Explain and implement basic methods for supervised and unsupervised data mining, as well as their application to biomedical OMICS data sets

Topics Covered

The following main topics are contained in the course:

• Central dogma of molecular genetics, epigenetics, and bacterial and phage genetics
• Design of online databases for molecular biology content (ontologies, and example databases: NCBI, CoryneRegNet, ONDEX)
• DNA and amino acid sequence pattern models (HMMS, scoring matrices, mixed models, efficient statistics with them on big data sets)
• Specialities in bacterial genetics (sequence models and functional models for operons prediction)
• De novo identification of transcription factor binding motifs (recursive expectation maximization, entropy-based models)
• Analysis of next-generation DNA sequencing data sets (memory-aware short sequence read mapping data with Burrows Wheeler transformation and suffix arrays, bi-modal peak calling)
• Visualization of biological networks (graph layouting: small but highly variable graphs vs. huge but rather static graphs)
• Systems biology and statistics on networks (network enrichment with CUSP, jActiveModules and KeyPathwayMiner)
• Basic supervised and unsupervised classification methods for OMICS data analysis

Requirements

During the course the students have to complete exercise sheets and participate on one large project at the end of the semester. The project will be evaluated with pass/fail and needs to be passed in order to be eligible for the oral exam at the end of the semester.

Lectures

Exercises

The exercises are not required to be handed in; nevertheless, we expect you to actively participate during the exercise session. Only in the case you want to have specific feedback for your solution you must send your solution to the TA before the session.

Assignment

General Notes

Here, you find all necessary information for the mandatory assignment for the course. Please note, that passing this assignment is necessary in order to be eligible to take the oral exam. Grading will be pass/fail with internal censor.

There will be no extensions to the deadline!

Deadline Final Hand-In: January 9th.

It is allowed and encouraged to work in teams of 5 students. Make sure, when submitting your reports and code, that all your team members' names are included.

Materials

• Project description
• Lecture Slides
• Software PEAX or directly from the vendor: here
• File 1: toydata - Raw data
• File 2: toydata - Peak picking results
• File 3: toydata - Peak alignment
• File 4: toydata - Indicator matrix
• File 5: toydata - Class lables
• File 6: Real data - Training: Raw data with class labels
• File 7: Real data - Unlabled raw data
• File 8: Output of PEAX for the labled and unlabled raw data

Additional Links

• Help with R: http://www.statmethods.net
• WEKA: http://www.cs.waikato.ac.nz/ml/weka/
• Papers
• Peak picking: here and here and here
• Breath Data Mining: here and here

Procedure of the oral exam

Examination Dates & Times

• Jan 29th: MM552
• Jan 30th: DM847
• Jan 31th: DM847

Further, I have posted lists with estimated time slots on my door. If you prefer to be examined at a certain time, please put your name next to the corresponding time slot. We will try our best to accommodate for your wishes but the times might be subject to change.

Procedure

The exam will last between 15-20 minutes. At the beginning, one topic from the list below will be drawn randomly. For each topic the examinee should be prepared to make a short presentation of max. 5 minutes. It is allowed to bring one page of hand-written notes (DIN A4 or US-Letter) for each of the topics. The examinee will have 2 minutes to briefly study the notes for the drawn topic before the presentation. The notes may be consulted during the exam if needed but it will negatively influence the evaluation of the examinee's performance. During the presentation, only the blackboard can be used (you cannot use overhead transparencies or powerpoint slides, for instance).

After the short presentation, additional question about the presentation's topic but also about other topics in the curriculum will be asked.

Below is the list of possible topics and some suggested content. The listed content are only suggestions and is not necessarily complete nor must everything be covered in the short presentation. It is the responsibility of the examinee to gather and select among all relevant information for each topic from the course material. The parts of the lecture not mentioned below might still be part of the oral exam but are just not deemed suitable for an oral presentation.

Topics for the short presentation

1. Exact String Matching
• Complexity
• KMP
• Boyer-Moore
• ...
2. Sequence Alignment
• Scoring Schemes
• Needleman-Wunsch
• Smith-Waterman
• BLAST
• ...
3. Short Read Mapping
• ChIP-Seq
• Burrows Wheeler Transformation
• ...
4. Transcription Factor Binding Sites
• PWMs
• Suffix Trees
• Enhanced Suffix Arrays
• ...
5. Sequence Logos and Motif Discovery
• Sequence Logos / Information Content
• Expectation Maximization
• MEME
• ...
6. Hidden Markov Models
• Markov Chain
• Classic HMM Problems
• Modeling of Proteins
• ...
7. Data Mining
• k-means
• Decision Trees
• Random Forest
• Performance Evaluation
• ...
8. Network Enrichment
• Active Modules
• CUPS
• KPM
• ...

Materials

All lecture slides are relevant for the exams.

Books:

• Gussfield, D. "Algorithms on strings, trees, and sequences." Computer Science and Computional Biology (Cambrigde, 1999) (1997).
• Durbin, Richard, et al. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge university press, 1998.

Useful Links

TBA