Department of Computer Science & Engineering

Abstract Motivation Viral surveillance from mixed samples (e.g. wastewater) has become critical in public health efforts to track and contain pathogens. However, existing open-source bioinformatics tools for viral consensus sequence generation are optimized for individual viruses (rather than multiple potential viruses of interest). Results MultiVirusConsensus (MVC) is an accurate and efficient open-source pipeline for identification and consensus sequence generation of multiple viruses from mixed samples. It utilizes the memory-efficient ViralConsensus tool to simultaneously perform consensus sequence calling on all viruses of interest (1) completely in parallel, and (2) by piping datastreams between tools without writing/reading intermediate files (thus eliminating slowdowns related to slow disk accesses). Availability MultiVirusConsensus (MVC) is freely available as an open-source software project at: https://github.com/niemasd/MultiVirusConsensus Supplementary information Supplementary data are available at Bioinformatics online.

Abstract. We study the power of query access for the fundamental task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels of the examples, and the goal is to compute a hypothesis that is competitive with the best-fit function in a known class; i.e., it achieves error [Formula: see text], where [Formula: see text] is the error of the best function in the class. We focus on a general family of multi-Index models (MIMs), which are [Formula: see text]-variate functions that depend only on a few relevant directions, i.e., have the form [Formula: see text] for an unknown link function [Formula: see text] and a [Formula: see text] matrix [Formula: see text]. MIMs cover a wide range of commonly studied function classes, including real-valued function classes, such as constant-depth neural networks with ReLU activations, and Boolean concept classes, such as intersections of halfspaces. Our main result shows that query access gives significant runtime improvements over random examples for agnostically learning both real-valued and Boolean-valued MIMs. Under standard regularity assumptions for the link function (namely, bounded variation or surface area), we give an agnostic query learner for MIMs with running time [Formula: see text]. In contrast, algorithms that rely only on random labeled examples inherently require [Formula: see text] samples and runtime, even for the basic problem of agnostically learning a single ReLU or a halfspace. As special cases of our general approach, we obtain the following results: [Formula: see text] For the class of depth-[Formula: see text], width-[Formula: see text] ReLU networks on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. This bound qualitatively matches the runtime of an algorithm by Chen, Klivans, and Meka [ Learning deep ReLU networks is fixed-parameter tractable, 2022] for the realizable PAC setting with random examples. [Formula: see text] For the class of arbitrary intersections of [Formula: see text] halfspaces on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. Prior to our work, no improvement over the agnostic PAC model complexity (without queries) was known, even for the case of a single halfspace. In both these settings, we provide evidence that the [Formula: see text] runtime dependence is required for proper query learners, even for agnostically learning a single ReLU or halfspace. Our algorithmic result establishes a strong computational separation between the agnostic PAC and the agnostic PAC + Query models under the Gaussian distribution for a range of natural function classes. Prior to our work, no such separation was known for any natural concept class, even for the case of a single halfspace, for which it was an open problem posed by Feldman [ On the power of membership queries in agnostic learning, 2008]. Our results are enabled by a general dimension-reduction technique that leverages query access to estimate gradients of (a smoothed version of) the underlying label function.

The standard response to the student mental health crisis has been to expand clinical capacity by hiring more therapists and increasing funding. We challenge this approach. Through a two-part study with 154 undergraduate students and 9 campus providers at a large US university, we found that students considered physical and mental health a lower priority than other factors in their daily life. Universities offer a wide range of wellness resources, but most students simply unaware of their existence. Our findings suggest that the core issue is not necessarily a supply shortage, but rather fragmented access and limited visibility of resources. We argue that institutions should focus on building aggregator platforms that help students discover and navigate the support already available to them, as a means for a sustainable solution. This reframing suggests universities should rethink resource allocation: designing for student discovery and access to holistic well-being support beyond the clinic.

MOTIVATION: Exome sequencing is widely used for genetic studies; however, accurate detection of copy number variants (CNV) in paralogous genes is challenging due to short-read mapping ambiguity and extensive copy-number variation. The human genome contains several hundred paralogous genes, many of which are known to harbor disease-associated CNVs. Existing exome CNV callers are primarily designed for rare CNV detection in uniquely mappable regions and are not well-suited for paralogous genes. METHODS: We describe a computational method (EdgeCopy) for copy number profiling of paralogous genes using whole-exome sequence data. EdgeCopy aggregates reads mapped to all copies of paralogous genes and relates observed read depth to copy number for multiple exome samples using an approximate composite likelihood function. The likelihood function is optimized using numerical optimization to obtain gene-level fractional copy number estimates that are discretized and refined using a Hidden Markov Model to obtain exon-level copy number estimates. RESULTS: Benchmarking of Edgecopy using experimental copy number data showed high concordance (mean = 0.973) for six disease-associated paralogous genes. We evaluated performance using whole-exome data from approximately 2400 samples across five continental populations from the 1000 Genomes Project. EdgeCopy shows robust concordance with whole-genome sequencing based estimates (0.974-0.982) across populations and 130 paralogous genes spanning a wide range of copy-number variation. In comparison, copy number analysis using a state-of-the-art exome CNV caller failed to estimate copy number for paralogous genes with very high mapping ambiguity and showed much lower concordance (0.565) for CNV events compared to EdgeCopy (0.908). AVAILABILITY: EdgeCopy is freely available at https://github.com/vibansal-lab/edgecopy.

Opinion 133 addresses the unusual situation of two genus names that are homonyms and are also considered heterotypic synonyms. Furthermore, it clarifies the meaning of the term 'homonym' in the International Code of Nomenclature of Prokaryotes, as well as the implications of the absence of the term 'isonym' from that code. Isonyms are homotypic synonyms with the same spelling and as such are adequately regulated by the code. The Judicial Commission agrees that the names Methylacidiphilum caldifontis Awala et al. 2023, Methylacidiphilum Awala et al. 2023, Methylacidiphilaceae Awala et al. 2023 and Methylacidiphilales Awala et al. 2023 are illegitimate. The possible actions to resolve this illegitimacy are outlined. The request to conserve Methylacidiphilum Awala et al. 2023 over Methylacidiphilum Ratnadevi et al. 2023 is not granted. However, Methylacidiphilaceae Awala et al. 2023 and Methylacidiphilales Awala et al. 2023 are conserved with Methylacidiphilum Ratnadevi et al. 2023 as the type genus, thereby rendering them legitimate. Opinion 134 addresses two distinct enquiries arising from the same Request for an Opinion. The Judicial Commission confirms that the priority between Yokenella regensburgei Kosako et al. 1985 and its heterotypic synonym Koserella trabulsii Hickman-Brenner et al. 1985 may at present be unresolved. Considering previous statements by the Judicial Commission, the differences in the amount of usage between the two names and their medical relevance, the request is granted. The name Yokenella Kosako et al. 1985 is conserved over Koserella Hickman-Brenner et al. 1985, as is the epithet in Yokenella regensburgei Kosako et al. 1985 over the epithet in Koserella trabulsii Hickman-Brenner et al. 1985. The Judicial Commission also confirms that the epithet in Proteus inconstans (Ornstein 1920) Shaw and Clarke 1955 (Approved Lists 1980) has priority over the one in its homotypic synonym Providencia alcalifaciens (de Salles Gomes 1944) Ewing 1962 (Approved Lists 1980). However, it is doubtful whether this renders Providencia Ewing 1962 (Approved Lists 1980) illegitimate. There are other reasons to conserve the epithet in Providencia alcalifaciens (de Salles Gomes 1944) Ewing 1962 (Approved Lists 1980) over that in Proteus inconstans (Ornstein 1920) Shaw and Clarke 1955 (Approved Lists 1980), and this request is also granted.

All-pairs shortest paths is a fundamental algorithm used for routing, logistics, and network analysis, but the cubic time complexity and heavy data movement of the canonical Floyd-Warshall algorithm severely limits its scalability on conventional CPUs or GPUs. In this paper, we propose PIM-FW, a novel co-designed hardware architecture and dataflow leveraging processing in and near memory to accelerate the blocked FW algorithm on an HBM3 stack. To enable fine-grained parallelism, we propose a massively parallel array of specialized bit-serial bank and channel PEs designed to accelerate core min-plus operations. Our dataflow complements this hardware, employing an interleaved mapping policy for superior load balancing and a hybrid memory computing model for efficient computation and reduction. This in-bank computing approach allows all distance updates to be performed and stored locally, a key contribution which eliminates the data-movement bottleneck inherent in GPU-based approaches. We implement a full hardware-software co-design using a cycle-accurate simulator for an 8-channel, 4-Hi HBM3 stack on real road-network traces. Experimental results show that, for an 8, 192 × 8, 192 graph, PIM-FW achieves an 18.7 × speedup and consumes 3200 × lower memory-stack/accelerator-side energy under our modeled PIM stack assumptions compared to a state-of-the-art GPU-only Floyd-Warshall.

Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm should be able to distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR), a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the area, it remains unclear whether low-degree indistinguishability actually rules out any interesting class of algorithms. In this work, we initiate the study and develop technical tools for translating LDLR upper bounds into rigorous lower bounds against concrete algorithms. As a consequence, for any permutation-invariant distribution P, we prove: 1.) If is over {0,1}n and is low-degree indistinguishable from U = ({0,1}n), then a noisy version of is statistically indistinguishable from U. 2.) If is over n and is low-degree indistinguishable from the standard Gaussian (0, 1)n, then no statistic based on symmetric polynomials of degree at most O(logn/loglogn) can distinguish between a noisy version of from (0, 1)n. 3.) If is over n× n and is low-degree indistinguishable from (0,1)n× n, then no constant-sized subgraph statistic can distinguish between a noisy version of and (0, 1)n× n. To obtain our results, we depart significantly from techniques typically used in the context of low-degree lower bounds. Instead, we show total variation closeness by carefully analyzing the Fourier transform of polynomials under the input distributions.

In list-decodable learning, we are given a set of data points such that an α-fraction of these points come from a “nice” distribution D, for some small α ≪ 1, and the goal is to output a short list of candidate solutions, such that at least one element of this list recovers some non-trivial information about D. By now, there is a large body of work on this topic; however, while many algorithms can achieve optimal list size in terms of α, all known algorithms must incur error which decays, in some cases quite poorly, with 1 / α. In this paper, we ask if this is inherent: is it possible to trade off list size with accuracy in list-decodable learning? More formally, given ε > 0, can we output a slightly larger list in terms of α and ε, but so that one element of this list has error at most ε with the ground truth? We call this problem high-accuracy list-decodable learning. Our main result is that non-trivial high-accuracy guarantees, both information-theoretically and algorithmically, are possible for the canonical setting of list-decodable mean estimation of identity-covariance Gaussians. Specifically, we demonstrate that there exists a list of candidate means of size at most L = exp( O( log2 1 / α/ε2 )) so that one of the elements of this list has ℓ2 distance at most ε to the true mean. We also design an algorithm that outputs such a list with runtime and sample complexity n = dO(logL) + expexp(O(logL)). In particular, our results demonstrate that in the natural regime where α and ε are both small constants, it is possible to achieve error ≤ 0.01 in fully-polynomial time, where all prior work suffered error which was much larger than 1. We do so by demonstrating a completely novel proof of identifiability, as well as a new algorithmic way of leveraging this proof without the sum-of-squares hierarchy, which may be of independent technical interest.