MOTIVATION: Identification of splice sites is critical to gene annotation and to determine which sequences control circRNA biogenesis. Full-length RNA transcripts could in principle complete annotations of introns and exons in genomes without external ontologies, i.e., ab initio. However, whether it is possible to reconstruct genomic positions where splicing occurs from full-length transcripts, even if sampled in the absence of noise, depends on the genome sequence composition. If it is not, there exist provable limits on the use of RNA-Seq to define splice locations (linear or circular) in the genome. RESULTS: We provide a formal definition of splice site ambiguity due to the genomic sequence by introducing equivalent junction, which is the set of local genomic positions resulting in the same RNA sequence when joined through RNA splicing. We show that equivalent junctions are prevalent in diverse eukaryotic genomes and occur in 88.64% and 78.64% of annotated human splice sites in linear and circRNA junctions, respectively. The observed fractions of equivalent junctions and the frequency of many individual motifs are statistically significant when compared against the null distribution computed via simulation or closed-form. The frequency of equivalent junctions establishes a fundamental limit on the possibility of ab initio reconstruction of RNA transcripts without appealing to the ontology of "GT-AG" boundaries defining introns. Said differently, completely ab initio is impossible in the vast majority of splice sites in annotated circRNAs and linear transcripts. AVAILABILITY AND IMPLEMENTATION: Two python scripts generating an equivalent junction sequence per junction are available at: https://github.com/salzmanlab/Equivalent-Junctions. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Next-generation sequencing is a cutting edge technology, but to quantify a dynamic range of abundances for different RNA or DNA species requires increasing sampling depth to levels that can be prohibitively expensive due to physical limits on molecular throughput of sequencers. To overcome this problem, we introduce a new general sampling theory which uses biophysical principles to functionally encode the abundance of a species before sampling, SeQUential depletIon and enriCHment (SQUICH). In theory and simulation, SQUICH enables sampling at a logarithmic rate to achieve the same precision as attained with conventional sequencing. A simple proof of principle experimental implementation of SQUICH in a controlled complex system of ~262,000 oligonucleotides already reduces sequencing depth by a factor of 10. SQUICH lays the groundwork for a general solution to a fundamental problem in molecular sampling and enables a new generation of efficient, precise molecular measurement at logarithmic or better sampling depth.

We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in the setting of bounded error entanglement-assisted communication, is based on sophisticated information theoretic arguments. Our results are derived from first principles, using a simple linear algebraic technique. A direct consequence is a tight lower bound for the Inner Product function that has found applications to privacy amplification in quantum key distribution protocols.

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.