Students will know:

• Basics principles of algorithms for multiple sequence alignment,

• algorithmic background of genome assebmly,

• data compression methods used for efficient storage and indexing genomes,

• algorithmic background of genome analysis and comparison.

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

The exam is composed of the written test and the oral exam.

Zkouška sestává z písemného testu a ústní část

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

R: E. Ohlebusch: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, 2013. ISBN: 978-3000413162

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

Z: E. Ohlebusch: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, 2013. ISBN: 978-3000413162

1. Multiple sequence alignment algorithms I - scoring systems, dynamic programming

2. Muliple sequence alignment algorithms II - heuristic algorithms - progressive and branch and bound methods

3. Read alignment algorithms

4. Genome assembly and string graphs

5. De Bruijn graphs and Eulerian walks

6. Building de Bruijn graphs

7. Representations of de Bruijn graphs

8. Scaffolding algorithms

9. Genome compression I - LZ based

10. Genome compression II - BWT based

11. Genome analysis and comparison I - space-efficient genome analysis

12. Genome analysis and comparison II - comparing genomes without alignment

13. Latest developments in computational genome processing

14. Summary of algorithms for computational genomics

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 Eulerivská 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

Online course materials

Online materiály ke kursům

Algorithmic thinking

Algoritmické myšlení