Course - Algorithms for Bioinformatics - TDT4287
TDT4287 - Algorithms for Bioinformatics
About
Examination arrangement
Examination arrangement: Home examination
Grade: Passed/Failed
| Evaluation form | Weighting | Duration | Examination aids | Grade deviation |
|---|---|---|---|---|
| Home examination | 100/100 | 4 hours |
Course content
The course deals with algorithms with applications in bioinformatics, with a particular focus on algorithms and data structures for search, comparisons, and motif discovery in strings. The course uses biological examples to motivate algorithms and solutions, but the course's focus is on the algorithmic problems and solutions.
Learning outcome
Knowledge:
- Knows how dynamic programming (DP) can be used to solve string comparison problems such as "longest common subsequence", "edit distance", "local alignment", and "global alignment".
- Knows how the DP solution for aligning two strings can be extended to aligning multiple strings.
- Knows how k-mer indexes can be used for exact and approximate string search.
- Knows what a keyword tree is, and how this index structure is built and used for string search.
- Knows what a suffix tree is, how Ukkonen's algorithm can build this index structure in linear time, and how suffix trees can be used to solve different string search and comparison problems.
- Knows how to find string motifs by using exact (branch-and-bound) and heuristic (simulated annealing) methods.
- Knows how sequence assembly is connected to the shortest super-string problem and why the Euler-cycle problem is a special version of sequence assembly.
- Knows what hidden Markov-models (HMM) are, how these can be used to model and identify properties of strings, and how the Viterbi, forward, and backward HMM algorithms work.
- Knows what a RNA secondary structure is, how this relates to palindromes, and how DP can be used to find optimal and suboptimal RNA secondary structures.
Skills:
- Implement known algorithms and data structures and use these on real data.
- Recognize variants of known problems and adapt known algorithms to solve these variant problems.
Competence:
- Choose between alternative solutions and use the solution that is most appropriate to solve a set of problems involving real data.
- Give oral and written presentations of own solutions and results.
Learning methods and activities
Lectures, optional exercises, and a mandatory project. If few students take the course, the lectures may be replaced with study groups.
Compulsory assignments
- Exercises
Further on evaluation
Exams are only given in English. Students are free to choose Norwegian or English for written assessments.
If there is a re-sit examination, the examination form may change from written to oral.
Specific conditions
Exam registration requires that class registration is approved in the same semester. Compulsory activities from previous semester may be approved by the department.
Recommended previous knowledge
The course TDT4120 Algorithms and Datastructures. The course TMA4240 Statistics or similar.
Course materials
Jones & Pevzner: An introduction to bioinformatics algorithms (MIT Press, 2004). Articles and handouts. (This may change.)
Version: 1
Credits:
7.5 SP
Study level: Second degree level
Term no.: 1
Teaching semester: AUTUMN 2020
No.of lecture hours: 2
Lab hours: 3
No.of specialization hours: 7
Language of instruction: English
Location: Trondheim
- Algorithm Construction
- Bioinformatics
Examination
Examination arrangement: Home examination
- Term Status code Evaluation form Weighting Examination aids Date Time Digital exam Room *
-
Autumn
ORD
Home examination (1)
100/100
Release 2020-12-07
Submission 2020-12-07
Release 09:00
Submission 13:00
INSPERA -
Room Building Number of candidates - Summer UTS Home examination 100/100 INSPERA
-
Room Building Number of candidates
- * The location (room) for a written examination is published 3 days before examination date. If more than one room is listed, you will find your room at Studentweb.
- 1) Merk at eksamensform er endret som et smittevernstiltak i den pågående koronasituasjonen. Please note that the exam form has changed as a preventive measure in the ongoing corona situation.
For more information regarding registration for examination and examination procedures, see "Innsida - Exams"