Algoritmy výpočetní genomiky

Garant předmětu:

Jan Holub

Přednášející:

Jan Holub

Cvičící:

Jan Holub

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět se zabývá efektivními algoritmy pro různé úlohy bioinformatiky. Jednou takovou úlohou je alignment dvou ale i více sekvencí. Dále se zabývá algoritmy pro jednotlivé fáze sestavení genomu. Předmět také představuje komprimované datové struktury pro uchovávání a indexování genomů a jejich velmi rychlé prohledávání.

Požadavky:

Přednáška je primárně určena pro doktorandy.

Osnova přednášek:

1. Algoritmy pro zarovnání více sekvencí I - skórovací systémy, dynamické programování

2. Algoritmy pro zarovnání více sekvencí II - heuristické algoritmy - metoda progresivní a metoda branch and bound

3. Algoritmy pro zarovnání readů

4. Sestavení genomu a řetězcové grafy

5. De Bruijnovy grafy a Eulerovská cesta.

6. Konstrukce de Bruijnových grafů.

7. Reprezentace de Bruijnových grafů.

8. Algoritmy pro scaffolding.

9. Komprese genomu I - založená na LZ

10. Komprese genomu II - založená na BWT

11. Analýza a porovnání genomů I - paměťově efektivní analýza genomů

12. Analýza a porovnání genomů II - porovnání genomů bez zarovnání

13. Poslední vývoj ve výpočetním zpracování genomu.

14. Shrnutí algoritmů výpočetní genomiky

Osnova cvičení:

Cíle studia:

Studenti budou umět:

- Znát základní principy algoritmů pro zarovnání více sekvencí,

- znát algoritmické pozadí sestavování genomu,

- znát kompresní metody používané pro efektivná ukládání a indexování genomů,

- znát algoritmické pozadí analýzy a porovnávání genomů.

Studijní materiály:

- V. Mäkinen, D. Belazzougui, F. Cunial, A.I. Tomescu: Genome-Scale

Algorithm Design: Biological Sequence Analysis in the Era of

High-Throughput Sequencing. Cambridge University Press, 2015. ISBN:

978-1107078536

- E. Ohlebusch: Bioinformatics Algorithms: Sequence Analysis, Genome

Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag,

2013. ISBN: 978-3000413162

Poznámka:

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Informatika (doktorská) (povinně volitelný předmět)
• Informatika (povinně volitelný předmět)