Předměty

V současné době dala biologie vzniknout celé řadě zajímavých matematických problémů, jejichž cílem je dekódování jazyka DNA sekvencí. Bioinformatika je rychle se rozvíjející oblastí moderní informatiky, která implikuje další rozvoj biologických věd. Tato přednáška je zaměřena na vysvětlení základních algoritmických principů použitelných při řešení nejrůznějších biologických problémů. Předpokládají se znalosti programování v rozsahu bakalářského kursu NPRG031 Programování II. Přednáška je určená pro studenty informatiky bez znalosti základů biologie.

Poslední úprava: Mráz František, RNDr., 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.

Poslední úprava: Mráz František, RNDr., CSc. (21.05.2013)

Naučit základy bioinformatiky a v ní používaných algoritmů.

Poslední úprava: T_KTI (23.04.2013)

An introduction to bioinformatics and algorithms used within bioinformatics.

Poslední úprava: Mráz František, RNDr., CSc. (19.04.2013)

A) Cvičení

V doprovodném Moodle-kurzu se budou postupně objevovat úkoly a testy.

Úkoly:

Každý úkol má stanovené datum odevzdání. Řešení lze do systému vkládat postupně a průběžně ho upravovat. Časem odevzdání je čas kliknutí na tlačítko "Odevzdat úkol". Po kliknutí na toto tlačítko řešení už nelze opravovat, ale lze zažádat e-mailem učitele o vrácení do stavu rozpracování. Každý úkol bude učitelem oznámkován přidělením 0-10 bodů. Za celý semestr budou zadány 3 úkoly.

Typické řešení úkolu bude sestávat z textu – popisu řešení – a kódu programu/skriptu použitého na vyřešení úkolu. Texty odevzdávejte ve formátu PDF, zdrojové kódy jako jednoduché ASCII soubory. Alternativně lze odevzdat text i kód v jediném souboru jako Jupyter notebook, který obsahuje popis i kód zároveň.

Upozornění: V případě, že bude zjištěno, že N≥2 posluchačů odevzdalo řešení, která se nápadně podobají nebo jsou zcela totožná, budou všechna tato řešení považována za jedno řešení. Toto řešení bude ohodnoceno B body podle jeho kvality, ale každý z těchto N řešitelů získá pouze dolní celou část z B/N bodů.

Testy:

Kromě úkolů, budou postupně zveřejňovány on-line testy. Za celý semestr bude zadáno několik testů za maximálně 20 bodů dohromady. Každý test bude mít stanovené datum, do kterého musí být vyřešen. Řešit test po tomto datu nebude možné.

Pro získání zápočtu je nutné:

Vypracovat řešení všech úkolů a za řešení každého úkolu získal alespoň 1 bod. POZOR: za pozdní odevzdání úkolu se strhává 1 bod za každý započatý týden po termínu odevzdání!

Vypracovat a přednést řešení projektu na jednom z posledních cvičení nebo v termínu prezentací v zkouškovém období (jeho datum a čas bude dohodnutý na cvičení v posledním týdnu semestru). Témata projektů budou dohodnuté přibližně v půlce semestru na cvičení. Prezentace a odevzdané řešení budou taktéž ohodnoceny dohromady 0-15 body.

Mezi výše uvedenými podmínkami nejsou uvedeny on-line testy. Na cvičeních lze získat dodatečné body

za předvedení řešení úkolu zadaného na cvičení – 1 bod,

za předvedení řešení úkolu zadaného a odevzdaného v Moodlu (po termínu odevzdání) – dolní celá část poloviny bodů, které budou přiděleny za odevzdané řešení.

Body získané za celý semestr budou zkoušejícím započítány do celkové známky za předmět tak, aby tvořily 40% výsledného bodového hodnocení, ze kterého bude odvozena známka při zkoušce.

Získání zápočtu vyžaduje průběžnou práci přes celý semestr, a proto žádné náhradní termíny pro získání zápočtu nebudou vypsány.

B) Přednáška

Jak už bylo zmíněno výše, body získané z cvičení budou započítány s vahou 40% do celkového hodnocení posluchače. Samotná zkouška na konci semestru se započítá 60% do výsledného hodnocení. Posluchač získá známku na základě celkového hodnocení podle následující tabulky

známka 1	známka 2	známka 3	nevyhověl
100%–86%	85%–71%	70%–56%	méně než 56%

Poslední úprava: Mráz František, RNDr., CSc. (01.10.2024)

A) The lab

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

Assignments:

Each assignment has a deadline until 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 to the draft state. Each submitted assignment will be graded by the teacher with 0–10 points. During the semester, you will solve 3 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 and the source codes as plain ASCII files. Alternatively, a solution can be submitted as a Jupyter notebook containing both the code and the description.

Warning: If N≥2 participants of the course will submit solutions that are identical or very similar, 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 submit it will obtain only the integer part of the value B/N points.

Quizzes:

Besides the assignments, you will solve several on-line quizzes. During the semester, there will be assigned several short quizzes for at most 20 points altogether. Each quiz will have set up also a deadline. In contrast to the assignments, it will be not possible to solve any quiz after its deadline.

For obtaining credits for the lab it is necessary:

To solve all the assignments and to obtain at least 1 point for each solution. WARNING: late submission of a solution will be penalized by 2 points decrease for each started week of the delay after the deadline

To prepare and to present a term project in a lab in the last week of this term or on a date (during the following exam period) which will be set up in the lab within the last week of this term. The subject of the project will be discussed in the middle of the semester. Each project will be graded up to 15 points according to its quality.

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

for demonstrating a solution of a problem assigned during a lab – 1 point,

for demonstrating a solution submitted as a solution for an assignment in Moodle (after its deadline) – the integer part of the half of the number of points awarded for the solution (after evaluating by the teacher)

Except for the additional points, it is possible to obtain up to 75 points. All points obtained during labs will be accounted for up to 40% of the final score of the exam. However, when a student obtains more than 75 points within labs (counting also additional points), these points will still account for only 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, the points acquired within the lab 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% of 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%

Poslední úprava: Mráz František, RNDr., CSc. (01.10.2024)

[1] Neil C. Jones and Pavel Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, 2004

[2] Richard Durbin, Sean R. Eddy, Anders Krogh and Graeme Mitchison: Biological sequence analysis. Cambridge University Press 1998

[3] Marketa J. Zvelebil and Jeremy O. Baum: Understanding bioinformatics. Taylor&Francis, 2008

[4] Phillip Compeau and Pavel Pevzner. Bioinformatics algorithms: an active learning approach. Vol. 1 & 2. La Jolla, California: Active Learning Publishers, 2015.

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)

[1] Neil C. Jones and Pavel Pevzner: An Introduction to Bioinformatics Algorithms, MIT Press, 2004

[2] Richard Durbin, Sean R. Eddy, Anders Krogh and Graeme Mitchison: Biological sequence analysis. Cambridge University Press 1998

[3] Marketa J. Zvelebil and Jeremy O. Baum: Understanding bioinformatics. Taylor&Francis, 2008

[4] Phillip Compeau and Pavel Pevzner. Bioinformatics algorithms: an active learning approach. Vol. 1 & 2. La Jolla, California: Active Learning Publishers, 2015.

Poslední úprava: Mráz František, RNDr., CSc. (28.09.2020)

Zkouška sestává z písemné a ústní části. Ústní část následuje bezprostředně po písemné části, zahrnuje diskusi a hodnocení písemné části. Písemná část se skládá ze tří otázek. První dvě otázky jsou dva okruhy z přednášky a třetí je buď konkrétní použití nějakého algoritmu z přednášky, anebo návrh algoritmu pro řešení nové varianty vybraného problému z přednášky nebo cvičení.

Požadavky ke zkoušce odpovídají sylabu přednášky v rozsahu, který byl prezentován na přednášce, resp. cvičení. Hodnocení zkoušky zahrnuje i hodnocení práce studenta na cvičení tak, jak je uvedeno v podmínkách zakončení předmětu. Nutnou podmínkou pro účast na zkoušce je získání zápočtu.

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)

The exam consists of a written and oral part. The oral part, which follows immediately after the written part, comprises discussion and evaluation of the written part. The written part 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 the 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.

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)

Úvod do bioinformatiky
- Bioinformatika – vymezení problematiky, historie a základní úlohy
- Úvod do molekulární biologie – struktura DNA a její analýza, geny, proteiny

Základní bioinformatické algoritmy:
- Úplné prohledávání – mapování restrikcí, vyhledávání motivů
- Hladové algoritmy – přeuspořádání genomu, vyhledávání motivů
- Dynamické programování – podobnost DNA sekvencí, alignment sekvencí, alignment s penalizací děr, predikce genů
- Algoritmy typu rozděl a panuj – prostorově a časově efektivní alignment sekvencí
- Grafové algoritmy – DNA sekvencování, sekvencování proteinů a jejich identifikace, sekvencování peptidů
- Kombinatorické algoritmy pro vyhledávání vzorů – exaktní vyhledávání vzorů, klíčové stromy, sufixové stromy, heuristické vyhledávání podobnosti, aproximativní vyhledávání vzorů, BLAST a FASTA

Pokročilé bioinformatické algoritmy:
- Skryté Markovovy modely – dekódovací algoritmus, odhad parametrů HMM
- Randomizované algoritmy a vyhledávání motivů – Gibbsovo vzorkování, náhodné projekce
- Zjišťování podobnosti pomocí komprese

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)

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

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

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

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)