SubjectsSubjects(version: 809)
Course, academic year 2017/2018
   Login via CAS
Bioinformatics Algorithms - NTIN084
Czech title: Bioinformatické algoritmy
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. František Mráz, CSc.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: RNDr. František Mráz, CSc. (21.05.2013)

In recent decades, biology has raised a lot of challenging mathematical problems aiming at deciphering the language of DNA sequences. Bioinformatics is a rapidly developing area of computer science driving further biological developments. This course is focused on explaining the main algorithmic principles applicable to the solution of various biological problems. This shall provide the students with a solid foundation to understand more easily also other parts of this emerging field. The lecture is for students of computer science without background in biology.
Aim of the course -
Last update: RNDr. František Mráz, CSc. (19.04.2013)

An introduction to bioinformatics and algorithms used within bioinformatics.

Terms of passing the course -
Last update: RNDr. František Mráz, CSc. (10.10.2017)

A) The seminary

Step by step, in an accompanying Moodle course there will be published assignments and quizzes.

Assignments:

Each assignment has a deadline untill which the assignment should be submitted for grading. A draft solution of an assignment can be edited at any time, but the time of submission is the time you click the button "Submit assignment". After clicking this button you cannot edit your submission anymore, but you can ask (per e-mail) your teacher to return the assignment back into the draft state. Each submitted assignment will be graded by the teacher with 0-10 points. During the semester, you will solve 4 assignments.

A typical solution for an assignment will consist of a text - a description of the solution - and a code of a program/script used for solving the assignment. Submit your texts as a PDF-file or alternatively as an RTF-file. The source codes should be submitted as plain ASCII files. Alternatively, description and source code can be submitted in single file - a jupyter/IPython notebook.

Warning: If N≥2 participants of the course will submit solutions which are very similar or identical, all these solutions will be considered as a single solution. The solution will be graded by B points according to its quality and all students who submitted it will obtain only the integer part of the value B/N points.

Quizzes:

Beside the assignments, you will solve several on-line quizzes. Each quiz will have set up also a deadline and a maximal achievable score. In contrast to assignments it will be not possible to solve any quiz after its deadline. On the other hand, you will be given 3 attempts for solving each quiz and you will score the best score of all your attempts on the quiz.

For obtaining credits for the seminary it is necessary:

  1. To solve all the assignments and to obtain at least 1 point for each solution. WARNING: a late submission of a solution will be penalized by 1 point for each started week of the delay after the deadline.
  2. To prepare and to present a term project in a seminary in the last week of this term or on a date (during the following exam period) which will be set-up on a seminary within the last week of this term. Subject for the project will be discussed in a seminary in the middle of this term. Each project will be graded by 0-15 points according to its quality.

The quizzes are not among the necessary conditions for obtaining credits for the seminary. During seminaries it is possible to obtain additional points

  • for demonstrating a solution of a problem assigned during a seminary  - 1 point
  • for demonstrating a solution submitted as a solutions for an assignment in Moodle (after its deadline) - the half of the number of point awarded for the solution (after evaluating by the teacher)

However, all points obtained during seminaries will be accounted for up to 40% of the final score of the exam.

Continuous work throughout the whole term is required to obtain the credits, therefore there will be no additional possibilities to acquire them later.

 

B) The lecture

The lecture will be given once per week according to the schedule. As already mentioned above, points acquired within the seminary will account for up to 40% of the final score for the exam. The exam at the end of this term will add up to the remaining 60% to the final score. The following table gives the final grade according to the achieved score:

grade 1 grade 2 grade 3 failure
100%–86% 85%–71% 71%–56%

less than 56%

Literature -
Last update: T_KTI (23.04.2013)

Jones N. C. and Pevzner P. A.: An Introduction to Bioinformatics Algorithms, MIT Press, 2004

Pevzner P. A.: Computational Molecular Biology: An Algorithmic Approach, MIT Press, 2000

Zvelebil M., Jeremy Baum J. A.: Understanding Bioinformatics, Garland Science, 2007

Requirements to the exam -
Last update: RNDr. František Mráz, CSc. (15.10.2017)

The exam consists of a written and oral part. The oral part follows immediately after the written part, comprises discussion and evaluation of the written part.

Written exam contains three questions. The first two questions are two subjects from the lecture and the third question is either an application of an algorithm from the lecture, or designing an algorithm for solving a new variant of a problem from the lecture or the seminar.

The requirements for the exam correspond to the syllabus of the lecture within the extent which was presented during the lecture or the seminar. The final grade of the exam is set based on points awarded for the exam as well as on the points obtained for student’s work throughout the semester - see “Terms of passing the course”. In order to take part in the exam, it is necessary to obtain Final course credit.

Syllabus -
Last update: RNDr. František Mráz, CSc. (30.04.2015)

  1. Introduction to bioinformatics:

    • Bioinformatics - its subject, history and main problems
    • Introduction to molecular biology - the structure of DNA and its analysis, genes, proteins

  2. Classical bioinformatics algorithms:

    • Exhaustive search - restriction mapping, motif finding
    • Greedy algorithms - genome rearrangements, motif finding
    • Dynamic Programming Algorithms - similarity of DNA sequences, sequence alignment, alignment with gap penalties, gene prediction
    • Divide-and-conquer algorithms - space and time efficient sequence alignment
    • Graph algorithms - DNA sequencing, protein sequencing and identification, peptide sequencing
    • Combinatorial pattern matching - exact pattern matching, keywords trees, suffix trees, heuristic similarity search, approximate pattern matching, BLAST and FASTA

  3. Advanced bioinformatics algorithms:

    • Hidden Markov Models - decoding algorithm, HMM parameter estimation
    • Randomized algorithms - Gibbs sampling, random projections
    • Computing similarity by compression

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html