Felix Reidl

We show that the VC-dimension of a graph can be computed in time n|log d+1| dO(d), where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time O(d2dn), afterwards queries can be computed efficiently using fast Möbius inversion. This data structure turns out to be useful for a range of tasks, especially for finding bipartite patterns in degenerate graphs, and we outline an efficient algorithm for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(nc), where c is a parameter of the pattern we call its left covering number. Concrete applications of this algorithm include counting the number of (non-induced) bicliques in linear time, the number of co-matchings in quadratic time, as well as a constant-factor approximation of the ladder index in linear time. Finally, we supplement our theoretical results with several implementations and run experiments on more than 200 real-world datasets—the largest of which has 8 million edges—where we obtain interesting insights into the VC-dimension of real-world networks.

Background: Knowledge about artifacts in optical coherence tomography angiography (OCTA) is important to avoid misinterpretations. An overview of possible artifacts in posterior uveitis provides important information for interpretations. Methods: In this monocentric prospective study, OCTA images from a total of 102 eyes of 54 patients with posterior uveitis, and an age-matched control group including 34 healthy subjects (67 eyes), were evaluated (day 0, month 3, month 6). We assigned different artifacts to distinct layers. Various types of artifacts were examined in different retinal layers. The χ2 test for the comparison between the control and uveitis group and Cochran’s Q test for the longitudinal comparison within the uveitis group were used. Results: A total of 2238 images were evaluated; 1836 from uveitis patients and 402 from healthy subjects. A total of 2193 artifacts were revealed. Projection (812 [36.3%]), segmentation (579 [25.9%]), shadowing (404 [18.1%]), and blink artifacts (297 [13.3%]) were the most common artifact types. The uveitis group displayed significantly more segmentation artifacts and projection artifacts (p < 0.001). No segmentation artifacts were documented in healthy subjects. The consecutive examinations within the uveitis group revealed the same artifact types without significance (p > 0.1). Conclusions: The uveitis patients showed more segmentation and projection artifacts than the control group. Within the uveitis group, artifacts remained longitudinally constant in terms of artifact type and pattern. The artifacts therefore appear to be reproducible on an individual level.

Microbial strains have closely related genomes but may have different phenotypes in the same environment. Shotgun metagenomic sequencing can capture the genomes of all strains present in a community but strain-resolved analysis from shotgun sequencing alone remains difficult. We developed an approach to identify and interrogate strain-level differences in groups of metagenomes. We use this approach to perform a meta-analysis of stool microbiomes from individuals with and without inflammatory bowel disease (IBD; Crohn’s disease, ulcerative colitis; n = 605), a disease for which there are not specific microbial biomarkers but some evidence that microbial strain variation may stratify by disease state. We first developed a machine learning classifier based on compressed representations of complete metagenomes (FracMinHash sketches) and identified genomes that correlate with IBD subtype. To rescue variation that may not have been present in the genomes, we then used assembly graph genome queries to recover strain variation for correlated genomes. Lastly, we developed a novel differential abundance framework that works directly on the assembly graph to uncover all sequence variants correlated with IBD. We refer to this approach as dominating set differential abundance analysis and have implemented it in the spacegraphcats software package . Using this approach, we identified five bacterial strains that are associated with Crohn’s disease. Our method captures variation within the entire sequencing data set, allowing for discovery of previously hidden disease associations.

We unify and extend previous kernelization techniques in sparse classes [6,17] by defining water lilies and show how they can be used in bounded expansion classes to construct linear bikernels for (r, c)-Dominating Set, (r, c)-Scattered Set, Total r-Domination, r-Roman Domination, and a problem we call (r, [{\lambda}, {\mu}])-Domination (implying a bikernel for r-Perfect Code). At the cost of slightly changing the output graph class our bikernels can be turned into kernels. We further demonstrate how these constructions can be combined to create 'multikernels', meaning graphs that represent kernels for multiple problems at once. Concretely, we show that r-Dominating Set, Total r-Domination, and r-Roman Domination admit a multikernel; as well as r-Dominating Set and 2r-Independent Set for multiple values of r at once.