Selected Topics in Algorithms for Computational Biology
Module IN2127
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Basic Information
IN2127 is a semester module in German language at Bachelor’s level and Master’s level which is offered irregular.
This module description is valid to WS 2000/1.
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 150 h | 60 h | 5 CP |
Content, Learning Outcome and Preconditions
Content
- Algorithms on Sequence Data
++ Suffix Trees - Theory, Implementation and Applications: Ukkonen's Online Linear-Time Algorithm, McCreight's Algorithm
++ Applications of Suffix Trees in Computational Biology: Classification of Exact String Matching Problems, An Obvious Application of Suffix Trees, Indexing with One Error, Using Suffix Trees for Dictionary Matching, Dictionary Matching with One Error, Longest Common Substrings of Two or More Strings, Efficient Searching in Protein Structure Databases (Guest Lecture)
++ Suffix Arrays - Outline: Basic Definitions, Indexing using Accelerants and Super-Accelerants
- Sequence Alignment
++ Basic Global Sequence Alignment: Edit Sequences, Edit Distance and Alignments, Needleman-Wunsch Algorithm to Compute Alignment Distances, Computing Alignments, Linear-Space Implementation
++ Hirschberg Optimization: Derivation of the Algorithm, Implementation
- Selected Algorithms for Gene Expression Analysis
++ Introduction: Basics of Gene Expression, DNA Microarray Technology, Sources of Systematic and Random Error in Microarray Experiments, Gene Expression Profiling (Type-II Experiments)
++ Similarity and Dissimilarity Measures for Gene Expression Profiles: Definition for Similarity and Distance Measures, Minkowski Distance, Pearson Correlation Coefficient, Spearman Rank-Order Correlation, Kendall's Tau, Jackknife Correlation, Mutual Information
++ Elementary Clustering Algorithms: Hierarchical Clustering, K-Means, HCS, Self-Organizing Maps
++ Probabilistic Algorithms: Short Reminder On Probability Theory, Introduction to Tail Inequalities, CAST, CLICK
++ Spectral Clustering Algorithms: Matrix Decomposition, Spectral Properties of Cluster Graphs, Perturbation Theoretical Analysis, Spectral Reduction Algorithms
++ Suffix Trees - Theory, Implementation and Applications: Ukkonen's Online Linear-Time Algorithm, McCreight's Algorithm
++ Applications of Suffix Trees in Computational Biology: Classification of Exact String Matching Problems, An Obvious Application of Suffix Trees, Indexing with One Error, Using Suffix Trees for Dictionary Matching, Dictionary Matching with One Error, Longest Common Substrings of Two or More Strings, Efficient Searching in Protein Structure Databases (Guest Lecture)
++ Suffix Arrays - Outline: Basic Definitions, Indexing using Accelerants and Super-Accelerants
- Sequence Alignment
++ Basic Global Sequence Alignment: Edit Sequences, Edit Distance and Alignments, Needleman-Wunsch Algorithm to Compute Alignment Distances, Computing Alignments, Linear-Space Implementation
++ Hirschberg Optimization: Derivation of the Algorithm, Implementation
- Selected Algorithms for Gene Expression Analysis
++ Introduction: Basics of Gene Expression, DNA Microarray Technology, Sources of Systematic and Random Error in Microarray Experiments, Gene Expression Profiling (Type-II Experiments)
++ Similarity and Dissimilarity Measures for Gene Expression Profiles: Definition for Similarity and Distance Measures, Minkowski Distance, Pearson Correlation Coefficient, Spearman Rank-Order Correlation, Kendall's Tau, Jackknife Correlation, Mutual Information
++ Elementary Clustering Algorithms: Hierarchical Clustering, K-Means, HCS, Self-Organizing Maps
++ Probabilistic Algorithms: Short Reminder On Probability Theory, Introduction to Tail Inequalities, CAST, CLICK
++ Spectral Clustering Algorithms: Matrix Decomposition, Spectral Properties of Cluster Graphs, Perturbation Theoretical Analysis, Spectral Reduction Algorithms
Learning Outcome
Teilnehmer können Algorithmen und Datenstrukturen für die Bioinformatik entwickeln, die Effizienz solcher Algorithmen und Datenstrukturen analysieren und optimieren und wissen um das Algorithm Engineering im Bereich Bioinformatik.
Preconditions
IN2003 Efficient Algorithms and Data Structures, IN0007 Fundamentals of Algorithms and Data Structures