We consider the lattice-input discrete-time Poisson (LIDTP) channel, which is a discrete-time Poisson (DTP) channel where the input is constrained to a lattice$\alpha \mathbb{Z}^{\geq 0}$, for some fixed parameter$\alpha> 0$, and where$\mathbb{Z}^{\geq 0}$denotes the set of non-negative integers. The LIDTP channel arises in the analysis of some channel models proposed in the DNA storage literature, which motivated our study. We show that the difference in capacity between the LIDTP channel and the standard DTP channel is upper-bounded by$K(\alpha)+R(\mathcal{E})+o(1)$, where$\mathcal{E}$is a mean power constraint on the input and the asymptotics are with respect to the ratio$\mathcal{E} / \alpha$going to infinity. The terms$K(\alpha)$and$R(\mathcal{E})$are given explicitly and tend to 0 with$\alpha \rightarrow 0$and$\mathcal{E} \rightarrow \infty$, as$O\left(\alpha \log \frac{1}{\alpha}\right)$and$O\left(\mathcal{E}^{-1 / 2}\right)$, respectively. Thus, for fixed$\alpha$and$\mathcal{E} \rightarrow \infty$, the term$K(\alpha)$bounds the gap in capacity incurred by enforcing a regular discrete input, and, as$\alpha$gets ever smaller, the asymptotic capacity of the LIDTP with$\mathcal{E} \rightarrow \infty$matches that of the DTP. We also show a non-asymptotic bound on the difference between the capacities of the LIDTP and DTP channels, of the form$K(\alpha)+R^{\prime}(\mathcal{E})+\frac{1}{2} \log 2 \pi e$. The term$R^{\prime}(\mathcal{E})$is also given explicitly and vanishes as$O(1 / \mathcal{E})$when$\mathcal{E} \rightarrow \infty$.

Since the beginning of 2020, COVID-19 has had a strong impact on the health of the world population. Tracing the contacts of infected people is one of the main strategies for controlling the pandemic. Given the high rates of contagion, which makes difficult an effective manual tracing, multiple initiatives arose for developing digital proximity tracing technologies. In this paper, we discuss in depth the security and personal data protection requirements that these technologies must satisfy, and we present an exhaustive and detailed list of the various applications that have been deployed globally. In particular, we identify potential threats that could undermine the satisfaction of the analyzed requirements, violating hegemonic personal data protection regulations.

MOTIVATION: Nanopore sequencing technologies are rapidly gaining popularity, in part, due to the massive amounts of genomic data they produce in short periods of time (up to 8.5 TB of data in <72 h). To reduce the costs of transmission and storage, efficient compression methods for this type of data are needed. RESULTS: We introduce RENANO, a reference-based lossless data compressor specifically tailored to FASTQ files generated with nanopore sequencing technologies. RENANO improves on its predecessor ENANO, currently the state of the art, by providing a more efficient base call sequence compression component. Two compression algorithms are introduced, corresponding to the following scenarios: (1) a reference genome is available without cost to both the compressor and the decompressor and (2) the reference genome is available only on the compressor side, and a compacted version of the reference is included in the compressed file. We compare the compression performance of RENANO against ENANO on several publicly available nanopore datasets. RENANO improves the base call sequences compression of ENANO by 39.8% in scenario (1), and by 33.5% in scenario (2), on average, over all the datasets. As for total file compression, the average improvements are 12.7% and 10.6%, respectively. We also show that RENANO consistently outperforms the recent general-purpose genomic compressor Genozip. AVAILABILITY AND IMPLEMENTATION: RENANO is freely available for download at: https://github.com/guilledufort/RENANO. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The amount of genomic data generated globally is seeing explosive growth, leading to increasing needs for processing, storage and transmission resources, which motivates the development of efficient compression tools for these data. Work so far has focused mainly on the compression of data generated by short-read technologies. However, nanopore sequencing technologies are rapidly gaining popularity due to the advantages offered by the large increase in the average size of the produced reads, the reduction in their cost and the portability of the sequencing technology. We present ENANO (Encoder for NANOpore), a novel lossless compression algorithm especially designed for nanopore sequencing FASTQ files. RESULTS: The main focus of ENANO is on the compression of the quality scores, as they dominate the size of the compressed file. ENANO offers two modes, Maximum Compression and Fast (default), which trade-off compression efficiency and speed. We tested ENANO, the current state-of-the-art compressor SPRING and the general compressor pigz on several publicly available nanopore datasets. The results show that the proposed algorithm consistently achieves the best compression performance (in both modes) on every considered nanopore dataset, with an average improvement over pigz and SPRING of >24.7% and 6.3%, respectively. In addition, in terms of encoding and decoding speeds, ENANO is 2.9× and 1.7× times faster than SPRING, respectively, with memory consumption up to 0.2 GB. AVAILABILITY AND IMPLEMENTATION: ENANO is freely available for download at: https://github.com/guilledufort/EnanoFASTQ. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study the maximum Markov model order that can be estimated for an (individual) input sequence x of length n over a finite alphabet of size α, for popular estimators of tree models, where the estimated order is determined by the depth of a context tree estimate, and in the special case of plain Markov models, where the tree is constrained to be perfect (with all leaves at the same depth). First, we consider penalized maximum likelihood estimators where a context tree T̂ is obtained by minimizing a cost of the form - log P̂τ(x) + f(n)|Sτ|, where P̂τ(x) is the ML of x under a model with context tree T, Sτis the set of leaves of T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator is a special case with f(n) = α-1/2 log n). For plain Markov models, a simple argument yields a known upper bound k̅(n) = O(log n) on the maximum order that can be estimated for x, and we show that, in fact, this simple bound is not far from tight. For general context trees, we derive an asymptotic upper bound, n1/2-o(1), on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to a multiplicative constant factor. We show that a similar upper bound applies also to MDL estimators based on the KT probability assignment and, moreover, the same example sequences asymptotically approach the upper bound also in this case.

This paper proposes lossless and near-lossless compression algorithms for multichannel biomedical signals. The algorithms are sequential and efficient, which makes them suitable for low-latency and low-power signal transmission applications. We make use of information theory and signal processing tools (such as universal coding, universal prediction, and fast online implementations of multivariate recursive least squares), combined with simple methods to exploit spatial as well as temporal redundancies typically present in biomedical signals. The algorithms are tested with publicly available electroencephalogram and electrocardiogram databases, surpassing in all cases the current state of the art in near-lossless and lossless compression ratios.

We study the maximum depth of context tree estimates, i.e., the maximum Markov order attainable by an estimated tree model given an (individual) input sequence of length n. We consider two classes of estimators: 1) Penalized maximum likelihood (PML) estimators where a context tree T̂ is obtained by minimizing a cost of the form - log P̂T(xn)+f(n)|S|, where P̂;T(xn) is the ML probability of the input sequence xnunder a tree model T, STis the set of states defined by T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n) = α-1/2 log n where α is the size of the input alphabet). 2) MDL estimators based on the KT probability assignment. In each case we derive an asymptotic upper bound, n1/2+o(1), on the estimated depth, and we exhibit explicit input sequences that asymptotically attain the bound up to the term o(1) in the exponent.

Efficient enumerative coding for tree sources is, in general, surprisingly intricate-a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models, such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the family of tree models in the sense that, for a string emitted by an unknown source whose model is supported on a known tree, the expected normalized code length of the encoding approaches the entropy rate of the source with a convergence rate (K/2)(log n)/n, where K is the number of free parameters of the model family. Based on recent results characterizing type classes of context trees, the code consists of the index of the sequence in the tree type class, and an efficient description of the class itself using a nonuniform encoding of selected string counts. The results are extended to a twice-universal setting, where the tree underlying the source model is unknown.

Suffix trees (ST) are useful in information-theoretic applications such as model order estimation and lossless source coding, which require access to occurrence counts of patterns of arbitrary length in an input string x. If the length of x, n, is large, the memory required to represent the ST may become a practical performance bottleneck. This can be alleviated, in cases where a nontrivial upper bound is known on the lengths of the patterns of interest, by using a truncated ST (TST). However, conventional TST implementations still require Ω(n) bits of memory, due to the need to store x. We describe a new TST representation that avoids this limitation by storing all the information necessary to reconstruct the TST edge labels in a string y that is often much shorter than x. We apply TSTs to the implementation of Markov order estimators, where an upper bound knon the estimated order is either imposed (for consistency, as in KT-based MDL estimators), or can be derived (as in the BIC estimator). The new representation allows for estimator implementations with sublinear space complexity in some cases of interest. In other cases we show, experimentally, that even when the new representation does not have an asymptotic advantage, it still achieves very significant memory savings in practice.

We study the maximal values estimated by commonly used Markov model order estimators on individual sequences. We start with penalized maximum likelihood (PML) estimators with cost functions of the form - log Pk(xn) + f (n)αk, where Pk(xn) is the ML probability of the input sequence xnunder a Markov model of order k, a is the size of the input alphabet, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n) = α - 1/2 log n). Comparison with a memoryless model yields a known upper bound k(n) on the maximum order that xncan estimate. We show that, under mild conditions on f that are satisfied by commonly used penalization functions, this simple bound is not far from tight, in the following sense: for sufficiently large n, and any knthat estimate order k; moreover, for all but a vanishing fraction of the values of n such that k = k̅(n), there are sequences xnthat estimate order k. We also study KT-based MDL Markov order estimators, and show that in this case, there are sequences xnthat estimate order n1/2-ϵ, which is much larger than the maximum log n/log α(l + o(1)) attainable by BIC, or the order o(log n) required for consistency of the KT estimator. In fact, for these sequences, limiting the allowed estimated order might incur in a significant asymptotic penalty in description length. All the results are constructive, and in each case we exhibit explicit sequences that attain the claimed estimated orders.

It is well known that a tree model does not always admit a finite-state machine (FSM) representation with the same (minimal) number of parameters. Therefore, known characterizations of type classes for FSMs do not apply, in general, to tree models. In this paper, the type class of a sequence with respect to a given context tree is studied. An exact formula is derived for the size of the class, extending Whittle's formula for type classes with respect to FSMs. The derivation is more intricate than in the FSM case, since some basic properties of FSM types do not hold in general for tree types. The derivation also yields an efficient enumeration of the tree type class. A formula for the number of type classes with respect to is also derived. The formula is asymptotically tight up to a multiplicative constant and also extends the corresponding result for FSMs. The asymptotic behavior of the number of type classes, and of the size of a class, is expressed in terms of the so-called minimal canonical extension of T, a tree that is generally larger than but smaller than its FSM closure.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

Efficient enumerative coding for tree sources is, in general, surprisingly intricate-a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the class of tree sources in the sense that, for a string emitted by an unknown source supported on a known tree, the expected normalized code length approaches the entropy rate of the source with a convergence rate (K/2)(log n)/n, where K is the number of free parameters of the source. The results extend also to the twice-universal setting, where the tree is unknown.

Given a parametric model family, the set of sequences of length n over a finite alphabet A is partitioned into type classes, where two sequences belong to the same class if and only if they are assigned the same probability by all models in the family. Since all sequences in a class are equiprobable, the universal probability assignment problem for the given model family reduces to optimally assigning probabilities to type classes. This reduction is optimally performed by the Normalized Maximum Likelihood (NML) code, which can be interpreted as a description of the type, generated by assigning to it a probability proportional to its ML probability, followed by an enumeration of the sequences in the type class. Unfortunately, implementing the NML code is difficult even for the simplest model classes. Other universal methods, based, for example, on the Krichevskii-Trofimov sequential probability assignment, are computationally efficient and also assign the same code length to all the sequences of a given type. They do not, however, provide a separate and identifiable description of the type. In this paper, we are interested in universal enumerative source codes that possess both qualities: they provide a separate description of the type class of the encoded sequence, and this description can be efficiently computed. By "efficient computation" we mean one with running time that is polynomial in the length of the input sequence, as well as in the number of model parameters.

The problem of universal simulation given a training sequence is studied both in a stochastic setting and for individual sequences. In the stochastic setting, the training sequence is assumed to be emitted by a Markov source of unknown order, extending previous work where the order is assumed known and leading to the notion of twice-universal simulation. A simulation scheme, which partitions the set of sequences of a given length into classes, is proposed for this setting and shown to be asymptotically optimal. This partition extends the notion of type classes to the twice-universal setting. In the individual sequence scenario, the same simulation scheme is shown to generate sequences which are statistically similar, in a strong sense, to the training sequence, for statistics of any order, while essentially maximizing the uncertainty on the output.

It is well known that a tree model does not always admit a finite-state machine (FSM) representation with the same (minimal) number of parameters. Therefore, known characterizations of type classes for FSMs do not apply, in general, to tree models. In this paper, the type class of a string with respect to a tree model is studied, and an exact formula is derived for the size of the class. The formula, which applies to arbitrary trees, generalizes Whittle's formula for FSMs. The derivation is more intricate than the FSM case, since some basic properties of FSM types do not hold in general for tree-model types. The derivation also yields an efficient enumeration of the tree-model type class, which has applications in universal data compression and universal simulation. A formula for the number of type classes with respect to a given tree is also derived. The formula is asymptotically tight up to multiplication by a constant and also generalizes a known result for FSMs.

Steganography is the art of secret communication. Its purpose is to hide the presence of information, using, for example, images as covers. We experimentally investigate if stego-images, bearing a secret message, are statistically "natural." For this purpose, we use recent results on the statistics of natural images and investigate the effect of some popular steganography techniques. We found that these fundamental statistics of natural images are, in fact, generally altered by the hidden "nonnatural" information. Frequently, the change is consistently biased in a given direction. However, for the class of natural images considered, the change generally falls within the intrinsic variability of the statistics, and, thus, does not allow for reliable detection, unless knowledge of the data hiding process is taken into account. In the latter case, significant levels of detection are demonstrated.

Applying generalized context trees and their finite state machine closures, a two-pass version of context, a twice-universal lossless coding scheme for tree models, can be implemented in linear encoding/decoding time. As it turns out, an optimal context selection rule and the corresponding context transitions are computationally not more expensive than the various steps involved in the implementation of the Burrows-Wheeler transform (BWT) and use, in fact, similar tools. Also the paper presents a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. This transform offers insight into the workings of the BWT and the nature of its suboptimality for twice-universal coding of tree models.

This paper presents the first algorithm for linear time encoding/decoding of a twice-universal code in class of tree models. The implemented code is a two-pass (semi-predictive) version of context. The algorithmic tools employed in its derivation and their information-theoretic implications is also investigated. The FSM closure of a generalised context tree, defined as the smallest finite-state machine is characterised.

Tree models are efficient parametrizations of finite-memory processes, offering potentially significant model cost savings. The information theory literature has focused mostly on redundancy aspects of the universal estimation and coding of these models. In this paper, we investigate representations and supporting data structures for finite-memory processes, as well as the major impact these structures have on the universal algorithms in which they are used. We first generalize the class of tree models, and then define and investigate the properties of the finite-state machine (FSM) closure of a tree, which is the smallest FSM that generates all the processes generated by the tree. The interaction between FSM closures, generalized context trees (GCTs), and classical data structures such as compact suffix trees brings together the information-theoretic and the computational aspects, leading to the first algorithm for linear time encoding/decoding of a lossless twice-universal code in the class of three models. The implemented code is a two-pass version of Context. The corresponding optimal context selection rule and context transitions use tools similar to those employed in efficient implementation of the popular Burrows-Wheeler transform (BWT), yielding similar computational complexities. We also present a reversible transform that displays the same "context deinterleaving" feature as the BWT but is naturally based on an optimal context tree. FSM closures are also applied to an investigation of the effect of time reversal on tree models, motivated in part by the following question: When compressing a data sequence using a universal scheme in the class of tree models, can it make a difference whether we read the sequence from left to right or from right to left? Given a tree model of a process, we show constructively that the number of states in the tree model corresponding to the reversed process might be, in the extreme case, quadratic in the number of states of the original tree. This result answers the above motivating question in the affirmative.