"Data driven governing equations approximation using deep neural networks", Journal of Computational Physics (2019) will be discussed in this Journal Club. We present a numerical framework for approximating unknown governing equations using observation data and deep neural networks (DNN). In particular, we propose to use residual network (ResNet) as the basic building block for equation approximation. We demonstrate that the ResNet block can be considered as a one-step method that is exact in temporal integration. We then present two multi-step methods, recurrent ResNet (RT-ResNet) method and recursive ReNet (RS-ResNet) method. The RT-ResNet is a multi-step method on uniform time steps, whereas the RS-ResNet is an adaptive multi-step method using variable time steps. All three methods presented here are based on integral form of the underlying dynamical system. As a result, they do not require time derivative data for equation recovery and can cope with relatively coarsely distributed trajectory data. Several numerical examples are presented to demonstrate the performance of the methods. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020, JACM 2022) to break a natural long-standing barrier in edge-weighted online bipartite matching. They posed two open questions, one of which was the following: Can we obtain n-way OCS for $n >2$, in which the algorithm can be given $n >2$ elements to choose from at each timestep? In this talk, we affirmatively answer this open question by presenting a three-way OCS which is simple to describe: it internally runs two instances of two-way OCS, one of which is fed with the output of the other. Contrast to its simple construction, we face a new challenge in analysis that the final output probability distribution of our three-way OCS is highly elusive since it requires the actual output distribution of two-way OCS. We show how we tackle this challenge by approximating the output distribution of two-way OCS by a flatter distribution serving as a safe surrogate. This is joint work with Hyung-Chan An.

"PenDA, a rank-based method for personalized differential analysis: Application to lung cancer", Plos Comp. Biol. (2020) will be discussed in this Journal Club. The hopes of precision medicine rely on our capacity to measure various high-throughput genomic information of a patient and to integrate them for personalized diagnosis and adapted treatment. Reaching these ambitious objectives will require the development of efficient tools for the detection of molecular defects at the individual level. Here, we propose a novel method, PenDA, to perform Personalized Differential Analysis at the scale of a single sample. PenDA is based on the local ordering of gene expressions within individual cases and infers the deregulation status of genes in a sample of interest compared to a reference dataset. Based on realistic simulations of RNA-seq data of tumors, we showed that PenDA outcompetes existing approaches with very high specificity and sensitivity and is robust to normalization effects. Applying the method to lung cancer cohorts, we observed that deregulated genes in tumors exhibit a cancer-type-specific commitment towards up- or down-regulation. Based on the individual information of deregulation given by PenDA, we were able to define two new molecular histologies for lung adenocarcinoma cancers strongly correlated to survival. In particular, we identified 37 biomarkers whose up-regulation lead to bad prognosis and that we validated on two independent cohorts. PenDA provides a robust, generic tool to extract personalized deregulation patterns that can then be used for the discovery of therapeutic targets and for personalized diagnosis. An open-access, user-friendly R package is available at https://github.com/bcm-uga/penda. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

Very little is known about critical properties of graphs in the hierarchy of monotone classes, i.e. classes closed under taking (not necessarily induced) subgraphs. We distinguish four important levels in this hierarchy and discuss possible new levels by focusing on the Hamiltonian cycle problem. In particular, we obtain a number of results for this problem on monotone classes.

"Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories in Reprogramming", Cell (2019) will be discussed in this Journal Club. Understanding the molecular programs that guide differentiation during development is a major challenge. Here, we introduce Waddington-OT, an approach for studying developmental time courses to infer ancestor-descendant fates and model the regulatory programs that underlie them. We apply the method to reconstruct the landscape of reprogramming from 315,000 single-cell RNA sequencing (scRNA-seq) profiles, collected at half-day intervals across 18 days. The results reveal a wider range of developmental programs than previously characterized. Cells gradually adopt either a terminal stromal state or a mesenchymal-to-epithelial transition state. The latter gives rise to populations related to pluripotent, extra-embryonic, and neural cells, with each harboring multiple finer subpopulations. The analysis predicts transcription factors and paracrine signals that affect fates and experiments validate that the TF Obox6 and the cytokine GDF9 enhance reprogramming efficiency. Our approach sheds light on the process and outcome of reprogramming and provides a framework applicable to diverse temporal processes in biology. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

A cross-cap drawing of a graph G is a drawing on the sphere with g distinct points, called cross-caps, such that the drawing is an embedding except at the cross-caps, where edges cross properly. A cross-cap drawing of a graph G with g cross-caps can be used to represent an embedding of G on a non-orientable surface of genus g. Mohar conjectured that any triangulation of a non-orientable surface of genus g admits a cross-cap drawing with g cross-caps in which each edge of the triangulation enters each cross-cap at most once. Motivated by Mohar’s conjecture, Schaefer and Stefankovic provided an algorithm that computes a cross-cap drawing with a minimal number of cross-caps for a graph G such that each edge of the graph enters each cross-cap at most twice. In this talk, I will first outline a connection between cross-cap drawings and an algorithm coming from computational biology to compute the signed reversal distance between two permutations. This connection will then be leveraged to answer two computational problems on graphs embedded on surfaces. First, I show how to compute a “short” canonical decomposition for a non-orientable surface with a graph embedded on it. Such canonical decompositions were known for orientable surfaces, but the techniques used to compute them do not generalize to non-orientable surfaces due to their more complex nature. Second, I explain how to build a counter example to a stronger version of Mohar’s conjecture that is stated for pseudo-triangulations. This is joint work with Alfredo Hubard and Arnaud de Mesmay.

---

ZOOM ID: 997 8258 4700(pw: 1234)

In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉. In this talk, we prove that Aharoni’s conjecture holds up to an additive constant. Specifically, we show that for each fixed r, there exists a constant c such that if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most n/r+c. This is joint work with Patrick Hompe.

---

ZOOM ID: 997 8258 4700(pw: 1234)

A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies of graphs in $\mathcal F$ within $G$ such that any vertex of $G$ is contained in at most 2, respectively at most 4, of these copies, or there exists a vertex set $A$ of size at most $f(k)$ such that $G - A$ contains no copies of graphs in $\mathcal F$. Very recently we showed that even dicycles have the quarter-integral Erdős-Pósa property [STOC'24] via the proof of a structure theorem for digraphs without large packings of even dicycles. In this talk we discuss our current effort to improve this approach towards the half-integral Erdős-Pósa property, which would be best possible, as even dicycles do not have the integral Erdős-Pósa property. Complementing the talk given by Sebastian Wiederrecht in this seminar regarding our initial result, we also shine a light on some of the particulars of the embedding we use in lieu of flatness and how this helps us to move even dicycles through the digraph. In the process of this, we highlight the parts of the proof that initially caused the result to be quarter-integral. (This is joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht.)

"An improved rhythmicity analysis method using Gaussian Processes detects cell-density dependent circadian oscillations in stem cells", ArXiv. (2023) will be discussed in this Journal Club. Detecting oscillations in time series remains a challenging problem even after decades of research. In chronobiology, rhythms in time series (for instance gene expression, eclosion, egg-laying and feeding) datasets tend to be low amplitude, display large variations amongst replicates, and often exhibit varying peak-to-peak distances (non-stationarity). Most currently available rhythm detection methods are not specifically designed to handle such datasets. Here we introduce a new method, ODeGP (Oscillation Detection using Gaussian Processes), which combines Gaussian Process (GP) regression with Bayesian inference to provide a flexible approach to the problem. Besides naturally incorporating measurement errors and non-uniformly sampled data, ODeGP uses a recently developed kernel to improve detection of non-stationary waveforms. An additional advantage is that by using Bayes factors instead of p-values, ODeGP models both the null (non-rhythmic) and the alternative (rhythmic) hypotheses. Using a variety of synthetic datasets we first demonstrate that ODeGP almost always outperforms eight commonly used methods in detecting stationary as well as non-stationary oscillations. Next, on analyzing existing qPCR datasets that exhibit low amplitude and noisy oscillations, we demonstrate that our method is more sensitive compared to the existing methods at detecting weak oscillations. Finally, we generate new qPCR time-series datasets on pluripotent mouse embryonic stem cells, which are expected to exhibit no oscillations of the core circadian clock genes. Surprisingly, we discover using ODeGP that increasing cell density can result in the rapid generation of oscillations in the Bmal1 gene, thus highlighting our method’s ability to discover unexpected patterns. In its current implementation, ODeGP (available as an R package) is meant only for analyzing single or a few time-trajectories, not genome-wide datasets. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to B if and only if A maps homomorphically to Γ(B). If this is the case Λ is called the left adjoint to Γ and Γ the right adjoint to Λ. In 2015, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We shall present several recent advances in this direction including a new approach based on the notion of Datalog Program borrowed from logic.

"Phenotypic switching in gene regulatory networks", PNAS. (2014) will be discussed in this Journal Club. Noise in gene expression can lead to reversible phenotypic switching. Several experimental studies have shown that the abundance distributions of proteins in a population of isogenic cells may display multiple distinct maxima. Each of these maxima may be associated with a subpopulation of a particular phenotype, the quantification of which is important for understanding cellular decision-making. Here, we devise a methodology which allows us to quantify multimodal gene expression distributions and single-cell power spectra in gene regulatory networks. Extending the commonly used linear noise approximation, we rigorously show that, in the limit of slow promoter dynamics, these distributions can be systematically approximated as a mixture of Gaussian components in a wide class of networks. The resulting closed-form approximation provides a practical tool for studying complex nonlinear gene regulatory networks that have thus far been amenable only to stochastic simulation. We demonstrate the applicability of our approach in a number of genetic networks, uncovering previously unidentified dynamical characteristics associated with phenotypic switching. Specifically, we elucidate how the interplay of transcriptional and translational regulation can be exploited to control the multimodality of gene expression distributions in two-promoter networks. We demonstrate how phenotypic switching leads to birhythmical expression in a genetic oscillator, and to hysteresis in phenotypic induction, thus highlighting the ability of regulatory networks to retain memory. If you want to participate in the seminar, you need to enter IBS builiding (https://www.ibs.re.kr/bimag/visiting/). Please contact if you first come IBS to get permission to enter IBS building.

Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid is a pair $D=(V,\mathcal F)$ where $\mathcal F$ is a collection of subsets of V known as "feasible sets." (They can be thought of as generalizing the set of bases of a matroid, while relaxing the condition that all bases must have the same cardinality.) Like with matroids, an important class of delta-matroids are linear delta-matroids, where the feasible sets are represented via a skew-symmetric matrix. Prominent examples of linear delta-matroids include linear matroids and matching delta-matroids (where the latter are represented via the famous Tutte matrix). However, the study of algorithms over delta-matroids seems to have been much less developed than over matroids. In this talk, we review recent results on representations of and algorithms over linear delta-matroids. We first focus on classical polynomial-time aspects. We present a new (equivalent) representation of linear delta-matroids that is more suitable for algorithmic purposes, and we show that so-called delta-sums and unions of linear delta-matroids are linear. As a result, we get faster (randomized) algorithms for Linear Delta-matroid Parity and Linear Delta-matroid Intersection, improving results from Geelen et al. (2004). We then move on to parameterized complexity aspects of linear delta-matroids. We find that many results regarding linear matroids which have had applications in FPT algorithms and kernelization directly generalize to linear delta-matroids of bounded rank. On the other hand, unlike with matroids, there is a significant difference between the "rank" and "cardinality" parameters - the structure of bounded-cardinality feasible sets in a delta-matroid of unbounded rank is significantly harder to deal with than feasible sets in a bounded-rank delta-matroid.

---

ZOOM ID: 997 8258 4700(pw: 1234)

The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) - p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is a $d$-regular graph on $n$ vertices and $d = O(n^{1/9})$, then the positive discrepancy of $G$ is at least $c d^{1/2}n$ for some constant $c$. We extend this result by proving lower bounds for the positive discrepancy with average degree d when $d < (1/2 - \epsilon)n$. We prove that the same lower bound remains true when $d < n^(2/3)$, while in the ranges $n^{2/3} < d < n^{4/5}$ and $n^{4/5} < d < (1/2 - \epsilon)n$ we prove that the positive discrepancy is at least $n^2/d$ and $d^{1/4}n/log(n)$ respectively. Our proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when $d < n^{3/4}$, thus demonstrating a change in the behaviour around $d = n^{2/3}$ when a random graph no longer minimises the positive discrepancy. As a by-product, we also present lower bounds for the second largest eigenvalue of a $d$-regular graph when $d < (1/2 - \epsilon)n$, thus extending the celebrated Alon-Boppana theorem. This is joint work with Benjamin Sudakov and István Tomon.

---

ZOOM ID: 997 8258 4700(pw: 1234)

Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs $\ell$ and $k$. We precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$. This is joint work with Ervin Győri, Binlong Li, Nika Salia, Kitti Varga and Manran Zhu.