To join the email distribution list of the cs colloquia, please visit the list subscription page.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
The Capacity of the Weighted Read Channel
Nanopore sequencing is emerging as a powerful tool for storing digital information in DNA molecules. This technique offers several advantages over traditional methods, making it an attractive area of research. In this work, we focus on a simplified model of the nanopore sequencing process, represented as a channel.
This channel operates by taking a DNA sequence and analyzing it one segment at a time. It uses a sliding window of a specific length, denoted by ℓ, to scan the sequence. The window is then shifted by δ characters, and the process repeats. The output of the channel called the read vector, is a collection of values where each value represents the sum of the bases (like A, C, G, T) within a particular window.
The channel’s capacity signifies the maximum rate of information transmission through it. Prior research has established capacity values for specific combinations of ℓ and δ. In this study, we delve deeper, demonstrating that when δ < ℓ < 2δ, the channel’s capacity can be expressed as (1/δ) log (1/2 (ℓ + 1 +√((ℓ + 1)2 − 4(ℓ − δ)(ℓ − δ + 1))). Furthermore, we establish an upper bound on the capacity when 2δ is less than ℓ. Finally, to enhance the model’s complexity, we extendit to a two-dimensional scenario and present various findings on its capacity. This extended model brings us closer to mimicking the real intricacies of nanopore sequencing and its potential for DNA storage
Drug Target Prediction by Learning from High-Throughput Metabolomics Data and Metabolic Pathway StructuresOMICS-based screening offers a promising approach for untargeted drug discovery. Mass-spectrometry metabolomics and proteomics were recently used for inferring drug mechanisms of action and off-target effects, analyzing the cellular response to treatment with numerous clinically approved drugs and tool compounds. In this talk, we present a novel high-throughput LC-MS metabolomics screening pipeline and a deep-learning method specifically designed for cellular metabolism.
Our novel Graph Neural Network (GNN) model fits the unique structure of this domain, enabling accurate identification of target pathways. Learning from time- and dose-dependent metabolic responses of cultured cells treated with 76 known metabolic inhibitors, we correctly identified the target pathway within the top three ranked pathways for ~50% of the drugs. Applying this approach to a diversity library of 1,020 drug-like compounds, we discovered five novel inhibitors targeting clinically relevant pathways and enzymes involved in purine and pyrimidine biosynthesis and redox metabolism. Our pipeline is readily scalable for screening thousands of compounds to identify new, clinically relevant metabolic inhibitors.
We will dive deep into our machine learning approach, offering valuable insights and comprehensive ablation studies that highlight its strength and domain-specific innovation.
Randomized and Continuous Algorithms for Submodular MaximizationSubmodular functions arise in various fields, including combinatorics, graph theory, information theory, and economics. This thesis addresses two key problems in submodular maximization and presents new algorithmic contributions. The first focuses on the Online Submodular Welfare problem, where bidders with submodular utility functions compete for items arriving sequentially. We propose a randomized algorithm that achieves a tight competitive ratio of 1/4 under adversarial arrivals and improve this to approximately 0.27493 under random arrivals. The second result introduces a Greedy Poisson Process for submodular maximization under matroid constraints, achieving a tight (1 − 1/e − ϵ)-approximation without requiring discretization or rounding. Our algorithm introduces a new framework for submodular maximization under matroid constraints, combining the strengths of both continuous and discrete approaches.
Persistency Race DetectionNonvolatile Memory (NVM) technologies offer new avenues for building high-performance and crash-consistent applications by combining byte-addressable DRAM-like characteristics with non-volatility. However, these features introduce complex challenges in ensuring data consistency, especially under concurrent access scenarios.
This paper introduces PRD, a specialized tool designed to detect persistency races - specific type of concurrency bugs in PM environments that can lead to critical inconsistencies following system failures.
PRD utilizes graph-theoretical analysis along with happens-before and program-dependence analysis to map causal relationships and dependencies among program operations. While these analyses are well-established techniques in data-race detection, PRD efficiently generalizes across multiple thread interleavings to detect potential races within a single program execution, significantly enhancing the speed and efficiency of race detection in NVM environments.
