Search

Malicious attacks such as jamming can cause significant disruption or complete denial of service (DoS) to wireless communication protocols. Moreover, jamming devices are getting smarter, making them difficult to detect. Forward error correction, which adds redundancy to data, is commonly deployed to protect communications against the deleterious effects of channel noise. Soft-information error correction decoders obtain reliability information from the receiver to inform their decoding, but in the presence of a jammer such information is misleading and results in degraded error correction performance. As decoders assume noise occurs independently to each bit, a bursty jammer will lead to greater degradation in performance than a non-bursty one. Here we establish, however, that such temporal dependencies can aid inferences on which bits have been subjected to jamming, thus enabling counter-measures. In particular, we introduce a pre-decoding processing step that updates log-likelihood ratio (LLR) reliability information to reflect inferences in the presence of a jammer, enabling improved decoding performance for any soft detection decoder. The proposed method requires no alteration to the decoding algorithm. Simulation results show that the method correctly infers a significant proportion of jamming in any received frame. Results with one particular decoding algorithm, the recently introduced ORBGRAND, show that the proposed method reduces the block-error rate (BLER) by an order of magnitude for a selection of codes, and prevents complete DoS at the receiver., Accepted for GLOBECOM 2022 Workshops. Contains 7 pages and 7 figures

Current analysis of forensic DNA stains relies on the probabilistic interpretation of bulk-processed samples that represent mixed profiles consisting of an unknown number of potentially partial representations of each contributor. Single-cell methods, in contrast, offer a solution to the forensic DNA mixture problem by incorporating a step that separates cells before extraction. A forensically relevant single-cell pipeline relies on efficient direct-to-PCR extractions that are compatible with standard down- stream forensic reagents. Here we demonstrate the feasibility of implementing single-cell pipelines into the forensic process by exploring four metrics of electropherogram (EPG) signal quality—i.e., allele detection rates, peak heights, peak height ratios, and peak height balance across low- to high-molecular-weight short tandem repeat (STR) markers—obtained with four direct-to-PCR extraction treatments and a common post-PCR laboratory procedure. Each treatment was used to extract DNA from 102 single buccal cells, whereupon the amplification reagents were immediately added to the tube and the DNA was amplified/injected using post-PCR conditions known to elicit a limit of detection (LoD) of one DNA molecule. The results show that most cells, regardless of extraction treatment, rendered EPGs with at least a 50% true positive allele detection rate and that allele drop-out was not cell independent. Statistical tests demonstrated that extraction treatments significantly impacted all metrics of EPG quality, where the Arcturus® PicoPure™ extraction method resulted in the lowest median allele drop-out rate, highest median average peak height, highest median average peak height ratio, and least negative median values of EPG sloping for GlobalFiler™ STR loci amplified at half volume. We, therefore, conclude the feasibility of implementing single-cell pipelines for casework purposes and demonstrate that inferential systems assuming cell independence will not be appropriate in the probabilistic interpretation of a collection of single-cell EPGs.

We consider the problem of secure and reliable communication over a noisy multipath network. Previous work considering a noiseless version of our problem proposed a hybrid universal network coding cryptosystem (HUNCC). By combining an information-theoretically secure encoder together with partial encryption, HUNCC is able to obtain security guarantees, even in the presence of an all-observing eavesdropper. In this paper, we propose a version of HUNCC for noisy channels (N-HUNCC). This modification requires four main novelties. First, we present a network coding construction which is jointly, individually secure and error-correcting. Second, we introduce a new security definition which is a computational analogue of individual security, which we call individual indistinguishability under chosen ciphertext attack (individual IND-CCA1), and show that NHUNCC satisfies it. Third, we present a noise based decoder for N-HUNCC, which permits the decoding of the encoded-thenencrypted data. Finally, we discuss how to select parameters for N-HUNCC and its error-correcting capabilities.

Guessing Random Additive Noise Decoding (GRAND) is a family of universal decoding algorithms suitable for decoding any moderate redundancy code of any length. We establish that, through the use of list decoding, soft-input variants of GRAND can replace the Chase algorithm as the component decoder in the turbo decoding of product codes. In addition to being able to decode arbitrary product codes, rather than just those with dedicated hard-input component code decoders, results show that ORBGRAND achieves a coding gain of up to 0.7dB over the Chase algorithm with same list size.

In the classic wiretap model, Alice wishes to reliably communicate to Bob without being overheard by Eve who is eavesdropping over a degraded channel. Systems for achieving that physical layer security often rely on an error correction code whose rate is below the Shannon capacity of Alice and Bob's channel, so Bob can reliably decode, but above Alice and Eve's, so Eve cannot reliably decode. For the finite block length regime, several metrics have been proposed to characterise information leakage. Here we assess a new metric, the success exponent, and demonstrate it can be operationalized through the use of Guessing Random Additive Noise Decoding (GRAND) to compromise the physical-layer security of any moderate length code. Success exponents are the natural beyond-capacity analogue of error exponents that characterise the probability that a maximum likelihood decoding is correct when the code-rate is above Shannon capacity, which is exponentially decaying in the code-length. Success exponents can be used to approximately evaluate the frequency with which Eve's decoding is correct in beyond-capacity channel conditions. Through the use of GRAND, we demonstrate that Eve can constrain her decoding procedure so that when she does identify a decoding, it is correct with high likelihood, significantly compromising Alice and Bob's communication by truthfully revealing a proportion of it. We provide general mathematical expressions for the determination of success exponents as well as for the evaluation of Eve's query number threshold, using the binary symmetric channel as a worked example. As GRAND algorithms are code-book agnostic and can decode any code structure, we provide empirical results for Random Linear Codes as exemplars. Simulation results demonstrate the practical possibility of compromising physical layer security.

Interpreting forensic DNA signal is arduous since the total intensity is a cacophony of signal from noise, artifact, and allele from an unknown number of contributors (NOC). An alternate to traditional bulk- processing pipelines is a single-cell one, where the sample is collected, and each cell is sequestered resulting in n single-source, single-cell EPGs (scEPG) that must be interpreted using applicable strategies. As with all forensic DNA interpretation strategies, high quality electropherograms are required; thus, to enhance the credibility of single-cell forensics, it is necessary to produce an efficient direct-to- PCR treatment that is compatible with prevailing downstream labo-ratory processes.We incorporated the semi-automated micro-fluidic DEPArray™ technology into the single-cell laboratory and optimized its implementation by testing the effects of four laboratory treatments on single-cell profiles. We focused on testing effects of phosphate buffer saline (PBS) since it is an important reagent that mitigates cell rup-ture but is also a PCR inhibitor. Specifically, we explored the effect of decreasing PBS concentrations on five electropherogram-quality metrics from 241 leukocytes: profile drop- out, allele drop-out, allele peak heights, peak height ratios, and scEPG sloping. In an effort to improve reagent use, we also assessed two concentrations of proteinase K. The results indicate that decreasing PBS concentrations to 0.5X or 0.25X improves scEPG quality, while modest modifications to proteinase K concentrations did not significantly impact it. We, therefore, conclude that a lower than recommended pro-teinase K concentration coupled with a lower than recommended PBS concentration results in enhanced scEPGs within the semi-automated single-cell pipeline.

To optimize immunity to pathogens, B lymphocytes generate plasma cells with functionally diverse antibody isotypes. By lineage tracing single cells within differentiating B cell clones, we identified the heritability of discrete fate controlling mechanisms to inform a general mathematical model of B cell fate regulation. Founder cells highly influenced clonal plasma-cell fate, whereas class switch recombination (CSR) was variegated within clones. In turn, these CSR patterns resulted from independent all-or-none expression of both activation-induced cytidine deaminase (AID) and IgH germline transcription (GLT), with the latter being randomly re-expressed after each cell division. A stochastic model premised on these molecular transition rules accurately predicted antibody switching outcomes under varied conditions in vitro and during an immune response in vivo. Thus, the generation of functionally diverse antibody types follows rules of autonomous cellular programming that can be adapted and modeled for the rational control of antibody classes for potential therapeutic benefit.

International audience; High-throughput single-cell methods have uncovered substantial heterogeneity in the pool of hematopoietic stem and progenitor cells (HSPCs), but how much instruction is inherited by offspring from their heterogeneous ancestors remains unanswered. Using a method that enables simultaneous determination of common ancestor, division number, and differentiation status of a large collection of single cells, our data revealed that murine cells that derived from a common ancestor had significant similarities in their division progression and differentiation outcomes. Although each family diversifies, the overall collection of cell types observed is composed of homogeneous families. Heterogeneity between families could be explained, in part, by differences in ancestral expression of cell surface markers. Our analyses demonstrate that fate decisions of cells are largely inherited from ancestor cells, indicating the importance of common ancestor effects. These results may have ramifications for bone marrow transplantation and leukemia, where substantial heterogeneity in HSPC behavior is observed.

Several significant models have been developed that enable the study of diffusion of signals across biological, social and engineered networks. Within these established frameworks, the inverse problem of identifying the source of the propagated signal is challenging, owing to the numerous alternative possibilities for signal progression through the network. In real world networks, the challenge of determining sources is compounded as the true propagation dynamics are typically unknown, and when they have been directly measured, they rarely conform to the assumptions of any of the well-studied models. In this paper we introduce a method called Network Infusion (NI) that has been designed to circumvent these issues, making source inference practical for large, complex real world networks. The key idea is that to infer the source node in the network, full characterization of diffusion dynamics, in many cases, may not be necessary. This objective is achieved by creating a diffusion kernel that well-approximates standard diffusion models, but lends itself to inversion, by design, via likelihood maximization or error minimization. We apply NI for both single-source and multi-source diffusion, for both single-snapshot and multi-snapshot observations, and for both homogeneous and heterogeneous diffusion setups. We prove the mean-field optimality of NI for different scenarios, and demonstrate its effectiveness over several synthetic networks. Moreover, we apply NI to a real-data application, identifying news sources in the Digg social network, and demonstrate the effectiveness of NI compared to existing methods. Finally, we propose an integrative source inference framework that combines NI with a distance centrality-based method, which leads to a robust performance in cases where the underlying dynamics are unknown., Comment: 21 pages, 13 figures

CRC codes have long since been adopted in a vast range of applications. The established notion that they are suitable primarily for error detection can be set aside through use of the recently proposed Guessing Random Additive Noise Decoding (GRAND). Hard-detection (GRAND-SOS) and soft-detection (ORBGRAND) variants can decode any short, high-rate block code, making them suitable for error correction of CRC-coded data. When decoded with GRAND, short CRC codes have error correction capability that is at least as good as popular codes such as BCH codes, but with no restriction on either code length or rate. The state-of-the-art CA-Polar codes are concatenated CRC and Polar codes. For error correction, we find that the CRC is a better short code than either Polar or CA-Polar codes. Moreover, the standard CA-SCL decoder only uses the CRC for error detection and therefore suffers severe performance degradation in short, high rate settings when compared with the performance GRAND provides, which uses all of the CA-Polar bits for error correction. Using GRAND, existing systems can be upgraded from error detection to low-latency error correction without re-engineering the encoder, and additional applications of CRCs can be found in IoT, Ultra-Reliable Low Latency Communication (URLLC), and beyond. The universality of GRAND, its ready parallelized implementation in hardware, and the good performance of CRC as codes make their combination a viable solution for low-latency applications., This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Clonal expansion is a core aspect of T cell immunity. However, little is known with respect to the relationship between replicative history and the formation of distinct CD8+ memory T cell subgroups. To address this issue, we developed a genetic-tracing approach, termed the DivisionRecorder, that reports the extent of past proliferation of cell pools in vivo. Using this system to genetically ‘record’ the replicative history of different CD8+ T cell populations throughout a pathogen-specific immune response, we demonstrate that the central memory T cell (TCM) pool is marked by a higher number of prior divisions than the effector memory T cell pool, due to the combination of strong proliferative activity during the acute immune response and selective proliferative activity after pathogen clearance. Furthermore, by combining DivisionRecorder analysis with single cell transcriptomics and functional experiments, we show that replicative history identifies distinct cell pools within the TCM compartment. Specifically, we demonstrate that lowly divided TCM display enriched expression of stem-cell-associated genes, and that such lowly divided cells are superior in eliciting a proliferative recall response. The latter data provide the first evidence that a stem cell like memory T cell pool that reconstitutes the CD8+ T cell effector pool upon reinfection is marked by prior quiescence.

If queue-states are unknown to a dispatcher, a replication strategy has been proposed where job copies are sent randomly to servers. When the service of any copy is completed, redundant copies are removed. For jobs that can be algebraically manipulated and have linear servers, to get the response-time performance of sending d copies of n jobs via the replication strategy, with Maximum Distance Separable (MDS) codes we show that n + d jobs suffice. That is, while replication is multiplicative, MDS is linear.

During an adaptive immune response, a population of naive lymphocytes becomes heterogeneous, containing a population of effector cells that clear the pathogen and then die during the contraction phase and a population of memory cells that are of a longer lineage. For CD8+ T cells, many theories have been proposed for the dynamics of this differentiation.

We present the first fully-integrated universal Max- imum Likelihood decoder in 40 nm CMOS using the Guessing Random Additive Noise Decoding (GRAND) algorithm for low- power applications. The 0.83 mm2 multi-code multi-rate universal decoder can efficiently decode any code of length up to 128 bits with 1 μs latency at 68 MHz. Dynamic clock gating leveraging noise statistics reduces the average power dissipation to 3.75 mW at 1.1 V or 30.6 pJ/decoded bit with a throughput of 122.6 Mb/s. Universal decoding reduces hardware footprint, and the design allows seamless swapping between codebooks with no downtime, enabling use by multiple applications without switch-over.

Two main problems arise in the Multiple Access Channel (MAC): interference from different users, and additive noise channel noise. Maximum A-Posteriori (MAP) joint decoding or successive interference cancellation are known to be capacity-achieving for the MAC when paired with appropriate codes. We extend the recently proposed Soft Guessing Random Additive Noise Decoder (SGRAND) to guess, using soft information, the effect of noise on the sum of users' transmitted codewords. Next, we manage interference by applying ZigZag decoding over the resulting putative noiseless MAC to obtain candidate codewords. Guessing continues until the candidate codewords thus obtained pertain to the corresponding users' codebooks. This MAC SGRAND decoder is a MAP decoder that requires no coordination between users, who can use arbitrary moderate redundancy short length codes of different types and rates.

Forensic DNA signal is notoriously challenging to assess, requiring computational tools to support its interpretation. Over-expressions of stutter, allele drop-out, allele drop-in, degradation, differential degradation, and the like, make forensic DNA profiles too complicated to evaluate by manual methods. In response, computational tools that make point estimates on the Number of Contributors (NOC) to a sample have been developed, as have Bayesian methods that evaluate an A Posteriori Probability (APP) distribution on the NOC. In cases where an overly narrow NOC range is assumed, the downstream strength of evidence may be incomplete insofar as the evidence is evaluated with an inadequate set of propositions. In the current paper, we extend previous work on NOCIt, a Bayesian method that determines an APP on the NOC given an electropherogram, by reporting on an implementation where the user can add assumed contributors. NOCIt is a continuous system that incorporates models of peak height (including degradation and differential degradation), forward and reverse stutter, noise, and allelic drop-out, while being cognizant of allele frequencies in a reference population. When conditioned on a known contributor, we found that the mode of the APP distribution can shift to one greater when compared with the circumstance where no known contributor is assumed, and that occurred most often when the assumed contributor was the minor constituent to the mixture. In a development of a result of Slooten and Caliebe (FSI:G, 2018) that, under suitable assumptions, establishes the NOC can be treated as a nuisance variable in the computation of a likelihood ratio between the prosecution and defense hypotheses, we show that this computation must not only use coincident models, but also coincident contextual information. The results reported here, therefore, illustrate the power of modern probabilistic systems to assess full weights-of-evidence, and to provide information on reasonable NOC ranges across multiple contexts.

We introduce Noise Recycling, a method that enhances decoding performance of channels subject to correlated noise without joint decoding. The method can be used with any combination of codes, code-rates and decoding techniques. In the approach, a continuous realization of noise is estimated from a lead channel by subtracting its decoded output from its received signal. This estimate is then used to improve the accuracy of decoding of an orthogonal channel that is experiencing correlated noise. In this design, channels aid each other only through the provision of noise estimates post-decoding. In a Gauss-Markov model of correlated noise, we constructive establish that noise recycling employing a simple successive order enables higher rates than not recycling noise. Simulations illustrate noise recycling can be employed with any code and decoder, and that noise recycling shows Block Error Rate (BLER) benefits when applying the same predetermined order as used to enhance the rate region. Finally, for short codes we establish that an additional BLER improvement is possible through noise recycling with racing, where the lead channel is not pre-determined, but is chosen on the fly based on which decoder completes first., Comment: Appear in IEEE International Symposium on Information Theory, ISIT 2020, based on arXiv:2006.04897

© 2020 IEEE. Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-theart soft-information decoder specific to CA-Polar codes.

Modern applications are driving demand for ultra-reliable low-latency communications, rekindling interest in the performance of short, high-rate error correcting codes. To that end, here we introduce a soft-detection variant of Guessing Random Additive Noise Decoding (GRAND) called Ordered Reliability Bits GRAND that can decode any short, high-rate block-code. For a code of $n$ bits, it avails of no more than $\lceil\log_2(n)\rceil$ bits of code-book-independent quantized soft detection information per received bit to determine an accurate decoding while retaining the original algorithm's suitability for a highly parallelized implementation in hardware. ORBGRAND is shown to provide similar block error performance for codes of distinct classes (BCH, CA-Polar and RLC) with low complexity, while providing better block error rate performance than CA-SCL, a state of the art soft detection CA-Polar decoder.

The question of testing for equality in distribution between two linear models, each consisting of sums of distinct discrete independent random variables with unequal numbers of observations, has emerged from the biological research. In this case, the computation of classical $\chi^2$ statistics, which would not include all observations, results in loss of power, especially when sample sizes are small. Here, as an alternative that uses all data, the nonparametric maximum likelihood estimator for the distribution of sum of discrete and independent random variables, which we call the convolution statistic, is proposed and its limiting normal covariance matrix determined. To challenge null hypotheses about the distribution of this sum, the generalized Wald's method is applied to define a testing statistic whose distribution is asymptotic to a $\chi^2$ with as many degrees of freedom as the rank of such covariance matrix. Rank analysis also reveals a connection with the roots of the probability generating functions associated to the addend variables of the linear models. A simulation study is performed to compare the convolution test with Pearson's $\chi^2$, and to provide usage guidelines.

To facilitate applications in IoT, 5G, and beyond, there is an engineering need to enable high-rate, low-latency communications. Errors in physical channels typically arrive in clumps, but most decoders are designed assuming that channels are memoryless. As a result, communication networks rely on interleaving over tens of thousands of bits so that channel conditions match decoder assumptions. Even for short high rate codes, awaiting sufficient data to interleave at the sender and de-interleave at the receiver is a significant source of unwanted latency. Using existing decoders with non-interleaved channels causes a degradation in block error rate performance owing to mismatch between the decoder's channel model and true channel behaviour. Through further development of the recently proposed Guessing Random Additive Noise Decoding (GRAND) algorithm, which we call GRAND-MO for GRAND Markov Order, here we establish that by abandoning interleaving and embracing bursty noise, low-latency, short-code, high-rate communication is possible with block error rates that outperform their interleaved counterparts by a substantial margin. Moreover, while most decoders are twinned to a specific code-book structure, GRAND-MO can decode any code. Using this property, we establish that certain well-known structured codes are ill-suited for use in bursty channels, but Random Linear Codes (RLCs) are robust to correlated noise. This work suggests that the use of RLCs with GRAND-MO is a good candidate for applications requiring high throughput with low latency., Comment: 6 pages

© 2020 IEEE. CA-Polar codes have been selected for all control channel communications in 5G NR, but accurate, computationally feasible decoders are still subject to development. Here we report the performance of a recently proposed class of optimally precise Maximum Likelihood (ML) decoders, GRAND, that can be used with any block-code. As published theoretical results indicate that GRAND is computationally efficient for short- length, high-rate codes and 5G CA-Polar codes are in that class, here we consider GRAND's utility for decoding them. Simulation results indicate that decoding of 5G CA-Polar codes by GRAND, and a simple soft detection variant, is a practical possibility.

Forensic DNA signal is notoriously challenging to interpret and requires the implementation of computational tools that support its interpretation. While data from high-copy, low-contributor samples result in electropherogram signal that is readily interpreted by probabilistic methods, electropherogram signal from forensic stains is often garnered from low-copy, high-contributor-number samples and is frequently obfuscated by allele sharing, allele drop-out, stutter and noise. Since forensic DNA profiles are too complicated to quantitatively assess by manual methods, continuous, probabilistic frameworks that draw inferences on the Number of Contributors (NOC) and compute the Likelihood Ratio (LR) given the prosecution’s and defense’s hypotheses have been developed. In the current paper, we validate a new version of the NOCIt inference platform that determines an A Posteriori Probability (APP) distribution of the number of contributors given an electropherogram. NOCIt is a continuous inference system that incorporates models of peak height (including degradation and differential degradation), forward and reverse stutter, noise and allelic drop-out while taking into account allele frequencies in a reference population. We established the algorithm’s performance by conducting tests on samples that were representative of types often encountered in practice. In total, we tested NOCIt’s performance on 815 degraded, UV-damaged, inhibited, differentially degraded, or uncompromised DNA mixture samples containing up to 5 contributors. We found that the model makes accurate, repeatable and reliable inferences about the NOCs and significantly outperformed methods that rely on signal filtering. By leveraging recent theoretical results of Slooten and Caliebe (FSI:G, 2018) that, under suitable assumptions, establish the NOC can be treated as a nuisance variable, we demonstrated that when NOCIt’s APP is used in conjunction with a downstream likelihood ratio (LR) inference system that employs the same probabilistic model, a full evaluation across multiple contributor numbers is rendered. This work, therefore, illustrates the power of modern probabilistic systems to report holistic and interpretable weights-of-evidence to the trier-of-fact without assigning a specified number of contributors or filtering signal.

DNA-based human identity testing is conducted by comparison of PCR-amplified polymorphic Short Tandem Repeat (STR) motifs from a known source with the STR profiles obtained from uncertain sources. Samples such as those found at crime scenes often result in signal that is a composite of incomplete STR profiles from an unknown number of unknown contributors, making interpretation an arduous task. To facilitate advancement in STR interpretation challenges we provide over 25,000 multiplex STR profiles produced from one to five known individuals at target levels ranging from one to 160 copies of DNA. The data, generated under 144 laboratory conditions, are classified by total copy number and contributor proportions. For the 70% of samples that were synthetically compromised, we report the level of DNA damage using quantitative and end-point PCR. In addition, we characterize the complexity of the signal by exploring the number of detected alleles in each profile.

Short tandem repeat (STR) profiling from DNA samples has long been the bedrock of human identification. The laboratory process is composed of multiple procedures that include quantification, sample dilution, PCR, electrophoresis, and fragment analysis. The end product is a short tandem repeat electropherogram comprised of signal from allele, artifacts, and instrument noise. In order to optimize or alter laboratory protocols, a large number of validation samples must be created at significant expense. As a tool to support that process and to enable the exploration of complex scenarios without costly sample creation, a mechanistic stochastic model that incorporates each of the aforementioned processing features is described herein. The model allows rapid in silico simulation of electropherograms from multicontributor samples and enables detailed investigations of involved scenarios. An implementation of the model that is parameterized by extensive laboratory data is publically available. To illustrate its utility, the model was employed in order to evaluate the effects of sample dilutions, injection time, and cycle number on peak height, and the nature of stutter ratios at low template. We verify the model's findings by comparison with experimentally generated data.

We recently introduced a noise-centric algorithm, Guessing Random Additive Noise Decoding (GRAND), that identifies a Maximum Likelihood (ML) decoding for arbitrary code-books. GRAND has the unusual property that its complexity decreases as code-book rate increases. Here we provide an extension to GRAND, soft-GRAND (SGRAND), that incorporates soft detection symbol reliability information and identifies a ML decoding in that context. In particular, we assume symbols received from the channel are declared to be error free or to have been potentially subject to additive noise. SGRAND inherits desirable properties of GRAND, including being capacity achieving when used with random code-books, and having a complexity that reduces as the code-rate increases.

The advent of high throughput single cell methods such as scRNA-seq has uncovered substantial heterogeneity in the pool of hematopoietic stem and progenitor cells (HSPCs). A significant issue is how to reconcile those findings with the standard model of hematopoietic development, and a fundamental question is how much instruction is inherited by offspring from their ancestors. To address this, we further developed a high-throughput method that enables simultaneously determination of common ancestor, generation, and differentiation status of a large collection of single cells. Data from it revealed that while there is substantial population-level heterogeneity, cells that derived from a common ancestor were highly concordant in their division progression and share similar differentiation outcomes, revealing significant familial effects on both division and differentiation. Although each family diversifies to some extent, the overall collection of cell types observed in a population is largely composed of homogeneous families from heterogeneous ancestors. Heterogeneity between families could be explained, in part, by differences in ancestral expression of cell-surface markers that are used for phenotypic HSPC identification: CD48, SCA-1, c-kit and Flt3. These data call for a revision of the fundamental model of haematopoiesis from a single tree to an ensemble of trees from distinct ancestors where common ancestor effect must be considered. As HSPCs are cultured in the clinic before bone marrow transplantation, our results suggest that the broad range of engraftment and proliferation capacities of HSPCs could be consequences of the heterogeneity in their engrafted families, and altered culture conditions might reduce heterogeneity between families, possibly improving transplantation outcomes.

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon's 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg's 1978 theorem on the NP-hardness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes., This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

We introduce a new algorithm for realizing maximum likelihood (ML) decoding for arbitrary codebooks in discrete channels with or without memory, in which the receiver rank-orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the codebook is the ML decoding. We name this algorithm GRAND for Guessing Random Additive Noise Decoding. We establish that GRAND is capacity-Achieving when used with random codebooks. For rates below capacity, we identify error exponents, and for rates beyond capacity, we identify success exponents. We determine the scheme's complexity in terms of the number of computations that the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which, if a member of the codebook is identified, that it is likely to be the transmitted code word. We introduce an approximate ML decoding scheme where the receiver abandons the search after a fixed number of queries, an approach we dub GRANDAB, for GRAND with ABandonment. While not an ML decoder, we establish that the algorithm GRANDAB is also capacity-Achieving for an appropriate choice of abandonment threshold, and characterize its complexity, error, and success exponents. Worked examples are presented for Markovian noise that indicate these decoding schemes substantially outperform the brute force decoding approach., National Science Foundation (U.S.) (Grant 6932716)

© 1963-2012 IEEE. We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. In this setting, we present an estimation-theoretic analysis of the privacy-utility trade-off (PUT). Here, an analyst is allowed to reconstruct (in a mean-squared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how chi-square information captures the fundamental PUT in this case and provide bounds for the best PUT. We propose a convex program to compute privacy-assuring mappings when the functions to be disclosed and hidden are known a priori and the data distribution is known. We derive lower bounds on the minimum mean-squared error of estimating a target function from the disclosed data and evaluate the robustness of our approach when an empirical distribution is used to compute the privacy-assuring mappings instead of the true data distribution. We illustrate the proposed approach through two numerical experiments.

Severe infections are a major source of stress on haematopoiesis, where consequences for haematopoietic stem cells (HSCs) have only recently started to emerge. HSC function critically depends on the integrity of complex bone marrow niches, which have been shown to be altered during ageing and haematopoietic malignancies. Whether the bone marrow (BM) microenvironment plays a role in mediating the effects of infection on HSCs remains an open question. Here we used an murine model of malaria coupled with intravital microscopy, single cell RNA-Seq, mathematical modelling and transplantation assays to obtain a quantitative understanding of the proliferation dynamics of haematopoietic stem and progenitor cells (HSPCs) duringPlasmodiuminfection. We uncovered that duringPlasmodiuminfection the HSC compartment turns over significantly faster than in steady state, and that a global interferon response and loss of functional HSCs are linked to alterations in BM endothelium function and osteoblasts number. Interventions that targeted osteoblasts uncoupled HSC proliferation and function, thus opening up new avenues for therapeutic interventions that may improve the health of survivors of severe infections.

© 2018 IEEE. We introduce a new algorithm for Maximum Likelihood (ML) decoding for channels with memory. The algorithm is based on the principle that the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in an element of the code-book is the ML decoding. In contrast to traditional approaches, this novel scheme has the desirable property that it becomes more efficient as the code-book rate increases. We establish that the algorithm is capacity achieving for randomly selected code-books. When the code-book rate is less than capacity, we identify asymptotic error exponents as the block length becomes large. When the code-book rate is beyond capacity, we identify asymptotic success exponents. We determine properties of the complexity of the scheme in terms of the number of computations the receiver must perform per block symbol. Worked examples are presented for binary memoryless and Markovian noise. These demonstrate that block-lengths that offer a good complexity-rate tradeoff are typically smaller than the reciprocal of the bit error rate.

Continuous mixture interpretation methods that employ probabilistic genotyping to compute the Likelihood Ratio (LR) utilize more information than threshold-based systems. The continuous interpretation schemes described in the literature, however, do not all use the same underlying probabilistic model and standards outlining which probabilistic models may or may not be implemented into casework do not exist; thus, it is the individual forensic laboratory or expert that decides which model and corresponding software program to implement. For countries, such as the United States, with an adversarial legal system, one can envision a scenario where two probabilistic models are used to present the weight of evidence, and two LRs are presented by two experts. Conversely, if no independent review of the evidence is requested, one expert using one model may present one LR as there is no standard or guideline requiring the uncertainty in the LR estimate be presented. The choice of model determines the underlying probability calculation, and changes to it can result in non-negligible differences in the reported LR or corresponding verbal categorization presented to the trier-of-fact. In this paper, we study the impact of model differences on the LR and on the corresponding verbal expression computed using four variants of a continuous mixture interpretation method. The four models were tested five times each on 101, 1-, 2- and 3-person experimental samples with known contributors. For each sample, LRs were computed using the known contributor as the person of interest. In all four models, intra-model variability increased with an increase in the number of contributors and with a decrease in the contributor's template mass. Inter-model variability in the associated verbal expression of the LR was observed in 32 of the 195 LRs used for comparison. Moreover, in 11 of these profiles there was a change from LR > 1 to LR < 1. These results indicate that modifications to existing continuous models do have the potential to significantly impact the final statistic, justifying the continuation of broad-based, large-scale, independent studies to quantify the limits of reliability and variability of existing forensically relevant systems.

The generation of cellular heterogeneity is an essential feature of immune responses. Understanding the heritability and asymmetry of phenotypic changes throughout this process requires determination of clonal-level contributions to fate selection. Evaluating intraclonal and interclonal heterogeneity and the influence of distinct fate determinants in large numbers of cell lineages, however, is usually laborious, requiring familial tracing and fate mapping. In this study, we introduce a novel, accessible, high-throughput method for measuring familial fate changes with accompanying statistical tools for testing hypotheses. The method combines multiplexing of division tracking dyes with detection of phenotypic markers to reveal clonal lineage properties. We illustrate the method by studying in vitro–activated mouse CD8+ T cell cultures, reporting division and phenotypic changes at the level of families. This approach has broad utility as it is flexible and adaptable to many cell types and to modifications of in vitro, and potentially in vivo, fate monitoring systems.

We consider an abstraction of computational security in password protected systems where a user draws a secret string of given length with i.i.d. characters from a finite alphabet, and an adversary would like to identify the secret string by querying, or guessing, the identity of the string. The concept of a "total entropy budget" on the chosen word by the user is natural, otherwise the chosen password would have arbitrary length and complexity. One intuitively expects that a password chosen from the uniform distribution is more secure. This is not the case, however, if we are considering only the average guesswork of the adversary when the user is subject to a total entropy budget. The optimality of the uniform distribution for the user's secret string holds when we have also a budget on the guessing adversary. We suppose that the user is subject to a "total entropy budget" for choosing the secret string, whereas the computational capability of the adversary is determined by his "total guesswork budget." We study the regime where the adversary's chances are exponentially small in guessing the secret string chosen subject to a total entropy budget. We introduce a certain notion of uniformity and show that a more uniform source will provide better protection against the adversary in terms of his chances of success in guessing the secret string. In contrast, the average number of queries that it takes the adversary to identify the secret string is smaller for the more uniform secret string subject to the same total entropy budget., In Proc. of Allerton 2017 (19 pages, 4 figures)

If trees are constructed from a pure birth process and one defines the depth of a leaf to be the number of edges to its root, it is known that the variance in the depth of a randomly selected leaf of a randomly selected tree grows linearly in time. In this letter, we instead consider the variance of the average depth of leaves within each individual tree, establishing that, in contrast, it converges to a constant, 7. This result indicates that while the variance in leaf depths amongst the ensemble of pure birth processes undergoes large fluctuations, the average depth across individual trees is much more consistent.

Samples containing low-copy numbers of DNA are routinely encountered in casework. The signal acquired from these sample types can be difficult to interpret as they do not always contain all of the genotypic information from each contributor, where the loss of genetic information is associated with sampling and detection effects. The present work focuses on developing a validation scheme to aid in mitigating the effects of the latter. We establish a scheme designed to simultaneously improve signal resolution and detection rates without costly large-scale experimental validation studies by applying a combined simulation and experimental based approach. Specifically, we parameterize an in silico DNA pipeline with experimental data acquired from the laboratory and use this to evaluate multifarious scenarios in a cost-effective manner. Metrics such as signal1copy-to-noise resolution, false positive and false negative signal detection rates are used to select tenable laboratory parameters that result in high-fidelity signal in the single-copy regime. We demonstrate that the metrics acquired from simulation are consistent with experimental data obtained from two capillary electrophoresis platforms and various injection parameters. Once good resolution is obtained, analytical thresholds can be determined using detection error tradeoff analysis, if necessary. Decreasing the limit of detection of the forensic process to one copy of DNA is a powerful mechanism by which to increase the information content on minor components of a mixture, which is particularly important for probabilistic system inference. If the forensic pipeline is engineered such that high-fidelity electropherogram signal is obtained, then the likelihood ratio (LR) of a true contributor increases and the probability that the LR of a randomly chosen person is greater than one decreases. This is, potentially, the first step towards standardization of the analytical pipeline across operational laboratories.

We explore properties and applications of the Principal Inertia Components (PICs) between two discrete random variables $X$ and $Y$. The PICs lie in the intersection of information and estimation theory, and provide a fine-grained decomposition of the dependence between $X$ and $Y$. Moreover, the PICs describe which functions of $X$ can or cannot be reliably inferred (in terms of MMSE) given an observation of $Y$. We demonstrate that the PICs play an important role in information theory, and they can be used to characterize information-theoretic limits of certain estimation problems. In privacy settings, we prove that the PICs are related to fundamental limits of perfect privacy., Comment: Overlaps with arXiv:1405.1472 and arXiv:1310.1512

We introduce Network Maximal Correlation (NMC) as a multivariate measure of nonlinear association among random variables. NMC is defined via an optimization that infers transformations of variables by maximizing aggregate inner products between transformed variables. For finite discrete and jointly Gaussian random variables, we characterize a solution of the NMC optimization using basis expansion of functions over appropriate basis functions. For finite discrete variables, we propose an algorithm based on alternating conditional expectation to determine NMC. Moreover we propose a distributed algorithm to compute an approximation of NMC for large and dense graphs using graph partitioning. For finite discrete variables, we show that the probability of discrepancy greater than any given level between NMC and NMC computed using empirical distributions decays exponentially fast as the sample size grows. For jointly Gaussian variables, we show that under some conditions the NMC optimization is an instance of the Max-Cut problem. We then illustrate an application of NMC in inference of graphical model for bijective functions of jointly Gaussian variables. Finally, we show NMC's utility in a data application of learning nonlinear dependencies among genes in a cancer dataset., Comment: 17 pages, 5 figures

SummaryCellular barcoding and other single-cell lineage-tracing strategies form experimental methodologies for analysis of in vivo cell fate that have been instrumental in several significant recent discoveries. Due to the highly nonlinear nature of proliferation and differentiation, interrogation of the resulting data for evaluation of potential lineage pathways requires a new quantitative framework complete with appropriate statistical tests. Here, we develop such a framework, illustrating its utility by analyzing data from barcoded multipotent cells of the blood system. This application demonstrates that the data require additional paths beyond those found in the classical model, which leads us to propose that hematopoietic differentiation follows a loss of potential mechanism and to suggest further experiments to test this deduction. Our quantitative framework can evaluate the compatibility of lineage trees with barcoded data from any proliferating and differentiating cell system.

Constraint satisfaction problems (CSPs) lie at the heart of many modern industrial and commercial tasks. An important new collection of CSPs has recently been emerging that differ from classical problems in that they impose constraints on the class of algorithms that can be used to solve them. In computer network applications, these constraints arise as the variables within the CSP are located at physically distinct devices that cannot communicate. At each instant, every variable only knows if all its constraints are met or at least one is not. Consequently, the CSP’s solution must be found using a decentralized approach. Existing algorithms for solving CSPs are either centralized or distributed, both of which fundamentally violate these algorithmic constraints. In this article we present the first algorithm for solving CSPs that satisfies these new constraints. It is fully decentralized, making no use of a centralized controller or message-passing between variables. We prove that this algorithm converges with probability one to a satisfying assignment whenever one exists. Surprisingly, we experimentally demonstrate that the time the algorithm takes to find a satisfying assignment is competitive with bothWalkSat and Survey Propagation, two popular and efficient CSP solvers. That is, despite its decentralized nature the algorithm is remarkably fast. This raises new questions about the relationship between information sharing and algorithm performance.

International audience; The dynamic process by which self-­‐renewing stem cells and their offspring proliferate and differentiate to create the erythroid, myeloid and lymphoid lineages of the blood system has long since been an important topic of study. A range of recent single cell and family-­‐tracing methodologies such as massively parallel single-­‐cell RNA-­‐sequencing, mass cytometry, integration site barcoding, cellular barcoding and transposon barcoding are enabling unprecedented analysis, dissection and re-­‐evaluation of the hematopoietic tree. In addition to the substantial experimental advances, these new techniques have required significant theoretical development in order to make biological deductions from their data. Here we review these approaches from both an experimental and inferential point of view, considering their discoveries to date, their capabilities, limitations and opportunities for further development.

Background Cellular barcoding is a recently developed biotechnology tool that enables the familial identification of progeny of individual cells in vivo. In immunology, it has been used to track the burst-sizes of multiple distinct responding T cells over several adaptive immune responses. In the study of hematopoiesis, it revealed fate heterogeneity amongst phenotypically identical multipotent cells. Most existing approaches rely on ex vivo viral transduction of cells with barcodes followed by adoptive transfer into an animal, which works well for some systems, but precludes barcoding cells in their native environment such as those inside solid tissues. Results With a view to overcoming this limitation, we propose a new design for a genetic barcoding construct based on the Cre Lox system that induces randomly created stable barcodes in cells in situ by exploiting inherent sequence distance constraints during site-specific recombination. We identify the cassette whose provably maximal code diversity is several orders of magnitude higher than what is attainable with previously considered Cre Lox barcoding approaches, exceeding the number of lymphocytes or hematopoietic progenitor cells in mice. Conclusions Its high diversity and in situ applicability, make the proposed Cre Lox based tagging system suitable for whole tissue or even whole animal barcoding. Moreover, it can be built using established technology. Electronic supplementary material The online version of this article (doi:10.1186/s12918-016-0290-3) contains supplementary material, which is available to authorized users.