Thema der Dissertation:
Advanced Methods for Real-time Metagenomic Analysis of Nanopore Sequencing Data Thema der Disputation:
Minimizer-space De Bruijn graphs
Advanced Methods for Real-time Metagenomic Analysis of Nanopore Sequencing Data Thema der Disputation:
Minimizer-space De Bruijn graphs
Abstract: DNA sequencing has experienced tremendous changes during the last two decades, evolving from low-throughput technologies used to sequence the first human genome to the recent high-throughput long-read technologies. With the unprecedented growth of sequencing data produced by those machines, efficient algorithms for sequence analysis became critical factors for tasks such as read mapping, genome assembly and taxonomic profiling. For de novo genome assembly, the naïve approach of pairwise comparisons between all sequenced reads is too resource-intensive for high-throughput sequencing data. More efficient de novo assemblers chop up reads into k-mers and create a de Bruijn graph, where each complete chromosome corresponds to a path in the resulting graph. While de Bruijn graphs theoretically scale linearly with the genome size, sequencing errors can cause branching and thus increase their size and runtime to search. A promising approach to advance the data structure is the minimizer-space de Bruijn graph, where short sequences of nucleotides known as minimizers are used as tokens in the de Bruijn graph instead of single nucleotides. In this talk, I will introduce the general concepts of minimizers and de Bruijn graphs and present the computational method underlying the minimizer-space de Bruijn graph used for de novo assembly of third-generation long reads.
Zeit & Ort
19.01.2024 | 15:00
Seminarraum 007/008
(Fachbereich Mathematik und Informatik, Arnimallee 6, 14195 Berlin)