Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Selected Topics in Computational Biology (SS 2005)

• Lectures:
  Dr. Jens Ernst

• 3 hrs of lecture per week (given in English language)
  2 hrs of exercises per week

• Location and Times:
  Tue. 08:15 - 09:00, MI Room 03.11.18
  Wed. 16:00 - 17:30, MI Room 03.11.18
  
• Exercises:
  2 hrs/wk of exercises
  Teaching Assistant: Johannes Nowak
  

• Audience:
  Students of Bioinformatics

• Prerequisites:
  Discrete Structures
  Fundamental Algorithms or Efficient Algorithms
  Algorithms for Bioinformatics I,II
  

• Information and Course Material:
  

  Suffix Trie/Tree example (pdf)

• Topics (up to now):
  
  • A. Alorithms on Sequence Data
  • 1. Suffix Trees - Theory, Implementation and Applications
  • 1.1. Ukkonen's Online Linear-Time Algorithm
  • 1.1.1. Constructing Suffix Tries
  • 1.1.2. Structure and Representation of Suffix Trees
  • 1.1.3. Efficient Construction of Suffix Trees
  • 1.2. Mc Creight's Algorithm
  • 1.2.1. Overview and Definitions
  • 1.2.2. Linear-time Algorithm
  • 1.2.3. Hash Code Implementation
  • 2. Applications of Suffix Trees in Computational Biology
  • 2.0. Classification of Exact String Matching Problems
  • 2.0.1. Indexing Problems
  • 2.0.2. Dictionary Matching Problems
  • 2.1. An Obvious Application of Suffix Trees to 2.0.1
  • 2.2. Indexing with One Error
  • 2.2.1. Central Idea
  • 2.2.2. Efficient Computation of Set Intersections
  • 2.2.3. Indexing With One Error in the Presence of Exact Matches
  • 2.3. Using Suffix Trees for Dictionary Matching
  • 2.4. Dictionary Matching with One Error
  • 2.4.1. Central Idea
  • 2.4.2. Set Intersection on Tree Paths
  • 2.5. Longest Common Substrings of Two or More Strings
  • 2.6. Efficient Searching in Protein Structure Databases (Guest Lecture)
  • 3. Suffix Arrays - Outline
  • 3.1. Basic Definitions
  • 3.2. Indexing using Accelerants and Super-Accelerants
  • B. Sequence Alignment (offered on Tuesdays, for Computer Scientists)
  • 1. Basic Global Sequence Alignment
  • 1.1. Edit Sequences, Edit Distance and Alignments
  • 1.2. Needleman-Wunsch Algorithm to Compute Alignment Distances
  • 1.3. Computing Alignments
  • 1.4. Linear-Space Implementation
  • 2. Hirschberg Optimization
  • 2.1. Derivation of the Algorithm
  • 2.2. Implementation
  • C. Selected Algorithms for Gene Expression Analysis
  • 1. Introduction
  • 1.1. Basics of Gene Expression
  • 1.2. DNA Microarray Technology
  • 1.3. Sources of Systematic and Random Error in Microarray Experiments
  • 1.4. Gene Expression Profiling (Type-II Experiments)
  • 2. Similarity and Dissimilarity Measures for Gene Expression Profiles
  • 2.1. Definition for Similarity and Distance Measures
  • 2.2. Minkowski Distance
  • 2.3. Pearson Correlation Coefficient
  • 2.4. Spearman Rank-Order Correlation
  • 2.5. Kendall's Tau
  • 2.6. Jackknife Correlation
  • 2.7. Mutual Information
  • 3. Elementary Clustering Algorithms
  • 3.1. Hierarchical Clustering
    • 3.1.1. Single Linkage
    • 3.1.2. Complete Linkage
    • 3.1.3. Average Linkage
  • 3.2. K-Means
  • 3.3. HCS
  • 3.4. Self-Organizing Maps
  • 4. Probabilistic Algorithms
  • 4.1. Short Reminder On Probability Theory
  • 4.2. Introduction to Tail Inequalities
    • 4.2.1. Marov and Chebyshev
    • 4.2.2. Chernoff
  • 4.3. CAST
  • 4.4. CLICK

  (Note: The information given here is incomplete, preliminary and will be subject to change.)



• Selected Literature:
  
  • "The smallest atuomaton recognizing the subwords of a text", A. Blumer et. al., Theoretical Computer Science 40 (1985), 31-55
  • "A comparison of imperative and purely functional suffix tree constructions", R. Giegerich, S. Kurz, Science of Computer Programming 25 (1995), 187-218
  • "From Ukkonen to McCreight and Weiner: A Unifying View to Linear-Time Suffix Tree Construction", R. Giegerich, S. Kurtz, Algorithmica 19 (1997), 331-353
  • "Algorithms on Strings, Trees and Sequences", Dan Gusfield Cambridge University Press
  • "Suffix Arrays: A new method for on-line string searches", U. Manber, G. Myers, SIAM J. Comput., Vol 22, No 5 (1993), 935-948
  • "A Space-Economical Sufix Tree Construction Algoritm", E. McCreight, Journal of the ACM, Vol 23, No 2 (1976), 262-272
  • "Practical Suffix Tree Construction", S. Tata et. al., Proceedings of the 30th VLDB Conference (2004)
  • "On-Line Construction of Suffix Trees", E. Ukkonen Algorithmica (1995), 249-260
• Office hours:
  by appointment