PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Bioinformatické algoritmy - NTIN084
Anglický název: Bioinformatics Algorithms
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: RNDr. František Mráz, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: RNDr. František Mráz, CSc. (21.05.2013)

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.
Cíl předmětu -
Poslední úprava: T_KTI (23.04.2013)

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

Podmínky zakončení předmětu -
Poslední úprava: RNDr. František Mráz, CSc. (10.10.2017)

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 "Odeslat řešení k oznámkování". 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 4 ú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, případně RTF, zdrojové kódy jako jednoduché ASCII soubory. Alternatívne lze odevzdat text i kód v jediném souboru jako jupyter/IPython notebook.

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. 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é. Na druhou stranu daný test lze řešit až třikrát s tím, že se započítává nejlepší výsledek.

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

  1. 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í!
  2. 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ískať 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íně 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%

Literatura -
Poslední úprava: T_KTI (23.04.2013)

Jones N. C., 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

Požadavky ke zkoušce -
Poslední úprava: RNDr. František Mráz, CSc. (15.10.2017)

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.

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

  1. Úvod do bioinformatiky

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

  2. 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

  3. 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

 
Univerzita Karlova | Informační systém UK