PředmětyPředměty(verze: 957)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Bioinformatické algoritmy - NTIN084
Anglický název: Bioinformatics Algorithms
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: RNDr. František Mráz, CSc.
Vyučující: RNDr. František Mráz, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Je neslučitelnost pro: NTIX084
Je záměnnost pro: NTIX084
Anotace -
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)
Cíl předmětu -

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

Poslední úprava: T_KTI (23.04.2013)
Podmínky zakončení předmětu -

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é:

  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í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)
Literatura -

[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)
Požadavky ke zkoušce -

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)
Sylabus -

  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

Poslední úprava: Mráz František, RNDr., CSc. (29.09.2020)
 
Univerzita Karlova | Informační systém UK