We introduce Themis, a scheme for introducing fair ordering of transactions into (permissioned) Byzantine consensus protocols with at most ƒ faulty nodes among n ≥ 4ƒ + 1. Themis enforces the strongest notion of fair ordering proposed to date. It also achieves standard liveness, rather than the weaker notion of previous work with the same fair ordering property.

Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper, we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure - our Trustboost protocols achieve the optimal threshold of tolerating the insecure blockchains. This optimality, along with the necessity of blockchain interactions, is formally shown within the classic shared memory model, tackling the long standing open challenge of solving consensus in the presence of both Byzantine objects and processes. Furthermore, our proposed construction of Trustboost simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of "consensus on top of consensus''. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying Trustboost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source [52]. Our evaluation shows that using 10 Cosmos chains in a local testnet, Trustboost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.

Peer-to-peer (P2P) networks underlie a variety of decentralized paradigms including blockchains, distributed file storage and decentralized domain name systems. A central primitive in P2P networks is the peer selection algorithm, which decides how a node should select a fixed number of neighbors to connect with. In this paper, we consider the design of a peer selection algorithm for unstructured P2P networks with the goal of minimizing the broadcast latency. We propose Goldfish, a novel solution that dynamically decides the neighbor set by exploiting the past experiences as well as exploring new neighbors. The key technical contributions come from bringing ideas of matrix completion for estimating message delivery times for every possible message for every peer ever connected, and a streaming algorithm to efficiently perform the estimation while achieving good performance. The matrix completion interpolates the delivery times to all virtual connections in order to select the best combination of neighbors. Goldfish employs a streaming algorithm that only uses a short recent memory to finish matrix interpolation. When the number of publishing source is equal to a node's maximal number of connections, Goldfish found the global optimal solution with 92.7% probability by exploring every node only once. In more complex situations where nodes are publishing based on exponential distribution and adjusting connection in real time, we compare Goldfish with a baseline peer selection system, Perigee [1], and show Goldfish saves approximately 14.5% less time under real world geolocation and propagation latency.

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners. Proof-of-Stake chains are energy-efficient, have fast finality but face several security issues: susceptibility to non-slashable long-range safety attacks, low liveness resilience and difficulty to bootstrap from low token valuation. We show that these security issues are inherent in any PoS chain without an external trusted source, and propose a new protocol, Babylon, where an off-the-shelf PoS protocol checkpoints onto Bitcoin to resolve these issues. An impossibility result justifies the optimality of Babylon. A use case of Babylon is to reduce the stake withdrawal delay: our experimental results show that this delay can be reduced from weeks in existing PoS chains to less than 5 hours using Babylon, at a transaction cost of less than 10K USD per annum for posting the checkpoints onto Bitcoin.

MOTIVATION: Detection of structural variants (SVs) from the alignment of sample DNA reads to the reference genome is an important problem in understanding human diseases. Long reads that can span repeat regions, along with an accurate alignment of these long reads play an important role in identifying novel SVs. Long-read sequencers, such as nanopore sequencing, can address this problem by providing very long reads but with high error rates, making accurate alignment challenging. Many errors induced by nanopore sequencing have a bias because of the physics of the sequencing process and proper utilization of these error characteristics can play an important role in designing a robust aligner for SV detection problems. In this article, we design and evaluate HQAlign, an aligner for SV detection using nanopore sequenced reads. The key ideas of HQAlign include (i) using base-called nanopore reads along with the nanopore physics to improve alignments for SVs, (ii) incorporating SV-specific changes to the alignment pipeline, and (iii) adapting these into existing state-of-the-art long-read aligner pipeline, minimap2 (v2.24), for efficient alignments. RESULTS: We show that HQAlign captures about 4%-6% complementary SVs across different datasets, which are missed by minimap2 alignments while having a standalone performance at par with minimap2 for real nanopore reads data. For the common SV calls between HQAlign and minimap2, HQAlign improves the start and the end breakpoint accuracy by about 10%-50% for SVs across different datasets. Moreover, HQAlign improves the alignment rate to 89.35% from minimap2 85.64% for nanopore reads alignment to recent telomere-to-telomere CHM13 assembly, and it improves to 86.65% from 83.48% for nanopore reads alignment to GRCh37 human genome. AVAILABILITY AND IMPLEMENTATION: https://github.com/joshidhaivat/HQAlign.git.

Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded.

The problem of decomposing a graph flow into a small set of paths has a wide range of applications, including transcriptome assembly and routing in data networks. A standard formulation is the sparsest flow decomposition problem, which is known to be NP-hard. In this work, we consider a multi-sample variant of this problem, motivated by the problem of identifying and quantifying proteoforms from mass spectrometry data, where multiple views of the graph can be obtained from multiple biological samples. We derive necessary conditions for the set of samples to unambiguously determine the ground truth set of paths, and we design an algorithm with matching sufficient conditions for a large class of problem instances, making our algorithm information optimal for this class of problem instances. The necessary conditions, combined with a probabilistic model for sample generation, yield a characterization of the number of samples needed for unambiguous recovery of the underlying paths. We analyze the algorithm’s performance on flow data simulated on peptide graphs from real mass spectrometry data.

Proof of Work (PoW) blockchains are susceptible to adversarial majority mining attacks in the early stages due to incipient participation and corresponding low net hash power. Bootstrapping ensures safety and liveness during the transient stage by protecting against a majority mining attack, allowing a PoW chain to grow the participation base and corresponding mining hash power. Liveness is especially important since a loss of liveness will lead to loss of honest mining rewards, decreasing honest participation, hence creating an undesired spiral; indeed existing bootstrapping mechanisms offer especially weak liveness guarantees.

MOTIVATION: Single-cell RNA sequencing (scRNA-seq) is widely used for analyzing gene expression in multi-cellular systems and provides unprecedented access to cellular heterogeneity. scRNA-seq experiments aim to identify and quantify all cell types present in a sample. Measured single-cell transcriptomes are grouped by similarity and the resulting clusters are mapped to cell types based on cluster-specific gene expression patterns. While the process of generating clusters has become largely automated, annotation remains a laborious ad hoc effort that requires expert biological knowledge. RESULTS: Here, we introduce CellMeSH-a new automated approach to identifying cell types for clusters based on prior literature. CellMeSH combines a database of gene-cell-type associations with a probabilistic method for database querying. The database is constructed by automatically linking gene and cell-type information from millions of publications using existing indexed literature resources. Compared to manually constructed databases, CellMeSH is more comprehensive and is easily updated with new data. The probabilistic query method enables reliable information retrieval even though the gene-cell-type associations extracted from the literature are noisy. CellMeSH is also able to optionally utilize prior knowledge about tissues or cells for further annotation improvement. CellMeSH achieves top-one and top-three accuracies on a number of mouse and human datasets that are consistently better than existing approaches. AVAILABILITY AND IMPLEMENTATION: Web server at https://uncurl.cs.washington.edu/db_query and API at https://github.com/shunfumao/cellmesh. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Byzantine fault-tolerant (BFT) protocols allow a group of replicas to come to consensus even when some of the replicas are Byzantine faulty. There exist multiple BFT protocols to securely tolerate an optimal number of faults t under different network settings. However, if the number of faults f exceeds t then security could be violated. In this paper we mathematically formalize the study of forensic support of BFT protocols: we aim to identify (with cryptographic integrity) as many of the malicious replicas as possible and in as distributed manner as possible. Our main result is that forensic support of BFT protocols depends heavily on minor implementation details that do not affect the protocol's security or complexity. Focusing on popular BFT protocols (PBFT, HotStuff, Algorand) we exactly characterize their forensic support, showing that there exist minor variants of each protocol for which the forensic supports vary widely. We show strong forensic support capability of LibraBFT, the consensus protocol of Diem cryptocurrency; our lightweight forensic module implemented on a Diem client is open-sourced and is under active consideration for deployment in Diem. Finally, we show that all secure BFT protocols designed for 2t+1 replicas communicating over a synchronous network forensic support is inherently nonexistent; this impossibility result holds for all BFT protocols and even if one has access to the states of all replicas (including Byzantine ones).

Several emerging proof-of-work (PoW) blockchain protocols rely on a ''parallel-chain'' architecture for scaling, where instead of a single chain, multiple chains are run in parallel and aggregated. A key requirement of practical PoW blockchains is to adapt to mining power variations over time (Bitcoin's total mining power has increased by a 1014 factor over the decade). In this paper, we consider the design of provably secure parallel-chain protocols which can adapt to such mining power variations.

MOTIVATION: Efficient and accurate alignment of DNA/RNA sequence reads to each other or to a reference genome/transcriptome is an important problem in genomic analysis. Nanopore sequencing has emerged as a major sequencing technology and many long-read aligners have been designed for aligning nanopore reads. However, the high error rate makes accurate and efficient alignment difficult. Utilizing the noise and error characteristics inherent in the sequencing process properly can play a vital role in constructing a robust aligner. In this article, we design QAlign, a pre-processor that can be used with any long-read aligner for aligning long reads to a genome/transcriptome or to other long reads. The key idea in QAlign is to convert the nucleotide reads into discretized current levels that capture the error modes of the nanopore sequencer before running it through a sequence aligner. RESULTS: We show that QAlign is able to improve alignment rates from around 80% up to 90% with nanopore reads when aligning to the genome. We also show that QAlign improves the average overlap quality by 9.2, 2.5 and 10.8% in three real datasets for read-to-read alignment. Read-to-transcriptome alignment rates are improved from 51.6% to 75.4% and 82.6% to 90% in two real datasets. AVAILABILITY AND IMPLEMENTATION: https://github.com/joshidhaivat/QAlign.git. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Gating is a key feature in modern neural networks including LSTMs, GRUs and sparsely-gated deep neural networks. The backbone of such gated networks is a mixture-of-experts layer, where several experts make regression decisions and gating controls how to weigh the decisions in an input-dependent manner. Despite having such a prominent role in both modern and classical machine learning, very little is understood about parameter recovery of mixture-of-experts since gradient descent and EM algorithms are known to be stuck in local optima in such models.In this paper, we perform a careful analysis of the optimization landscape and show that with appropriately designed loss functions, gradient descent can indeed learn the parameters accurately. A key idea underpinning our results is the design of two {\em distinct} loss functions, one for recovering the expert parameters and another for recovering the gating parameters. We demonstrate the first sample complexity results for parameter recovery in this model for any algorithm and demonstrate significant performance gains over standard loss functions in numerical experiments.

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

Designing channel codes is one of the core research areas for modern communication systems. Canonical channel codes asymptotically achieve near-capacity performance under large block length regime for additive white gaussian noise channels. However, this achieved success does not generalize to many channels. Channels with output feedback, proposed by Shannon, is one of such channels where practical codes have been unknown for several decades.Recently it has been demonstrated that deep learning based code outperforms the state-of-the-art codes for channels with output feedback. While the success is promising and inspiring, there are a few major challenges that need to be addressed. Firstly, the channel assumes a feedback with a unit step delay, which is not very practical. Second is the lack of generalization to larger block lengths. In this work, we propose Feedback Auto Turbo Encoder (FTAE) which harmoniously combines interleaver and iterative decoding with CNN architectures and demonstrate the blocklength gain and improved performance in the block feedback setting.

Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

A key performance metric in blockchains is the latency between when a transaction is broadcast and when it is confirmed (the so-called, confirmation latency). While improvements in consensus techniques can lead to lower confirmation latency, a fundamental lower bound on confirmation latency is the propagation latency of messages through the underlying peer-to-peer (p2p) network (in Bitcoin, the propagation latency is several tens of seconds). The de facto p2p protocol used by Bitcoin and other blockchains is based on random connectivity: each node connects to a random subset of nodes. The induced p2p network topology can be highly suboptimal since it neglects geographical distance, differences in bandwidth, hash-power and computational abilities across peers. We present Perigee, a decentralized algorithm that automatically learns an efficient p2p topology tuned to the aforementioned network heterogeneities, purely based on peers' interactions with their neighbors. Motivated by the literature on the multi-armed bandit problem, Perigee optimally balances the tradeoff between retaining connections to known well-connected neighbors, and exploring new connections to previously-unseen neighbors. Experimental evaluations show that Perigee reduces the latency to broadcast by 33%. Lastly Perigee is simple, computationally lightweight, adversary-resistant, and compatible with the selfish interests of peers, making it an attractive p2p protocol for blockchains.

Estimation of information theoretic quantities such as mutual information and its conditional variant has drawn interest in recent times owing to their multifaceted applications. Newly proposed neural estimators for these quantities have overcome severe drawbacks of classical $k$NN-based estimators in high dimensions. In this work, we focus on conditional mutual information (CMI) estimation by utilizing its formulation as a \textit{minmax} optimization problem. Such a formulation leads to a joint training procedure similar to that of generative adversarial networks. We find that our proposed estimator provides better estimates than the existing approaches on a variety of simulated datasets comprising linear and non-linear relations between variables. As an application of CMI estimation, we deploy our estimator for conditional independence (CI) testing on real data and obtain better results than state-of-the-art CI testers.

BACKGROUND: Single-cell RNA sequencing (scRNA-seq) is an emerging technology that can assess the function of an individual cell and cell-to-cell variability at the single cell level in an unbiased manner. Dimensionality reduction is an essential first step in downstream analysis of the scRNA-seq data. However, the scRNA-seq data are challenging for traditional methods due to their high dimensional measurements as well as an abundance of dropout events (that is, zero expression measurements). RESULTS: To overcome these difficulties, we propose DR-A (Dimensionality Reduction with Adversarial variational autoencoder), a data-driven approach to fulfill the task of dimensionality reduction. DR-A leverages a novel adversarial variational autoencoder-based framework, a variant of generative adversarial networks. DR-A is well-suited for unsupervised learning tasks for the scRNA-seq data, where labels for cell types are costly and often impossible to acquire. Compared with existing methods, DR-A is able to provide a more accurate low dimensional representation of the scRNA-seq data. We illustrate this by utilizing DR-A for clustering of scRNA-seq data. CONCLUSIONS: Our results indicate that DR-A significantly enhances clustering performance over state-of-the-art methods.

Generative Adversarial networks (GANs) have obtained remarkable success in many unsupervised learning tasks and unarguably, clustering is an important unsupervised learning problem. While one can potentially exploit the latent-space back-projection in GANs to cluster, we demonstrate that the cluster structure is not retained in the GAN latent space. In this paper, we propose ClusterGAN as a new mechanism for clustering using GANs. By sampling latent variables from a mixture of one-hot encoded variables and continuous latent variables, coupled with an inverse network (which projects the data to the latent space) trained jointly with a clustering specific loss, we are able to achieve clustering in the latent space. Our results show a remarkable phenomenon that GANs can preserve latent space interpolation across categories, even though the discriminator is never exposed to such vectors. We compare our results with various clustering baselines and demonstrate superior performance on both synthetic and real datasets.

The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput and confirmation latency. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing Nakamoto's blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

Designing channel codes under low latency constraints is one of the most demanding requirements in 5G standards. However, sharp characterizations of the performances of traditional codes are only available in the large block lengths limit. Code designs are guided by those asymptotic analyses and require large block lengths and long latency to achieve the desired error rate. Furthermore, when the codes designed for one channel (e.g. Additive White Gaussian Noise (AWGN) channel) are used for another (e.g. non-AWGN channels), heuristics are necessary to achieve any non trivial performance - thereby severely lacking in robustness as well as adaptivity. Obtained by jointly designing recurrent neural network (RNN) based encoder and decoder, we propose an end-to-end learned neural code which outperforms canonical convolutional code under block settings. With this gained experience of designing a novel neural block code, we propose a new class of codes under low latency constraint - Low-latency Efficient Adaptive Robust Neural (LEARN) codes, which outperform the state-of-the-art low latency codes as well as exhibit robustness and adaptivity properties. LEARN codes show the potential of designing new versatile and universal codes for future communications via tools of modern deep learning coupled with communication engineering insights.

Mixture-of-Experts (MoE) is a widely popular model for ensemble learning and is a basic building block of highly successful modern neural networks as well as a component in Gated Recurrent Units (GRU) and Attention networks. However, present algorithms for learning MoE, including the EM algorithm and gradient descent, are known to get stuck in local optima. From a theoretical viewpoint, finding an efficient and provably consistent algorithm to learn the parameters remains a long standing open problem for more than two decades. In this paper, we introduce the first algorithm that learns the true parameters of a MoE model for a wide class of non-linearities with global consistency guarantees. While existing algorithms jointly or iteratively estimate the expert parameters and the gating parameters in the MoE, we propose a novel algorithm that breaks the deadlock and can directly estimate the expert parameters by sensing its echo in a carefully designed cross-moment tensor between the inputs and the output. Once the experts are known, the recovery of gating parameters still requires an EM algorithm; however, we show that the EM algorithm for this simplified problem, unlike the joint EM algorithm, converges to the true parameters. We empirically validate our algorithm on both the synthetic and real data sets in a variety of settings, and show superior performance to standard baselines.

Designing codes that combat the noise in a communication medium has remained a significant area of research in information theory as well as wireless communications. Asymptotically optimal channel codes have been developed by mathematicians for communicating under canonical models after over 60 years of research. On the other hand, in many non-canonical channel settings, optimal codes do not exist and the codes designed for canonical models are adapted via heuristics to these channels and are thus not guaranteed to be optimal. In this work, we make significant progress on this problem by designing a fully end-to-end jointly trained neural encoder and decoder, namely, Turbo Autoencoder (TurboAE), with the following contributions: (a) under moderate block lengths, TurboAE approaches state-of-the-art performance under canonical channels; (b) moreover, TurboAE outperforms the state-of-the-art codes under non-canonical settings in terms of reliability. TurboAE shows that the development of channel coding design can be automated via deep learning, with near-optimal performance.

We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.

The design of codes for communicating reliably over a statistically well defined channel is an important endeavor involving deep mathematical research and wide- ranging practical applications. In this work, we present the first family of codes obtained via deep learning, which significantly beats state-of-the-art codes designed over several decades of research. The communication channel under consideration is the Gaussian noise channel with feedback, whose study was initiated by Shannon; feedback is known theoretically to improve reliability of communication, but no practical codes that do so have ever been successfully constructed. We break this logjam by integrating information theoretic insights harmoniously with recurrent-neural-network based encoders and decoders to create novel codes that outperform known codes by 3 orders of magnitude in reliability. We also demonstrate several desirable properties in the codes: (a) generalization to larger block lengths; (b) composability with known codes; (c) adaptation to practical constraints. This result also presents broader ramifications to coding theory: even when the channel has a clear mathematical model, deep learning methodologies, when combined with channel specific information-theoretic insights, can potentially beat state-of-the-art codes, constructed over decades of mathematical research.

Information theoretic quantities play an important role in various settings in machine learning, including causality testing, structure inference in graphical models, time-series problems, feature selection as well as in providing privacy guarantees. A key quantity of interest is the mutual information and generalizations thereof, including conditional mutual information, multivariate mutual information, total correlation and directed information. While the aforementioned information quantities are well defined in arbitrary probability spaces, existing estimators employ a $\Sigma H$ method, which can only work in purely discrete space or purely continuous case since entropy (or differential entropy) is well defined only in that regime. In this paper, we define a general graph divergence measure ($\mathbb{GDM}$), generalizing the aforementioned information measures and we construct a novel estimator via a coupling trick that directly estimates these multivariate information measures using the Radon-Nikodym derivative. These estimators are proven to be consistent in a general setting which includes several cases where the existing estimators fail, thus providing the only known estimators for the following settings: (1) the data has some discrete and some continuous valued components (2) some (or all) of the components themselves are discrete-continuous \textit{mixtures} (3) the data is real-valued but does not have a joint density on the entire space, rather is supported on a low-dimensional manifold. We show that our proposed estimators significantly outperform known estimators on synthetic and real datasets.

Motivation: Single cell RNA-seq (scRNA-seq) data contains a wealth of information which has to be inferred computationally from the observed sequencing reads. As the ability to sequence more cells improves rapidly, existing computational tools suffer from three problems. (i) The decreased reads-per-cell implies a highly sparse sample of the true cellular transcriptome. (ii) Many tools simply cannot handle the size of the resulting datasets. (iii) Prior biological knowledge such as bulk RNA-seq information of certain cell types or qualitative marker information is not taken into account. Here we present UNCURL, a preprocessing framework based on non-negative matrix factorization for scRNA-seq data, that is able to handle varying sampling distributions, scales to very large cell numbers and can incorporate prior knowledge. Results: We find that preprocessing using UNCURL consistently improves performance of commonly used scRNA-seq tools for clustering, visualization and lineage estimation, both in the absence and presence of prior knowledge. Finally we demonstrate that UNCURL is extremely scalable and parallelizable, and runs faster than other methods on a scRNA-seq dataset containing 1.3 million cells. Availability and implementation: Source code is available at https://github.com/yjzhang/uncurl_python. Supplementary information: Supplementary data are available at Bioinformatics online.

Nanopore sequencing is an emerging new technology for sequencing Deoxyribonucleic acid (DNA), which can read long fragments of DNA (~50000 bases), in contrast to most current short-read sequencing technologies which can only read hundreds of bases. While nanopore sequencers can acquire long reads, the high error rates (20%-30%) pose a technical challenge. In a nanopore sequencer, a DNA is migrated through a nanopore, and current variations are measured. The DNA sequence is inferred from this observed current pattern using an algorithm called a base-caller. In this paper, we propose a mathematical model for the “channel” from the input DNA sequence to the observed current, and calculate bounds on the information extraction capacity of the nanopore sequencer. This model incorporates impairments, such as (non-linear) intersymbol interference, deletions, and random response. These information bounds have two-fold application: 1) The decoding rate with a uniform input distribution can be used to calculate the average size of the plausible list of DNA sequences given an observed current trace. This bound can be used to benchmark existing base-calling algorithms, as well as serving a performance objective to design better nanopores. 2) When the nanopore sequencer is used as a reader in a DNA storage system, the storage capacity is quantified by our bounds.

Nanopore sequencing is an emerging new technology for sequencing DNA, which can read long fragments of DNA (~50,000 bases) unlike most current sequencers which can only read hundreds of bases. While nanopore sequencers can acquire long reads, the high error rates (≈ 30%) pose a technical challenge. In a nanopore sequencer, a DNA is migrated through a nanopore and current variations are measured. The DNA sequence is inferred from this observed current pattern using an algorithm called a base-caller. In this paper, we propose a mathematical model for the “channel” from the input DNA sequence to the observed current, and calculate bounds on the information extraction capacity of the nanopore sequencer. This model incorporates impairments like inter-symbol interference, deletions, as well as random response. The practical application of such information bounds is two-fold: (1) benchmarking present base-calling algorithms, and (2) offering an optimization objective for designing better nanopore sequencers.

Estimation of mutual information from observed samples is a basic primitive in machine learning, useful in several learning tasks including correlation mining, information bottleneck, Chow-Liu tree, and conditional independence testing in (causal) graphical models. While mutual information is a quantity well-defined for general probability spaces, estimators have been developed only in the special case of discrete or continuous pairs of random variables. Most of these estimators operate using the 3H -principle, i.e., by calculating the three (differential) entropies of X, Y and the pair (X,Y). However, in general mixture spaces, such individual entropies are not well defined, even though mutual information is. In this paper, we develop a novel estimator for estimating mutual information in discrete-continuous mixtures. We prove the consistency of this estimator theoretically as well as demonstrate its excellent empirical performance. This problem is relevant in a wide-array of applications, where some variables are discrete, some continuous, and others are a mixture between continuous and discrete components.

Discovering a correlation from one variable to another variable is of fundamental scientific and practical interest. While existing correlation measures are suitable for discovering average correlation, they fail to discover hidden or potential correlations. To bridge this gap, (i) we postulate a set of natural axioms that we expect a measure of potential correlation to satisfy; (ii) we show that the rate of information bottleneck, i.e., the hypercontractivity coefficient, satisfies all the proposed axioms; (iii) we provide a novel estimator to estimate the hypercontractivity coefficient from samples; and (iv) we provide numerical experiments demonstrating that this proposed estimator discovers potential correlations among various indicators of WHO datasets, is robust in discovering gene interactions from gene expression time series data, and is statistically more powerful than the estimators for other correlation measures in binary hypothesis testing of canonical examples of potential correlations.

Variant calling, in particular, calling SNPs (Single Nucleotide Polymorphisms) is a fundamental task in genomics. While existing packages offer excellent performance on calling SNPs which have uniquely mapped reads, they suffer in loci where the reads are multiply mapped, and are unable to make any reliable calls. Variants in multiply mapped loci can arise, for example in long segmental duplications, and can play important role in evolution and disease. In this paper, we develop a new SNP caller named abSNP, which offers three innovations. (a) abSNP calls SNPs from RNA-Seq data. Since RNA-Seq data is primarily sampled from gene regions, this method is inexpensive. (b) abSNP is able to successfully make calls on repetitive gene regions by exploiting the quality scores of multiply mapped reads carefully in order to make variant calls. (c) abSNP exploits a specific feature of RNA-Seq data, namely the varying abundance of different genes, in order to identify which repetitive copy a particular read is sampled from. We demonstrate that the proposed method offers significant performance gains on repetitive regions in simulated data. In particular, the algorithm is able to achieve near-perfect sensitivity on high-coverage SNPs, even when multiply mapped.

We consider the setting where a collection of time series, modeled as random processes, evolve in a causal manner, and one is interested in learning the graph governing the relationships of these processes. A special case of wide interest and applicability is the setting where the noise is Gaussian and relationships are Markov and linear. We study this setting with two additional features: firstly, each random process has a hidden (latent) state, which we use to model the internal memory possessed by the variables (similar to hidden Markov models). Secondly, each variable can depend on its latent memory state through a random lag (rather than a fixed lag), thus modeling memory recall with differing lags at distinct times. Under this setting, we develop an estimator and prove that under a genericity assumption, the parameters of the model can be learned consistently. We also propose a practical adaption of this estimator, which demonstrates significant performance gains in both synthetic and real-world datasets.

We consider axiomatically the problem of estimating the strength of a conditional dependence relationship P_Y|X from a random variables X to a random variable Y. This has applications in determining the strength of a known causal relationship, where the strength depends only on the conditional distribution of the effect given the cause (and not on the driving distribution of the cause). Shannon capacity, appropriately regularized, emerges as a natural measure under these axioms. We examine the problem of calculating Shannon capacity from the observed samples and propose a novel fixed-k nearest neighbor estimator, and demonstrate its consistency. Finally, we demonstrate an application to single-cell flow-cytometry, where the proposed estimators significantly reduce sample complexity.

We consider the single-unicast communication problem in a network with a delay constraint. For this setting, it has recently been shown that network coding offers an advantage over routing. We show that the existing upper bound in the literature on the capacity offered by network coding can be a factor of Θ(D) larger than the true capacity where D is the delay bound. In this work, we tighten this gap significantly to 8 log(D + 1) by proving a new upper bound. The key insight is a connection to a new traffic model that we call triangle-cast (or degraded multiple-unicast), for which we obtain a logarithmic flow-cut gap by suitably adapting the techniques from the approximation algorithms literature.

Given low order moment information over the random variables X = (X1, X2, …, Xp) and Y, what distribution minimizes the Hirschfeld-Gebelein-Rényi (HGR) maximal correlation coefficient between X and Y, while remains faithful to the given moments? The answer to this question is important especially in order to fit models over (X, Y) with minimum dependence among the random variables X and Y. In this paper, we investigate this question first in the continuous setting by showing that the jointly Gaussian distribution achieves the minimum HGR correlation coefficient among distributions with the given first and second order moments. Then, we pose a similar question in the discrete scenario by fixing the pairwise marginals of the random variables X and Y. Subsequently, we derive a lower bound for the HGR correlation coefficient over the class of distributions with fixed pairwise marginals. Then we show that this lower bound is tight if there exists a distribution with certain additive structure satisfying the given pairwise marginals. Moreover, the distribution with the additive structure achieves the minimum HGR correlation coefficient. Finally, we conclude by showing that the event of obtaining pairwise marginals containing an additive structured distribution has a positive Lebesgue measure over the probability simplex.

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334--347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185--204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285--301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303--6328] and we anticipate others in the future.

We propose a new coding scheme for interference alignment in a single hop fast fading wireless network with general message demands. For the X-Channel, the Degrees of Freedom (DoF) region achievable by the scheme is shown to touch a known outer-bound at several points. For multiple-multicast demands we show that the achievable region is at least half of the cut-set bound region. The key innovation in our scheme is the reduction of the vector space alignment problem to a combinatorial arrangement problem. Finally, we use the scheme to give a poly-logarithmic bound for the flow-cut gap in fast fading Gaussian wireless networks with multiple multicasts.

We study interference channels (IFCs) where the interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other using full-duplex radios. The interaction can come in two ways. First is through in-band interaction where sources and destinations can transmit and listen in the same channel simultaneously, enabling interaction. Second is through out-of-band interaction where destinations talk back to the sources on an out-of-band channel, which is possible from white-space channels. The flexibility afforded by the interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties,” i.e., insensitivity to the rationality or irrationality of channel parameters, small block lengths, and finite SNR operations. We show that, for several classes of IFCs, the interactive IA scheme can achieve the optimal degrees of freedom. In particular, we show a simple scheme (having a finite block length for channels having no diversity) for three-user and four-user IFCs with full-duplex radios to achieve the optimal degrees of freedom even after accounting for the cost of interaction. On the technical side, we show using a Gröbner basis argument that, in a general network potentially utilizing cooperation and feedback, the optimal degrees of freedom under linear schemes of a fixed block length is the same for channel coefficients with a probability of 1. Furthermore, a numerical method to estimate this value is also presented. These tools have potentially wider utility in studying other wireless networks as well.

The problem of designing near optimal strategies for multiple unicast traffic in wireline networks is wide open; however, channel symmetry or traffic symmetry can be leveraged to show that routing can achieve with a polylogarithmic approximation factor of the edge-cut bound. For the same problem, the edge-cut bound is known to only upper bound rates of routing flows and unlike the information theoretic cut-set bound, it does not upper bound (capacity-achieving) information rates with general strategies. In this paper, we demonstrate that under channel or traffic symmetry, the edge-cut bound upper-bounds general information rates, thus providing a capacity approximation result. The key technique is a combinatorial result relating edge-cut bounds to generalized network sharing bounds. Finally, we generalize the results to wireless networks via an intermediary class of combinatorial graphs known as polymatroidal networks-our main result is that a natural architecture separating the physical and networking layers is near optimal when the traffic is symmetric among source-destination pairs, even when the channel is asymmetric (due to asymmetric power constraints, or prior frequency allocation like frequency division duplexing). This result is complementary to an earlier work of two of the authors proving a similar result under channel symmetry.

A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast traffic (multiple sources communicating independent messages to multiple destinations): the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper, we extend the wireline result to the wireless context. In particular, we show the following meta-theorem: if for a given channel and its reciprocal channel, the cut-set bound is (approximately) achievable, then for multiple-unicast in a bidirected network comprised of such channels, the cut-set bound is (approximately) achievable within a logarithmic factor of the number of sources. The achievable scheme can be viewed as an instantiation of a simple layering principle: local physical-layer schemes combined with global routing. We use the reciprocity of the wireless channel critically in this result. We prove this result formally as a capacity approximation result for a variety of channel models, including general Gaussian networks under fast fading, networks comprised only of broadcast and MAC channels, and networks comprised of broadcast erasure channels with feedback. The capacity approximations we prove tend to have both an additive gap (power loss) and a multiplicative gap (degrees of freedom loss). The key engineering insight is that layered architectures, common in the engineering-design of wireless networks, can have near-optimal performance if the locality over which physical-layer schemes should operate is carefully designed. Feedback is shown to play a critical role in enabling the separation between the physical and the network layers. The main technical contribution is the usage of polymatroidal network as a graphical model for analyzing the performance of complex wireless networks.

We study interference channels (IFC) where interaction among sources and destinations is enabled, e.g., both sources and destinations can talk to each other. The interaction can come in two ways: 1) for half-duplex radios, destinations can talk back to sources using either simultaneous out-of-band (white spaces) transmission or in-band half-duplex transmission; 2) for full-duplex radios, both sources and destinations can transmit and listen in the same channel simultaneously. The flexibility afforded by interaction among sources and destinations allows for the derivation of interference alignment (IA) strategies that have desirable “engineering properties”: insensitivity to the rationality or irrationality of channel parameters, small block lengths and finite SNR operations. We show that for several classes of interference channels the interactive interference alignment scheme can achieve the optimal degrees of freedom.

In the function computation problem, certain nodes of an undirected graph have access to independent data, while certain other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which the function computation is possible on a capacitated graph. We consider a general model of function computation, which we term as multi-session function multicasting. In this general model, there are K independent sessions sharing the communication infrastructure; in each session, a set of D destinations all want the same function of a group of S sources. This traffic model generalizes various well known traffic models like the classical model of function computation (K = 1, D = 1), multiple-unicasting (S = 1, D = 1) and multicasting (K = 1, S = 1). For this general model, we propose a simple achievable strategy in which the function is computed for each session using Steiner trees at a specific destination and then distributed to the other destinations also using Steiner trees. Thus, in our proposed strategy, Steiner trees play the dual role of computation trees and also that of multicasting trees. Our main result is that this achievable strategy is near optimal for multi-session function multicasting of a wide class of functions in undirected graphs. The key technical contribution involves relating algorithmic work on Steiner cuts in undirected graphs to the function computation problem.

In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are near optimal for a wide class of function computation requirements even at multiple terminals in undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [20] and Hassin [15] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [10]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far as the authors are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks.

It has been shown recently that a simple layering principle - local physical-layer schemes combined with global routing - can achieve approximately optimal performance in wireless networks. However, this result depends heavily on the assumption of reciprocity of wireless networks, which may be violated due to asymmetric power constraints, directional antennas or frequency-duplexing. In this paper, we show that the approximate optimality continues to hold even for wireless networks modeled as directed graphs as long as there is a symmetric demand constraint: every demand from source sito sink tiat rate Rihas a counterpart demand from source node tito sink node siat the same rate. This models several practical scenarios including voice calls, video calls, and interactive gaming. We prove this result in the context of several channel models for which good local schemes exist. The key technical contributions are an outer bound based on a Generalized Network Sharing bound for wireless networks and an achievable strategy based on a connection to polymatroidal networks.

We study a wireless broadcast network, where a single source reliably communicates independent messages to multiple destinations, with the potential aid of relays and cooperation between destinations. The wireless nature of the medium is captured by the broadcast nature of transmissions as well as the superposition of transmitted signals plus independent Gaussian noise at the received signal at any radio. We propose a scheme that can achieve rate tuples within a constant gap away from the cut-set bound, where the constant is independent of channel coefficients and power constraints. First, for a deterministic broadcast network, we propose a new coding scheme, constructed by adopting a “receiver-centric” viewpoint, that uses quantize-and-forward relaying as an inner code concatenated with an outer Marton code for the induced deterministic broadcast channel. This scheme is shown to achieve the cut-set bound evaluated with product form distributions. This result is then lifted to the Gaussian network by using a deterministic network called the discrete superposition network as a formal quantization interface. This two-stage construction circumvents the difficulty involved in working with a vector nonlinear non-Gaussian broadcast channel that arises if we construct a similar scheme directly for the Gaussian network.

A classical result in undirected wireline networks is the near optimality of routing (flow) for multiple-unicast: the min cut upper bound is within a logarithmic factor of the number of sources of the max flow. Wireless channels differ from wireline ones in two primary ways: the signal out of a transmitting node is broadcast and the signals at a receiving node superpose. In this paper we focus on “extending” the wireline result to the wireless context, by separately considering the broadcast and superposition constraints. Our main result is the approximate optimality of a simple layering principle: local physical-layer schemes combined with global routing. We show this in the context of both Gaussian networks and packet erasure networks. The key technical contribution is an approximation of min cut in a bidirected graph with submodular constraints on the edge capacities by max flow.

We study a wireless broadcast-cum-multicast network, where a single source reliably communicates independent messages to multiple destinations, with the aid of relays. In addition, we assume there are nodes that demand all the messages at the source. We propose a compress-and-forward scheme that can achieve rates within a constant gap away from the cut-set bound. The proposed scheme operates in two steps: the inner code induces a broadcast channel with sufficient mutual information between the source and the destinations, and the outer code is basically a Marton code for broadcast channels. The inner code is constructed by lifting a scheme designed for a corresponding discrete superposition network.

A classical result in undirected wireline networks is the approximate optimality of routing (flow) for multiple-unicast: the min-cut upper bound is within a logarithmic factor of the number of sources of the max flow. In this paper we focus on “extending” this result to the wireless context. Our main result is the approximate optimality of a simple layering principle: local physical-layer schemes combined with global routing. We show this in the context of wireless networks, in which links are either absent or undergo i.i.d. fast fading. We also show an approximation result on the degrees-of-freedom, when the channels are fixed, but are chosen from a continuous ensemble. The key technical contribution is an approximation of min-cut in a bidirected graph with submodular constraints on the edge capacities by max flow.