+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Freitag, 26. August 2022, 13.00 Uhr
Der öffentliche Vortrag findet hybrid statt:
Ort: Raum 9222, Ahornstr. 55
Zoom:
https://rwth.zoom.us/j/92249056004?pwd=cHkwRW1lNTlmS1RXQW95Wmw1MjhFQT09
Referent: Janosch Fuchs M.Sc.
Lehrstuhl Informatik 1
Thema: Graph Exploration with Advice (and Online Crossing Minimization)
Abstract:
Online problems reveal their input instance piece by piece and require
an irrevocable decision each time a new piece is revealed. This scenario
models critical applications where a decision, once it is made, cannot
be changed afterwards and also influences future decisions. Like for
classical offline problems, it is common to make a worst-case analysis
to give a guarantee on the performance of an online algorithm. A
worst-case analysis is achieved by assuming that a malicious adversary,
knowing the behavior of the online algorithm, creates the input. Due to
the nature of uncertainty online algorithms rarely compute an optimal
solution. Thus, their performance is measured in terms of the
competitive ratio, which compares the solution computed by the online
algorithm to the optimal solution achievable when the whole instance is
known beforehand.
To measure the impact of the missing knowledge about the future the
classical online setting was extended with a helpful oracle providing
information about the future input. The online algorithm receives the
information by accessing a tape containing a binary bit string. The
number of bits that the algorithm reads during its computation is called
its advice complexity. Bounds on the advice complexity of an online
algorithm that optimally solves an online problem show how much
information about the future is needed to avoid any mistake. An obvious
upper bound for the advice complexity of all online problems is the size
of the binary encoding of the input instance or the optimal solution.
But most of the time it is possible to derive better bounds by encoding
only critical decisions which then reveals the core difficulty of an
online problem. Thus, the advice complexity strongly correlates to the
difficulty of an online problem and it can be used to measure the
difficulty of different online problems.
In the main part, we analyze the advice complexity of the graph
exploration problem. Here, an algorithm has to move an agent through a
graph from vertex to vertex using the edges such that the agent
traverses the cheapest or shortest tour that visits every vertex at
least once. The algorithm does not know the graph beforehand and each
time the agent is located at a new vertex the reachable neighborhood is
revealed together with the cost to reach them from the current location.
Already seen or visited vertices are recognizable. Due to the already
known tight upper bound of n\log(n) for the advice complexity of the
graph exploration problem on dense graphs, we focus on sparse graphs. We
show that a linear amount of advice is sufficient and also necessary to
solve the graph exploration problem on directed and undirected graphs.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Mittwoch, 10.08.2022, 14:00-15:00 Uhr
Ort: Raum 5053.2 (großer B-IT-Raum)/Informatikzentrum, Ahornstraße
55
Referent: Herr Zhijian Li , M.Sc.
Institute for Computational Genomics
Thema: Computational Method for Single-cell ATAC-seq Imputation and
Dimensionality Reduction
Abstract:
Single-cell sequencing assay for transposase-accessible chromatin
(scATAC-seq) allows mapping of regulatory variation of thousands of cells at
the single-cell resolution. However, analyzing the scATAC-seq data is
computationally challenging due to the sparsity, high dimensionality, and
the nature of the binary signal. In this thesis, we proposed scOpen, a
computational approach for quantification of single-cell open chromatin
status and reduction of the dimensionality based on the non-negative matrix
factorization (NMF) topic modeling. We demonstrated that scOpen can improve
several crucial downstream analysis steps of scATAC-seq, such as clustering,
visualization, cis-regulatory DNA interactions, and delineation of
regulatory features. We also applied scOpen to investigate the regulatory
programs that drive the development of chronic kidney disease (CKD).
Altogether, these results demonstrate that scOpen is a useful computational
approach in single-cell open chromatin data analysis.
Es laden ein: die Dozentinnen und Dozenten der Informatik
_______________________________
Leany Maaßen
RWTH Aachen University
Lehrstuhl Informatik 5, LuFG Informatik 5
Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke,
Prof. Gerhard Lakemeyer Ph.D.
Ahornstrasse 55
D-52074 Aachen
Tel: 0241-80-21509
Fax: 0241-80-22321
E-Mail: maassen(a)dbis.rwth-aachen.de