A de Bruijn sequence of order$k$over a finite alphabet is a cyclic sequence with the property that it contains every possible$k$-sequence as a substring exactly once. Orthogonal de Bruijn sequences are collections of de Bruijn sequences of the same order,$k$, satisfying the joint constraint that every ($k+1$) sequence appears as a substring in at most one of the sequences in the collection. Both de Bruijn and orthogonal de Bruijn sequences have found numerous applications in synthetic biology, although the latter topic remains largely unexplored in the coding theory literature. Here we study three relevant practical generalizations of orthogonal de Bruijn sequences where we relax either the constraint that every ($k+1$) -sequence appears exactly once, or that the sequences themselves are de Bruijn rather than balanced de Bruijn sequences. We also provide lower and upper bounds on the number of fixed-weight orthogonal de Bruijn sequences.

Data deduplication refers to a collection of data processing strategies that aim to remove repeated data chunks stored by different users. Despite providing excellent storage savings, deduplication can lead to severe file fragmentation issues: data chunks of the same file may be stored at distal locations on the server, making reconstruction time-consuming. Here, we continue our analytical study of uncoded and coded deduplication methods with reduced fragmentation levels. We model files as self-avoiding (simple) paths in specialized graphs whose nodes correspond to data chunks. To measure the level of fragmentation, we introduce the jump metric which captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. We derive lower and upper bounds on the degree of jump fragmentation, and provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. We also present examples that show how repetition and coded redundancy in chunk stores can reduce jump fragmentation.

We introduce a new graph diffusion model for small drug molecule generation which simultaneously offers a 10-fold reduction in the number of diffusion steps when compared to existing methods, preservation of small molecule graph motifs via motif compression, and an average 3\% improvement in SMILES validity over the DiGress model across all real-world molecule benchmarking datasets. Furthermore, our approach outperforms the state-of-the-art DeFoG method with respect to motif-conservation by roughly 4\%, as evidenced by high ChEMBL-likeness, QED and newly introduced shingles distance scores. The key ideas behind the approach are to use a combination of deterministic and random subgraph perturbations, so that the node and edge noise schedules are codependent; to modify the loss function of the training process in order to exploit the deterministic component of the schedule; and, to ''compress'' a collection of highly relevant carbon ring and other motif structures into supernodes in a way that allows for simple subsequent integration into the molecular scaffold.

Machine unlearning techniques aim to mitigate unintended memorization in large language models (LLMs). However, existing approaches predominantly focus on the explicit removal of isolated facts, often overlooking latent inferential dependencies and the non-deterministic nature of knowledge within LLMs. Consequently, facts presumed forgotten may persist implicitly through correlated information. To address these challenges, we propose a knowledge unlearning evaluation framework that more accurately captures the implicit structure of real-world knowledge by representing relevant factual contexts as knowledge graphs with associated confidence scores. We further develop an inference-based evaluation protocol leveraging powerful LLMs as judges; these judges reason over the extracted knowledge subgraph to determine unlearning success. Our LLM judges utilize carefully designed prompts and are calibrated against human evaluations to ensure their trustworthiness and stability. Extensive experiments on our newly constructed benchmark demonstrate that our framework provides a more realistic and rigorous assessment of unlearning performance. Moreover, our findings reveal that current evaluation strategies tend to overestimate unlearning effectiveness.

Data deduplication, one of the key features of modern Big Data storage devices, is the process of removing replicas of data chunks stored by different users. Despite the importance of deduplication, several drawbacks of the method, such as storage robustness and file fragmentation, have not been previously analyzed from a theoretical point of view. Storage robustness pertains to ensuring that deduplicated data can be used to reconstruct the original files without service disruptions and data loss. Fragmentation pertains to the problems of placing deduplicated data chunks of different user files in a proximity-preserving linear order, since neighboring chunks of the same file may be stored in sectors far apart on the server. This work proposes a new theoretical model for data fragmentation and introduces novel graph- and coding-theoretic approaches for reducing fragmentation via limited duplication (repetition coding) and coded deduplication (e.g., linear coding). In addition to alleviating issues with fragmentation, limited duplication and coded deduplication can also serve the dual purpose of increasing the robusteness of the system design. The contributions of our work are three-fold. First, we describe a new model for file structures of the form of self-avoiding (simple) paths in specialized graphs. Second, we introduce several new metrics for measuring the fragmentation level in deduplication systems on graph-structured files, including thestretch metricthat captures the worst-case “spread” of adjacent data chunks within a file when deduplicated and placed on the server; and, thejump metricthat captures the worst-case number of times during the reconstruction process of a file that one has to change the readout location on the server. For the stretch metric, we establish a connection between the level of fragmentation and thebandwidthof the file-graph. In particular, we derive lower and upper bounds on the degree of fragmentation and describe instances of the problem where repetition and coding reduce fragmentation. The key ideas behind our approach are graph folding and information-theoretic arguments coupled with graph algorithms such as matching. For the jump metric, we provide a new algorithm for computing the jump number of hierarchical data structures captured by trees. Third, we describe how controlled repetition and coded redundancy added after deduplication can ensure valuable trade-offs between the storage volume and the degree of fragmentation.

We study the problem of online conditional distribution estimation with \emph{unbounded} label sets under local differential privacy. The problem may be succinctly stated as follows. Let $\mathcal{F}$ be a distribution-valued function class with an unbounded label set. Our aim is to estimate an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion. More precisely, at time $t$, given a sample ${\mathbf{x}}_t$, we generate an estimate of $f({\mathbf{x}}_t)$ using only a \emph{privatized} version of the true \emph{labels} sampled from $f({\mathbf{x}}_t)$. The objective is to minimize the cumulative KL-risk of a finite horizon $T$. We show that under $(\epsilon,0)$-local differential privacy for the labels, the KL-risk equals $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT}),$ up to poly-logarithmic factors, where $K=|\mathcal{F}|$. This result significantly differs from the $\tilde{\Theta}(\sqrt{T\log K})$ bound derived in Wu et al., (2023a) for \emph{bounded} label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem of Gopi et al., (2020), which has only been established for the \emph{batch} setting.

In our problem, we are given access to a number of sequences of nonnegative i.i.d. random variables, whose realizations are observed sequentially. All sequences are of the same finite length. The goal is to pick one element from each sequence in order to maximize a reward equal to the expected value of the sum of the selections from all sequences. The decision on which element to pick is irrevocable, i.e., rejected observations cannot be revisited. Furthermore, the procedure terminates upon having a single selection from each sequence. Our observation constraint is that we cannot observe the current realization of all sequences at each time instant. Instead, we can observe only a smaller, yet arbitrary, subset of them. Thus, together with a stopping rule that determines whether we choose or reject the sample, the solution requires a sampling rule that determines which sequence to observe at each instant. The problem can be solved via dynamic programming, but with an exponential complexity in the length of the sequences. In order to make the solution computationally tractable, we introduce a decoupling approach and determine each stopping time using either a single-sequence dynamic programming, or a Prophet Inequality inspired threshold method, with polynomial complexity in the length of the sequences. We prove that the decoupling approach guarantees at least 0.745 of the optimal expected reward of the joint problem. In addition, we describe how to efficiently compute the optimal number of samples for each sequence, and its' dependence on the variances.

The performance of Transfer Learning (TL) significantly depends on effective pretraining, which not only requires extensive amounts of data but also substantial computational resources. As a result, in practice, it is challenging to successfully perform TL at the level of individual model developers. Federated Learning (FL) addresses these challenges by enabling collaboration among individual clients through an indirect expansion of the available dataset, distribution of the computation burden across different entities, and privacy-preserving communication mechanisms. Despite several attempts to devise effective transferable FL approaches, several important issues remain unsolved. First, existing methods in this setting primarily focus on optimizing transferability within their local client domains, thereby ignoring transferability over the global learning domain. Second, most approaches focus on analyzing indirect transferability metrics, which does not allow for accurate assessment of the final target loss and extent of transferability. To address these issues, we introduce two important FL features into the model. The first boosts transferability via an exchange protocol between the clients and the server that includes information about cross-client Jacobian (gradient) norms. The second feature promotes an increase of the average of the Jacobians of the clients at the server side, which is subsequently used as a local regularizer that reduces the cross-client Jacobian variance. A rigorous analysis of our transferable federated algorithm, termed FedGTST (Federated Global Transferability via Statistics Tuning), reveals that increasing the averaged Jacobian norm across clients and reducing its variance ensures tight control of the target loss. This insight leads to the first known upper bound on the target loss of transferable federated learning in terms of the source loss and source-target domain discrepancy. Extensive experimental results on datasets including MNIST → MNIST-M and CIFAR10 → SVHN suggest that FedGTST significantly outperforms other relevant baselines, such as FedSR. For example, on the second source-target dataset pair, we improve the accuracy of FedSR by 9.8% and that of FedIIR by 7.6% when the backbone used is LeNet.

BACKGROUND: Pathogenic infections pose a significant threat to global health, affecting millions of people every year and presenting substantial challenges to healthcare systems worldwide. Efficient and timely testing plays a critical role in disease control and transmission prevention. Group testing is a well-established method for reducing the number of tests needed to screen large populations when the disease prevalence is low. However, it does not fully utilize the quantitative information provided by qPCR methods, nor is it able to accommodate a wide range of pathogen loads. RESULTS: To address these issues, we introduce a novel adaptive semi-quantitative group testing (SQGT) scheme to efficiently screen populations via two-stage qPCR testing. The SQGT method quantizes cycle threshold (Ct) values into multiple bins, leveraging the information from the first stage of screening to improve the detection sensitivity. Dynamic Ct threshold adjustments mitigate dilution effects and enhance test accuracy. Comparisons with traditional binary outcome GT methods show that SQGT reduces the number of tests by 24% on the only complete real-world qPCR group testing dataset from Israel, while maintaining a negligible false negative rate. CONCLUSION: In conclusion, our adaptive SQGT approach, utilizing qPCR data and dynamic threshold adjustments, offers a promising solution for efficient population screening. With a reduction in the number of tests and minimal false negatives, SQGT holds potential to enhance disease control and testing strategies on a global scale.

Dictionary learning (DL), implemented via matrix factorization (MF), is commonly used in computational biology to tackle ubiquitous clustering problems. The method is favored due to its conceptual simplicity and relatively low computational complexity. However, DL algorithms produce results that lack interpretability in terms of real biological data. Additionally, they are not optimized for graph-structured data and hence often fail to handle them in a scalable manner. In order to address these limitations, we propose a novel DL algorithm called online convex network dictionary learning (online cvxNDL). Unlike classical DL algorithms, online cvxNDL is implemented via MF and designed to handle extremely large datasets by virtue of its online nature. Importantly, it enables the interpretation of dictionary elements, which serve as cluster representatives, through convex combinations of real measurements. Moreover, the algorithm can be applied to data with a network structure by incorporating specialized subnetwork sampling techniques. To demonstrate the utility of our approach, we apply cvxNDL on 3D-genome RNAPII ChIA-Drop data with the goal of identifying important long-range interaction patterns (long-range dictionary elements). ChIA-Drop probes higher-order interactions, and produces data in the form of hypergraphs whose nodes represent genomic fragments. The hyperedges represent observed physical contacts. Our hypergraph model analysis has the objective of creating an interpretable dictionary of long-range interaction patterns that accurately represent global chromatin physical contact maps. Through the use of dictionary information, one can also associate the contact maps with RNA transcripts and infer cellular functions. To accomplish the task at hand, we focus on RNAPII-enriched ChIA-Drop data from Drosophila Melanogaster S2 cell lines. Our results offer two key insights. First, we demonstrate that online cvxNDL retains the accuracy of classical DL (MF) methods while simultaneously ensuring unique interpretability and scalability. Second, we identify distinct collections of proximal and distal interaction patterns involving chromatin elements shared by related processes across different chromosomes, as well as patterns unique to specific chromosomes. To associate the dictionary elements with biological properties of the corresponding chromatin regions, we employ Gene Ontology (GO) enrichment analysis and perform multiple RNA coexpression studies.

This invited review paper has the aim to acquaint the communication theory community with the emerging topic of molecular data storage. The exposition includes an overview of basic concepts in synthetic and computational biology and a discussion of diverse approaches used to implement such systems. It also describes new problems in communication and coding theory, and discusses some relevant results pertaining to DNA sequence profiles, coded trace reconstruction, coding for DNA punchcard systems and coding for unique reconstruction.

The eXtreme Multi-label Classification (XMC) problem seeks to find relevant labels from an exceptionally large label space. Most of the existing XMC learners focus on the extraction of semantic features from input query text. However, conventional XMC studies usually neglect the side information of instances and labels, which can be of use in many real-world applications such as recommendation systems and e-commerce product search. We propose Predicted Instance Neighborhood Aggregation (PINA), a data augmentation method for the general XMC problem that leverages beneficial side information. Unlike most existing XMC frameworks that treat labels and input instances as featureless indicators and independent entries, PINA extracts information from the label metadata and the correlations among training instances. Extensive experimental results demonstrate the consistent gain of PINA on various XMC tasks compared to the state-of-the-art methods: PINA offers a gain in accuracy compared to standard XR-Transformers on five public benchmark datasets. Moreover, PINA achieves a $\sim 5$% gain in accuracy on the largest dataset LF-AmazonTitles-1.3M.

Motivated by testing for pathogenic diseases we consider a new nonadaptive group testing problem for which: (1) positives occur within a burst, capturing the fact that infected test subjects often come in clusters, and (2) that the test outcomes arise from semiquantitative measurements that provide coarse information about the number of positives in any tested group. Our model generalizes prior work on detecting a single burst with classical group testing [1] to the setting of semiquantitative group testing (SQGT) [2]. Specifically, we study the setting where the burst-length ℓ is known and the semiquantitative tests provide potentially nonuniform estimates on the number of positives in a test group. The estimates represent the index of a quantization bin containing the (exact) total number of positives, for arbitrary thresholds η1,…, ηs. Interestingly, we show that the minimum number of tests needed for burst identification is essentially only a function of the largest threshold ηs. In this context, our main result is an order-optimal test scheme that can recover any burst of length ℓ using roughly $\left\lfloor {\frac{\ell }{{2{\eta _s}}}} \right\rfloor + {\log _{s + 1}}(n)$ measurements. This suggests that a large saturation level ηsis more important than finely quantized information when dealing with bursts. We also provide results for related modeling assumptions and specialized choices of thresholds.

Motivated by applications in polymer-based data storage we introduced the new problem of characterizing the code rate and designing constant-weight binary B2-sequences. Binary B2-sequences are collections of binary strings of length nwith the property that the real-valued sums of all distinct pairs of strings are distinct. In addition to this defining property, constant-weight binary B2-sequences also satisfy the constraint that each string has a fixed, relatively small weight ωthat scales linearly with n. The constant-weight constraint ensures low-cost synthesis and uniform processing of the data readout via tandem mass spectrometers. Our main results include upper bounds on the size of the codes formulated as entropy-optimization problems and constructive lower bounds based on Sidon sequences.

Balanced and swap-robust minimal trades, introduced in [1], are important for studying the balance and stability of server access request protocols under data popularity changes. Constructions of such trades have so far relied on paired sets obtained through iterative combining of smaller sets that have provable stability guarantees, coupled with exhaustive computer search. Currently, there exists a nonnegligible gap between the resulting total dynamic balance discrepancy and the known theoretical lower bound. We present both new upper and lower bounds on the total service requests discrepancy under limited popularity changes. Our constructive near-optimal approach uses a new class of paired graphs whose vertices are two balanced sets with edges (arcs) that capture the balance and potential balance changes induced by limited-magnitude popularity changes (swaps).

The Secretary problem is a classical sequential decision-making question that can be succinctly described as follows: a set of rank-ordered applicants are interviewed sequentially for a single position. Once an applicant is interviewed, an immediate and irrevocable decision is made if the person is to be offered the job or not and only applicants observed so far can be used in the decision process. The problem of interest is to identify the stopping rule that maximizes the probability of hiring the highest-ranked applicant. A multiple-choice version of the Secretary problem, known as the Dowry problem, assumes that one is given a fixed integer budget for the total number of selections allowed to choose the best applicant. It has been solved using tools from dynamic programming and optimal stopping theory. We provide the first combinatorial proof for a related new query-based model for which we are allowed to solicit the response of an expert to determine if an applicant is optimal. Since the selection criteria differ from those of the Dowry problem, we obtain nonidentical expected stopping times.

Graph Neural Networks (GNNs) have proven to be highly effective in solving real-world learning problems that involve graph-structured data. However, GNNs can also inadvertently expose sensitive user information and interactions through their model predictions. To address these privacy concerns, Differential Privacy (DP) protocols are employed to control the trade-off between provable privacy protection and model utility. Applying standard DP approaches to GNNs directly is not advisable due to two main reasons. First, the prediction of node labels, which relies on neighboring node attributes through graph convolutions, can lead to privacy leakage. Second, in practical applications, the privacy requirements for node attributes and graph topology may differ. In the latter setting, existing DP-GNN models fail to provide multigranular trade-offs between graph topology privacy, node attribute privacy, and GNN utility. To address both limitations, we propose a new framework termed Graph Differential Privacy (GDP), specifically tailored to graph learning. GDP ensures both provably private model parameters as well as private predictions. Additionally, we describe a novel unified notion of graph dataset adjacency to analyze the properties of GDP for different levels of graph topology privacy. Our findings reveal that DP-GNNs, which rely on graph convolutions, not only fail to meet the requirements for multigranular graph topology privacy but also necessitate the injection of DP noise that scales at least linearly with the maximum node degree. In contrast, our proposed Differentially Private Decoupled Graph Convolutions (DPDGCs) represent a more flexible and efficient alternative to graph convolutions that still provides the necessary guarantees of GDP. To validate our approach, we conducted extensive experiments on seven node classification benchmarking and illustrative synthetic datasets. The results demonstrate that DPDGCs significantly outperform existing DP-GNNs in terms of privacy-utility trade-offs.

As the demand for user privacy grows, controlled data removal (machine unlearning) is becoming an important feature of machine learning models for data-sensitive Web applications such as social networks and recommender systems. Nevertheless, at this point it is still largely unknown how to perform efficient machine unlearning of graph neural networks (GNNs); this is especially the case when the number of training samples is small, in which case unlearning can seriously compromise the performance of the model. To address this issue, we initiate the study of unlearning the Graph Scattering Transform (GST), a mathematical framework that is efficient, provably stable under feature or graph topology perturbations, and offers graph classification performance comparable to that of GNNs. Our main contribution is the first known nonlinear approximate graph unlearning method based on GSTs. Our second contribution is a theoretical analysis of the computational complexity of the proposed unlearning mechanism, which is hard to replicate for deep neural networks. Our third contribution are extensive simulation results which show that, compared to complete retraining of GNNs after each removal request, the new GST-based approach offers, on average, a 10.38x speed-up and leads to a 2.6% increase in test accuracy during unlearning of 90 out of 100 training graphs from the IMDB dataset (10% training ratio). Our implementation is available online at https://doi.org/10.5281/zenodo.7613150.

Higher-order motif structures and multi-vertex interactions are becoming increasingly important in studies of functionalities and evolution patterns of complex networks. To elucidate the role of higher-order structures in community detection over networks, we introduce a Superimposed Stochastic Block Model (SupSBM). The model is based on a random graph framework in which certain higher-order structures or subgraphs are generated through an independent hyperedge generation process and then replaced with graphs superimposed with edges generated by an inhomogeneous random graph model. Consequently, the model introduces dependencies between edges which allow for capturing more realistic network phenomena, namely strong local clustering in a sparse network, short average path length, and community structure. We then proceed to rigorously analyze the performance of a recently proposed higher-order spectral clustering method on the SupSBM. In particular, we prove non-asymptotic upper bounds on the misclustering error of higher-order spectral community detection for a SupSBM setting in which triangles are superimposed with undirected edges. We assess the model fit of the proposed model and compare it with existing random graph models in terms of observed properties of real network data obtained from diverse domains by sampling networks from the fitted models and a nonparametric network cross-validation approach.

We consider the problem of determining the mutational support and distribution of the SARS-CoV-2 viral genome in the small-sample regime. The mutational support refers to the unknown number of sites that may eventually mutate in the SARS-CoV-2 genome while mutational distribution refers to the distribution of point mutations in the viral genome across a population. The mutational support may be used to assess the virulence of the virus and guide primer selection for real-time RT-PCR testing. Estimating the distribution of mutations in the genome of different subpopulations while accounting for the unseen may also aid in discovering new variants. To estimate the mutational support in the small-sample regime, we use GISAID sequencing data and our state-of-the-art polynomial estimation techniques based on new weighted and regularized Chebyshev approximation methods. For distribution estimation, we adapt the well-known Good-Turing estimator. Our analysis reveals several findings: First, the mutational supports exhibit significant differences in the ORF6 and ORF7a regions (older versus younger patients), ORF1b and ORF10 regions (females versus males) and in almost all ORFs (Asia/Europe/North America). Second, even though the N region of SARS-CoV-2 has a predicted 10% mutational support, mutations fall outside of the primer regions recommended by the CDC.

The problem of reconstructing strings from substring information has found many applications due to its importance in genomic data sequencing and DNA- and polymer-based data storage. One important paradigm requires reconstructing mixtures of strings based on the union of compositions of their prefixes and suffixes, generated by mass spectrometry devices. We describe new coding methods that allow for unique joint reconstruction of subsets of strings selected from a code and provide upper and lower bounds on the asymptotic rate of the underlying codebooks. Our code constructions combine properties of binary$B_{h}$and Dyck strings that can be extended to accommodate missing substrings in the pool. As auxiliary results, we present simple entropy upper bounds for binary$B_{h}$codes and an improved bound for$h=4$, and also describe errors that arise during mass spectrometry.

Polymer-based data-storage platforms use chains of binary synthetic polymers as recording media and read the content via tandem mass spectrometers. For such systems, we propose the first known family of codes that allows for both unique string reconstruction and correction of multiple mass errors. We consider two approaches: The first approach pertains to asymmetric error-correction and it is based on introducing redundancy that scales linearly with the number of errors and logarithmically with the length of the string. The construction allows for the string to be uniquely reconstructed based only on its erroneous substring composition multiset. The key idea behind our unique reconstruction approach is to interleave (shifted) Catalan-Bertrand strings with arbitrary binary strings and “reflect” them so as to force prefixes and suffixes of the same length to have different weights. The asymptotic code rate of the scheme is one, and decoding is accomplished via a simplified version of the Backtracking algorithm used for the Turnpike problem. For symmetric errors, we use a polynomial characterization of the mass information and adapt polynomial evaluation code constructions for this setting. In the process, we develop new efficient decoding algorithms for a constant number of composition errors.

The k-deck problem is concerned with finding the smallest positive integer S(k) such that there exist at least two strings of length S(k) that share the same k-deck, i.e., the multiset of subsequences of length k. We introduce the new problem of gapped k-deck reconstruction: For a given gap parameter s, we seek the smallest positive integer Gs(k) such that there exist at least two distinct strings of length Gs(k) that cannot be distinguished based on a "gapped" set of k-subsequences. The gap constraint requires the elements in the subsequences to be at least s positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same 2-gapped k-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on G2(k). Second, we further improve this bound using the approach by Dudik and Schulman [6].

Trades, introduced by Hedayat [9], are two sets of blocks of elements which may be exchanged (traded) without altering the counts of certain subcollections of elements within their constituent blocks. They are of importance in applications where certain combinations of elements dynamically become prohibited from being placed in the same group of elements, since in this case one can trade the offending blocks with allowed ones. This is particularly the case in distributed storage systems, where due to privacy and other constraints, data of some groups of users cannot be stored together on the same server. We introduce a new class of balanced trades, important for access balancing of servers, and perturbation resilient balanced trades, important for studying the stability of server access frequencies with respect to changes in data popularity. The constructions and bounds on our new trade schemes rely on specialized selections of defining sets in minimal trades and number-theoretic analyses.

The problem of fitting distances by tree-metrics has received significant attention in the theoretical computer science and machine learning communities alike, due to many applications in natural language processing, phylogeny, cancer genomics and a myriad of problem areas that involve hierarchical clustering. Despite the existence of several provably exact algorithms for tree-metric fitting of data that inherently obeys tree-metric constraints, much less is known about how to best fit tree-metrics for data whose structure moderately (or substantially) differs from a tree. For such noisy data, most available algorithms perform poorly and often produce negative edge weights in representative trees. Furthermore, it is currently not known how to choose the most suitable approximation objective for noisy fitting. Our contributions are as follows. First, we propose a new approach to tree-metric denoising (HyperAid) in hyperbolic spaces which transforms the original data into data that is "more'' tree-like, when evaluated in terms of Gromov's δ hyperbolicity. Second, we perform an ablation study involving two choices for the approximation objective, lp norms and the Dasgupta loss. Third, we integrate HyperAid with schemes for enforcing nonnegative edge-weights. As a result, the HyperAid platform outperforms all other existing methods in the literature, including Neighbor Joining (NJ), TreeRep and T-REX, both on synthetic and real-world data. Synthetic data is represented by edge-augmented trees and shortest-distance metrics while the real-world datasets include Zoo, Iris, Glass, Segmentation and SpamBase; on these datasets, the average improvement with respect to NJ is $125.94%$.

Many high-dimensional and large-volume data sets of practical relevance have hierarchical structures induced by trees, graphs or time series. Such data sets are hard to process in Euclidean spaces and one often seeks low-dimensional embeddings in other space forms to perform required learning tasks. For hierarchical data, the space of choice is hyperbolic since it guarantees low-distortion embeddings for tree-like structures. Unfortunately, the geometry of hyperbolic spaces has properties not encountered in Euclidean spaces that pose challenges when trying to rigorously analyze algorithmic solutions. Here, for the first time, we establish a unified framework for learning scalable and simple hyperbolic linear classifiers with provable performance guarantees. The gist of our approach is to focus on Poincaré ball models and formulate the classification problems using tangent space formalisms. Our results include a new hyperbolic and second-order perceptron algorithm as well as an efficient and highly accurate convex optimization setup for hyperbolic support vector machine classifiers. All algorithms provably converge and are highly scalable as they have complexities comparable to those of their Euclidean counterparts. Their performance accuracies on synthetic data sets comprising millions of points, as well as on complex real-world data sets such as single-cell RNA-seq expression measurements, CIFAR10, 1 Fashion-MNIST and mini-ImageNet.

Semiquantitative group testing (SQGT) is a pooling method in which the test outcomes represent bounded intervals for the number of defectives. Alternatively, it may be viewed as an adder channel with quantized outputs. SQGT represents a natural choice for Covid-19 group testing as it allows for a straightforward interpretation of the cycle threshold values produced by polymerase chain reactions (PCR). Prior work on SQGT did not address the need for adaptive testing with a small number of rounds as required in practice. We propose conceptually simple methods for two-round and nonadaptive SQGT that significantly improve upon existing schemes by using ideas on nonbinary measurement matrices based on expander graphs and list-disjunct matrices.

The problem of estimating the support of a distribution is of great importance in many areas of machine learning, computer science and molecular biology. Almost all of the existing work in this area has used perfectly accurate sampling assumptions, which is seldom true in practice. Here we introduce the first known theoretical approach to support estimation in the presence of sampling artifacts, where each sample is assumed to be observed through a Poisson channel that simultaneously captures repetitions and deletions. The proposed estimator is based on regularized weighted Chebyshev approximations, with weights governed by evaluations of Touchard (Bell) polynomials. The supports in the presence of sampling artifacts are calculated via discretized semi-infinite programming methods. The newly proposed estimation approach is tested on synthetic and textual data, as well as on GISAID data for the purpose of estimating the mutational diversity of genes in the SARS-Cov-2 viral genome. For all experiments performed, we observed significant improvements of our integrated method compared to adequately modified known noiseless support estimation methods. A full version of this paper is accessible at: https://arxiv.org/pdf/2006.07999.pdf

The well-known secretary problem in sequential analysis and optimal stopping theory asks one to maximize the probability of finding the optimal candidate in a sequentially examined list under the constraint that accept/reject decisions are made in real-time. The problem is related to practical questions arising in online search, data streaming, daily purchase modeling and multi-arm bandit mechanisms. An extension is the postdoc problem, for which one aims to identify the second-best candidate with highest possible probability of success. We solve the postdoc problem for the nontraditional setting where the candidates are not presented uniformly at random but rather according to permutations drawn from the Mallows distribution. The optimal stopping criteria depend on the choice of the Mallows model parameter$\theta$: For$\theta > 1$, we reject the first$k^{\prime}(\theta)$candidates and then accept the next left-to-right second-best candidate (second-best ranked when comparing with all appeared candidates). This coincides with the optimal strategy for the classical postdoc problem, where the rankings being drawn uniformly at random$(\boldsymbol{i}.\boldsymbol{e}. \theta=1)$. For$0 < \theta\leqslant 1/2$, we reject the first$k^{\prime \prime}(\theta)$candidates and then accept the next left-to-right best candidate; if no selection is made before the last candidate, then the last candidate is accepted. For$1/2 < \theta < 1$, we reject the first$k_{1}(\theta)$candidates and then accept the next left-to-right maximum, or reject the first$k_{2}(\theta)\geqslant k_{1}(\theta)$candidates and then accept the next left-to-right second-maximum, whichever comes first.

The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed “partial clique-expansion” to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein (, 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.

We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over \mathbb Fqland have redundancy r = n-k ≥ qm, 1 ≤ m ≤l, where n and k are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever n=qland r = qm, for all 1 ≤ m ≤l. For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, forl/m is a power of q, and forl= qa, m=qb-1 > 1 ( a ≥ b ≥ 1), and for m ≥l/2 whenlis even and q is a power of two.

Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds.

Generative graph models create instances of graphs that mimic the properties of real-world networks. Generative models are successful at retaining pairwise associations in the underlying networks but often fail to capture higher-order connectivity patterns known as network motifs. Different types of graphs contain different network motifs, an example of which are triangles that often arise in social and biological networks. It is hence vital to capture these higher-order structures to simulate real-world networks accurately. We propose Multi-MotifGAN (MMGAN), a motif-targeted Generative Adversarial Network (GAN) that generalizes the benchmark NetGAN approach. The generalization consists of combining multiple biased random walks, each of which captures a different motif structure. MMGAN outperforms NetGAN at creating new graphs that accurately reflect the network motif statistics of input graphs such as Citeseer, Cora and Facebook.

ABSTRACT The main obstacles for the practical deployment of DNA-based data storage platforms are the prohibitively high cost of synthetic DNA and the large number of errors introduced during synthesis. In particular, synthetic DNA products contain both individual oligo (fragment) symbol errors as well as missing DNA oligo errors, with rates that exceed those of modern storage systems by orders of magnitude. These errors can be corrected either through the use of a large number of redundant oligos or through cycles of writing, reading, and rewriting of information that eliminate the errors. Both approaches add to the overall storage cost and are hence undesirable. Here we propose the first method for storing quantized images in DNA that uses signal processing and machine learning techniques to deal with error and cost issues without resorting to the use of redundant oligos or rewriting. Our methods rely on decoupling the RGB channels of images, performing specialized quantization and compression on the individual color channels, and using new discoloration detection and image inpainting techniques. We demonstrate the performance of our approach experimentally on a collection of movie posters stored in DNA.

Motivated by applications in topological DNA-based data storage, we introduce and study a novel setting of Non-Adaptive Group Testing (NAGT) with runlength constraints on the columns of the test matrix, in the sense that any two 1's must be separated by a run of at least d 0's. We describe and analyze a probabilistic construction of a runlength-constrained scheme in the zero-error and vanishing error settings, and show that the number of tests required by this construction is optimal up to logarithmic factors in the runlength constraint d and the number of defectives k in both cases. Our results reveal that runlength-constrained NAGT is not more restrictive than unconstrained NAGT when d = O(k), and that for almost all choices of d and k it is not more restrictive than NAGT with a column Hamming weight constraint only.

We consider the problem of correcting mass readout errors in information encoded in binary polymer strings. Our work builds on results for string reconstruction problems using composition multisets [1] and the unique string reconstruction framework proposed in [2]. Binary polymer-based data storage systems [3] operate by designing two molecules of significantly different masses to represent the symbols {0,1} and perform readouts through noisy tandem mass spectrometry. Tandem mass spectrometers fragment the strings to be read into shorter substrings and only report their masses, often with errors due to imprecise ionization. Modeling the fragmentation process output in terms of composition multisets allows for designing asymptotically optimal codes capable of unique reconstruction and the correction of a single mass error [2] through the use of derivatives of Catalan paths. Nevertheless, no solutions for multiple-mass error-corrections are currently known. Our work addresses this issue by describing the first multiple-error correction codes that use the polynomial factorization approach for the Turnpike problem [4] and the related factorization described in [1]. Adding Reed-Solomon type coding redundancy into the corresponding polynomials allows for correcting t mass errors in polynomial time using ${\mathcal{O}}\left( {{t^2}\log k} \right)$ redundant bits, where k is the information string length. The redundancy can be improved to ${\mathcal{O}}(t + \log k)$. However, no decoding algorithm that runs polynomial-time in both t and n for this scheme are currently known, where n is the length of the coded string.

The problem of string reconstruction from substring information has found many applications due to its relevance in DNA- and polymer-based data storage. One practically important and challenging paradigm requires reconstructing mixtures of strings based on the union of compositions of their prefixes and suffixes, generated by mass spectrometry readouts. We describe new coding methods that allow for unique joint reconstruction of subsets of strings selected from a code and provide matching upper and lower bounds on the asymptotic rate of the underlying codebooks. Under certain mild constraints on the problem parameters, one can show that the largest possible rate of a codebook that allows for all subcollections of less than or equal to h codestrings to be uniquely reconstructable from the prefix-suffix information equals 1/h.

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits close ties to decomposable submodular function minimization (DSFM) yet is much more challenging to solve. We approach the problem via a new dual strategy and formulate an objective that can be optimized through a number of double-loop algorithms. The outer-loop uses either random coordinate descent (RCD) or alternative projection (AP) methods, for both of which we prove linear convergence rates. The inner-loop computes projections onto cones generated by base polytopes of the submodular functions via the modified min-norm-point or Frank-Wolfe algorithms. We also describe two new applications of QDSFM: hypergraph-adapted PageRank and semi-supervised learning. The proposed hypergraph-based PageRank algorithm can be used for local hypergraph partitioning and comes with provable performance guarantees. For hypergraph-adapted semi-supervised learning, we provide numerical experiments demonstrating the efficiency of our QDSFM solvers and their significant improvements on prediction accuracy when compared to state-of-the-art methods.

We address the new problem of designing large families of subsets of a common labeled ground set that simultaneously have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the subsets is less than or equal to one. Our results include an upper bound on the size of such families, and constructions based on transversal designs, packings, and new forms of Latin rectangles. The constructions jointly optimize the size of the family of sets and the labeling scheme and achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The intersecting sets discrepancy problem is motivated by emerging applications in coding for molecular data storage.

Motivated by applications in social and biological network analysis we introduce a new form of agnostic clustering termed motif correlation clustering, which aims to minimize the cost of clustering errors associated with both edges and higher-order network structures. The problem may be succinctly described as follows: Given a complete graph $G$ , partition the vertices of the graph so that certain predetermined “important” subgraphs mostly lie within the same cluster, while “less relevant” subgraphs are allowed to lie across clusters. Our contributions are as follows: We first introduce several variants of motif correlation clustering and then show that these clustering problems are NP-hard. We then proceed to describe polynomial-time clustering algorithms that provide constant approximation guarantees for the problems at hand. Despite following the frequently used LP relaxation and rounding procedure, the algorithms involve a sophisticated and carefully designed neighborhood growing step that combines information about both edges and motifs. We conclude with several examples illustrating the performance of the developed algorithms on synthetic and real networks.

We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.

Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.

Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of coded trace reconstruction, the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called traces) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i. d. deletions and constant deletion probability. Our work is a first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i. d. deletions, and begin by analyzing marker-based code-constructions coupled with worst-case trace reconstruction algorithms. Then, we show how a more careful design of the code allows us to exploit ideas from average-case trace reconstruction to reduce the number of traces required with the same redundancy.

Motivated by polymer-based data-storage platforms that use chains of binary synthetic polymers as the recording media and read the content via tandem mass spectrometers, we propose a new family of codes that allows for unique string reconstruction and correction of one mass error. Our approach is based on introducing redundancy that scales logarithmically with the length of the string and allows for the string to be uniquely reconstructed based only on its erroneous substring composition multiset. The key idea behind our unique reconstruction approach is to interleave Catalan-type paths with arbitrary binary strings and “reflect” them so as to allow prefixes and suffixes of the same length to have different weights. For error correction, we add a constant number of bits that provides information about the weights of reflected pairs of bits and hence enable recovery from a single mass error. The asymptotic code rate of the scheme is one, and decoding is accomplished via a simplified version of the backtracking algorithm used for the Turnpike problem.

Landing probabilities (LP) of random walks (RW) over graphs encode rich information regarding graph topology. Generalized PageRanks (GPR), which represent weighted sums of LPs of RWs, utilize the discriminative power of LP features to enable many graph-based learning studies. Previous work in the area has mostly focused on evaluating suitable weights for GPRs, and only a few studies so far have attempted to derive the optimal weights of GPRs for a given application. We take a fundamental step forward in this direction by using random graph models to better our understanding of the behavior of GPRs. In this context, we provide a rigorous non-asymptotic analysis for the convergence of LPs and GPRs to their mean-field values on edge-independent random graphs. Although our theoretical results apply to many problem settings, we focus on the task of seed-expansion community detection over stochastic block models. There, we find that the predictive power of LPs decreases significantly slower than previously reported based on asymptotic findings. Given this result, we propose a new GPR, termed Inverse PR (IPR), with LP weights that increase for the initial few steps of the walks. Extensive experiments on both synthetic and real, large-scale networks illustrate the superiority of IPR compared to other GPRs for seeded community detection.

Matrix factorization (MF) is a versatile learning method that has found wide applications in various data-driven disciplines. Still, many MF algorithms do not adequately scale with the size of available datasets and/or lack interpretability. To improve the computational efficiency of the method, an online (streaming) MF algorithm was proposed in Mairal et al., 2010. To enable data interpretability, a constrained version of MF, termed convex MF, was introduced in Ding et al., 2010. In the latter work, the basis vectors are required to lie in the convex hull of the data samples, thereby ensuring that every basis can be interpreted as a weighted combination of data samples. No current algorithmic solutions for online convex MF are known as it is challenging to find adequate convex bases without having access to the complete dataset. We address both problems by proposing the first online convex MF algorithm that maintains a collection of constant-size sets of representative data samples needed for interpreting each of the basis (Ding et al., 2010) and has the same almost sure convergence guarantees as the online learning algorithm of Mairal et al., 2010. Our proof techniques combine random coordinate descent algorithms with specialized quasi-martingale convergence analysis. Experiments on synthetic and real world datasets show significant computational savings of the proposed online convex MF method compared to classical convex MF. Since the proposed method maintains small representative sets of data samples needed for convex interpretations, it is related to a body of work in theoretical computer science, pertaining to generating point sets (Blum et al., 2016), and in computer vision, pertaining to archetypal analysis (Mei et al., 2018). Nevertheless, it differs from these lines of work both in terms of the objective and algorithmic implementations.

We introduce a general class of codes which includes several well-known classes of deletion/insertion correcting codes as special cases. For example, the Helberg code, the Levenshtein code, the Varshamov-Tenengolts code, and most variants of these codes including most of those which have been recently used in studying DNA-based data storage systems are all special cases of our code. Then, using a number theoretic method, we give an explicit formula for the weight enumerator of our code which in turn gives explicit formulas for the weight enumerators and for the sizes of all the aforementioned codes. We also obtain the size of the shifted Varshamov-Tenengolts code. Another application which automatically follows from our result is an explicit formula for the number of binary solutions of an arbitrary linear congruence which, to the best of our knowledge, is the first result of its kind in the literature and might be also of independent interest. Our general result might have more applications/implications in information theory, computer science, and mathematics.

The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem ofcoded string reconstructionfrom multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termedrepeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. We also consider extensions of the problem to noisy settings in which substrings are compromised by burst and random errors. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.

We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in cluster- ing applications in which higher-order structures carry relevant information. For such hypergraphs, we define the notion of p-Laplacians and derive corresponding nodal domain theorems and k-way Cheeger inequalities. We conclude with the description of algorithms for computing the spectra of 1- and 2-Laplacians that constitute the basis of new spectral hypergraph clustering methods.

We derive an explicit expression for the weight enumerator of a general class of codes which includes several classes of deletion correcting codes, such as Helberg, Levenshtein, and Shifted Varshamov- Tenengolts codes, as special cases. Our approach generalizes the number-theoretic methods previously used for evaluating the size of single deletion correcting codes, and also leads to a new explicit formula for the number of binary solutions of an arbitrary linear congruence which might be also of independent interest.

The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem of coded string reconstruction from multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termed repeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.

We consider the problem of approximate $K$-means clustering with outliers and side information provided by same-cluster queries and possibly noisy answers. Our solution shows that, under some mild assumptions on the smallest cluster size, one can obtain an $(1+\epsilon)$-approximation for the optimal potential with probability at least $1-\delta$, where $\epsilon>0$ and $\delta\in(0,1)$, using an expected number of $O(\frac{K^3}{\epsilon \delta})$ noiseless same-cluster queries and comparison-based clustering of complexity $O(ndK + \frac{K^3}{\epsilon \delta})$; here, $n$ denotes the number of points and $d$ the dimension of space. Compared to a handful of other known approaches that perform importance sampling to account for small cluster sizes, the proposed query technique reduces the number of queries by a factor of roughly $O(\frac{K^6}{\epsilon^3})$, at the cost of possibly missing very small clusters. We extend this settings to the case where some queries to the oracle produce erroneous information, and where certain points, termed outliers, do not belong to any clusters. Our proof techniques differ from previous methods used for $K$-means clustering analysis, as they rely on estimating the sizes of the clusters and the number of points needed for accurate centroid estimation and subsequent nontrivial generalizations of the double Dixie cup problem. We illustrate the performance of the proposed algorithm both on synthetic and real datasets, including MNIST and CIFAR $10$.

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization. The problem is closely related to decomposable submodular function minimization and arises in many learning on graphs and hypergraphs settings, such as graph-based semi-supervised learning and PageRank. We approach the problem via a new dual strategy and describe an objective that may be optimized via random coordinate descent (RCD) methods and projections onto cones. We also establish the linear convergence rate of the RCD algorithm and develop efficient projection algorithms with provable performance guarantees. Numerical experiments in semi-supervised learning on hypergraphs confirm the efficiency of the proposed algorithm and demonstrate the significant improvements in prediction accuracy with respect to state-of-the-art methods.

We introduce a new approach to decomposable submodular function minimization (DSFM) that exploits incidence relations. Incidence relations describe which variables effectively influence the component functions, and when properly utilized, they allow for improving the convergence rates of DSFM solvers. Our main results include the precise parametrization of the DSFM problem based on incidence relations, the development of new scalable alternative projections and parallel coordinate descent methods and an accompanying rigorous analysis of their convergence rates.

Motivation: DNA methylation is one of the most important epigenetic mechanisms in cells that exhibits a significant role in controlling gene expressions. Abnormal methylation patterns have been associated with cancer, imprinting disorders and repeat-instability diseases. As inexpensive bisulfite sequencing approaches have led to significant efforts in acquiring methylation data, problems of data storage and management have become increasingly important. The de facto compression method for methylation data is gzip, which is a general purpose compression algorithm that does not cater to the special format of methylation files. We propose METHCOMP, a new compression scheme tailor-made for bedMethyl files, which supports random access. Results: We tested the METHCOMP algorithm on 24 bedMethyl files retrieved from four randomly selected ENCODE assays. Our findings reveal that METHCOMP offers an average compression ratio improvement over gzip of up to 7.5x. As an example, METHCOMP compresses a 48 GB file to only 0.9 GB, which corresponds to a 98% reduction in size. Availability and implementation: METHCOMP is freely available at https://github.com/jianhao2016/METHCOMP. Supplementary information: Supplementary data are available at Bioinformatics online.

Motivation: Chromatin immunoprecipitation sequencing (ChIP-seq) experiments are inexpensive and time-efficient, and result in massive datasets that introduce significant storage and maintenance challenges. To address the resulting Big Data problems, we propose a lossless and lossy compression framework specifically designed for ChIP-seq Wig data, termed ChIPWig. ChIPWig enables random access, summary statistics lookups and it is based on the asymptotic theory of optimal point density design for nonuniform quantizers. Results: We tested the ChIPWig compressor on 10 ChIP-seq datasets generated by the ENCODE consortium. On average, lossless ChIPWig reduced the file sizes to merely 6% of the original, and offered 6-fold compression rate improvement compared to bigWig. The lossy feature further reduced file sizes 2-fold compared to the lossless mode, with little or no effects on peak calling and motif discovery using specialized NarrowPeaks methods. The compression and decompression speed rates are of the order of 0.2 sec/MB using general purpose computers. Availability and implementation: The source code and binaries are freely available for download at https://github.com/vidarmehr/ChIPWig-v2, implemented in C ++. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Many code families such as low-density parity-check codes, fractional repetition codes, batch codes, and private information retrieval codes with low storage overhead rely on the use of combinatorial block designs or derivatives thereof. In the context of distributed storage applications, one is often faced with system design issues that impose additional constraints on the coding schemes and therefore on the underlying block designs. Here, we address one such problem, pertaining to server access frequency balancing, by introducing a new form of Steiner systems, termed MaxMinSum Steiner systems. MaxMinSum Steiner systems are characterized by the property that the minimum value of the sum of points (elements) within a block is maximized or that the minimum sum of block indices containing some fixed point is maximized. We show that proper relabelings of points in the Bose and Skolem constructions for Steiner triple systems lead to optimal MaxMin values for the sums of interest; for the duals of the designs, we exhibit block labelings that are within a $3/4$ multiplicative factor from the optimum.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions, and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.

We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph G whose edges are labeled with + or -, we wish to partition the graph into clusters while trying to avoid errors: + edges between clusters or - edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provides a rounding algorithm which converts "fractional clusterings" into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes.

We propose a novel rank aggregation method based on converting permutations into their corresponding Lehmer codes or other subdiagonal images. Lehmer codes, also known as inversion vectors, are vector representations of permutations in which each coordinate can take values not restricted by the values of other coordinates. This transformation allows for decoupling of the coordinates and for performing aggregation via simple scalar median or mode computations. We present simulation results illustrating the performance of this completely parallelizable approach and analytically prove that both the mode and median aggregation procedure recover the correct centroid aggregate with small sample complexity when the permutations are drawn according to the well-known Mallows models. The proposed Lehmer code approach may also be used on partial rankings, with similar performance guarantees.

Motivated by applications in social network community analysis, we introduce a new clustering paradigm termed motif clustering. Unlike classical clustering, motif clustering aims to minimize the number of clustering errors associated with both edges and certain higher order graph structures (motifs) that represent “atomic units” of social organizations. Our contributions are two-fold: We first introduce motif correlation clustering, in which the goal is to agnostically partition the vertices of a weighted complete graph so that certain predetermined “important” social subgraphs mostly lie within the same cluster, while “less relevant” social subgraphs are allowed to lie across clusters. We then proceed to introduce the notion of motif covers, in which the goal is to cover the vertices of motifs via the smallest number of (near) cliques in the graph. Motif cover algorithms provide a natural solution for overlapping clustering and they also play an important role in latent feature inference of networks. For both motif correlation clustering and its extension introduced via the covering problem, we provide hardness results, algorithmic solutions and community detection results for two well-studied social networks.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. We extend their trace collection technique to cope with two erasures.

Reed-Solomon codes have found many applications in practical storage systems, but were until recently considered unsuitable for distributed storage applications due to the widely-held belief that they have poor repair bandwidth. The work of Guruswami and Wootters (STOC'16) has shown that one can actually perform bandwidth-efficient linear repair with Reed-Solomon codes: When the codes are over the field Fqt and the number of parities r ≥ qs, where (t - s) divides t, there exists a linear scheme that achieves a repair bandwidth of (n - 1)(t - s) logg q bits. We extend this result by showing the existence of such a linear repair scheme for every 1 ≤ stand r = qs. Additionally, we improve the lower bound on the repair bandwidth for Reed-Solomon codes, also established in the work of Guruswami and Wootters.

We introduce a new variant of the k-deck problem, which in its traditional formulation asks for determining the smallest k that allows one to reconstruct any binary sequence of length n from the multiset of its k-length subsequences. In our version of the problem, termed the hybrid k-deck problem, one is given a certain number of special subsequences of the sequence of length n - t, t > 0, and the question of interest is to determine the smallest value of k such that the k-deck, along with the subsequences, allows for reconstructing the original sequence in an error-free manner. We first consider the case that one is given a single subsequence of the sequence of length n - t, obtained by deleting zeros only, and seek the value of k that allows for hybrid reconstruction. We prove that in this case, k ϵ [log t + 2, min{t + 1, O(√n)}]. We then proceed to extend the single-subsequence setup to the case where one is given M subsequences of length n - t obtained by deleting zeroes only. In this case, we first aggregate the asymmetric traces and then invoke the single-trace results. The analysis and problem at hand are motivated by nanopore sequencing problems for DNA-based data storage.

We introduce a new family of minmax rank aggregation problems under two distance measures, the Kendall τ and the Spearman footrule. As the problems are NP-hard, we proceed to describe a number of constant-approximation algorithms for solving them. We conclude with illustrative applications of the aggregation methods on the Mallows model and genomic data.

Hypergraph partitioning is an important problem in machine learning, computer vision and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of partitioning hyperedges across clusters. Algorithmic solutions based on this approach assume that different partitions of a hyperedge incur the same cost. However, this assumption fails to leverage the fact that different subsets of vertices within the same hyperedge may have different structural importance. We hence propose a new hypergraph clustering technique, termed inhomogeneous hypergraph partitioning, which assigns different costs to different hyperedge cuts. We prove that inhomogeneous partitioning produces a quadratic approximation to the optimal solution if the inhomogeneous costs satisfy submodularity constraints. Moreover, we demonstrate that inhomogenous partitioning offers significant performance improvements in applications such as structure learning of rankings, subspace segmentation and motif clustering.

We introduce a new family of codes, termed asymmetric Lee distance (ALD) codes, designed to correct errors arising in DNA-based storage systems and systems with parallel string transmission protocols. ALD codes are defined over a quaternary alphabet and analyzed in this particular setting, but the derived results hold for other alphabet sizes as well. Our technical contributions are twofold. First, we derive upper bounds on the size of the codes under the ALD metric based on linear programming techniques. Second, we propose a number of code constructions, which imply lower bounds.

We propose a new latent Boolean feature model for complex networks that capture different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the Boolean intersection representation of a graph, which generalizes the notion of an intersection representation. We mostly focus on one form of Boolean intersection, termed cointersection, and describe how to use this representation to deduce node feature sets and their communities. We derive several general bounds on the minimum number of features used in cointersection representations and discuss graph families for which exact cointersection characterizations are possible. Our results also include algorithms for finding optimal and approximate cointersection representations of a graph.

We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph G whose edges are labeled with + or -, we wish to partition the graph into clusters while trying to avoid errors: + edges between clusters or - edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provide a rounding algorithm which converts “fractional clusterings” into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions.

We propose a new latent Boolean feature model for complex networks that captures different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the co-intersection representation of a graph, which generalizes the notion of an intersection representation. We describe how to use co-intersection representations to deduce node feature sets and their communities, and proceed to derive several general bounds on the minimum number of features used in co-intersection representations. We also discuss graph families for which exact co-intersection characterizations are possible, and describe algorithms for computing co-intersection numbers and assignments.

Motivated by charge balancing constraints for rank modulation schemes, we introduce the notion of balanced permutations and derive the capacity of balanced permutation codes. We also describe simple interleaving methods for permutation code constructions and show that they approach capacity.

We introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which also allows for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. Bounds on the size of the codes and accompanying decoding algorithms are presented as well.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based storage systems and synchronization protocols. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. In addition, WMU sequences used in DNA-based storage systems are required to have balanced compositions of symbols and to be at large mutual Hamming distance from each other. We present a number of constructions for balanced, error-correcting WMU codes using Dyck paths, Knuth's balancing principle, prefix synchronized and cyclic codes.

Threshold graphs are recursive deterministic network models that capture properties of certain social and economic interactions. One drawback of these graph families is that they they have limited constrained generative attachment rules. To mitigate this problem, we introduce a new class of graphs termed Doubly Threshold (DT) graphs which may be succinctly described through vertex weights that govern the existence of edges via two inequalities. One inequality imposes the constraint that the sum of weights of adjacent vertices has to exceed a specified threshold. The second inequality ensures that adjacent vertices have a bounded difference of their weights. We provide a succinct characterization and decomposition of DT graphs and analyze their forbidden induced subgraphs which we compare to those of known social networks. We also present a method for performing vertex weight assignments on DT graphs that satisfy the defining constraints.

Motivation: Cancer genomes exhibit a large number of different alterations that affect many genes in a diverse manner. An improved understanding of the generative mechanisms behind the mutation rules and their influence on gene community behavior is of great importance for the study of cancer. Results: To expand our capability to analyze combinatorial patterns of cancer alterations, we developed a rigorous methodology for cancer mutation pattern discovery based on a new, constrained form of correlation clustering. Our new algorithm, named C3 (Cancer Correlation Clustering), leverages mutual exclusivity of mutations, patient coverage and driver network concentration principles. To test C3, we performed a detailed analysis on TCGA breast cancer and glioblastoma data and showed that our algorithm outperforms the state-of-the-art CoMEt method in terms of discovering mutually exclusive gene modules and identifying biologically relevant driver genes. The proposed agnostic clustering method represents a unique tool for efficient and reliable identification of mutation patterns and driver pathways in large-scale cancer genomics studies, and it may also be used for other clustering problems on biological graphs. Availability and Implementation: The source code for the C3 method can be found at https://github.com/jackhou2/C3 Contacts: [email protected] or [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

CONTRIBUTIONS: We developed a new lossless compression method for WIG data, named smallWig, offering the best known compression rates for RNA-seq data and featuring random access functionalities that enable visualization, summary statistics analysis and fast queries from the compressed files. Our approach results in order of magnitude improvements compared with bigWig and ensures compression rates only a fraction of those produced by cWig. The key features of the smallWig algorithm are statistical data analysis and a combination of source coding methods that ensure high flexibility and make the algorithm suitable for different applications. Furthermore, for general-purpose file compression, the compression rate of smallWig approaches the empirical entropy of the tested WIG data. For compression with random query features, smallWig uses a simple block-based compression scheme that introduces only a minor overhead in the compression rate. For archival or storage space-sensitive applications, the method relies on context mixing techniques that lead to further improvements of the compression rate. Implementations of smallWig can be executed in parallel on different sets of chromosomes using multiple processors, thereby enabling desirable scaling for future transcriptome Big Data platforms. MOTIVATION: The development of next-generation sequencing technologies has led to a dramatic decrease in the cost of DNA/RNA sequencing and expression profiling. RNA-seq has emerged as an important and inexpensive technology that provides information about whole transcriptomes of various species and organisms, as well as different organs and cellular communities. The vast volume of data generated by RNA-seq experiments has significantly increased data storage costs and communication bandwidth requirements. Current compression tools for RNA-seq data such as bigWig and cWig either use general-purpose compressors (gzip) or suboptimal compression schemes that leave significant room for improvement. To substantiate this claim, we performed a statistical analysis of expression data in different transform domains and developed accompanying entropy coding methods that bridge the gap between theoretical and practical WIG file compression rates. RESULTS: We tested different variants of the smallWig compression algorithm on a number of integer-and real- (floating point) valued RNA-seq WIG files generated by the ENCODE project. The results reveal that, on average, smallWig offers 18-fold compression rate improvements, up to 2.5-fold compression time improvements, and 1.5-fold decompression time improvements when compared with bigWig. On the tested files, the memory usage of the algorithm never exceeded 90 KB. When more elaborate context mixing compressors were used within smallWig, the obtained compression rates were as much as 23 times better than those of bigWig. For smallWig used in the random query mode, which also supports retrieval of the summary statistics, an overhead in the compression rate of roughly 3-17% was introduced depending on the chosen system parameters. An increase in encoding and decoding time of 30% and 55% represents an additional performance loss caused by enabling random data access. We also implemented smallWig using multi-processor programming. This parallelization feature decreases the encoding delay 2-3.4 times compared with that of a single-processor implementation, with the number of processors used ranging from 2 to 8; in the same parameter regime, the decoding delay decreased 2-5.2 times. AVAILABILITY AND IMPLEMENTATION: The smallWig software can be downloaded from: http://stanford.edu/~zhiyingw/smallWig/smallwig.html, http://publish.illinois.edu/milenkovic/, http://web.stanford.edu/~tsachy/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Metagenomics is a genomics research discipline devoted to the study of microbial communities in environmental samples and human and animal organs and tissues. Sequenced metagenomic samples usually comprise reads from a large number of different bacterial communities and hence tend to result in large file sizes, typically ranging between 1-10 GB. This leads to challenges in analyzing, transferring and storing metagenomic data. In order to overcome these data processing issues, we introduce MetaCRAM, the first de novo, parallelized software suite specialized for FASTA and FASTQ format metagenomic read processing and lossless compression. RESULTS: MetaCRAM integrates algorithms for taxonomy identification and assembly, and introduces parallel execution methods; furthermore, it enables genome reference selection and CRAM based compression. MetaCRAM also uses novel reference-based compression methods designed through extensive studies of integer compression techniques and through fitting of empirical distributions of metagenomic read-reference positions. MetaCRAM is a lossless method compatible with standard CRAM formats, and it allows for fast selection of relevant files in the compressed domain via maintenance of taxonomy information. The performance of MetaCRAM as a stand-alone compression platform was evaluated on various metagenomic samples from the NCBI Sequence Read Archive, suggesting 2- to 4-fold compression ratio improvements compared to gzip. On average, the compressed file sizes were 2-13 percent of the original raw metagenomic file sizes. CONCLUSIONS: We described the first architecture for reference-based, lossless compression of metagenomic data. The compression scheme proposed offers significantly improved compression ratios as compared to off-the-shelf methods such as zip programs. Furthermore, it enables running different components in parallel and it provides the user with taxonomic and assembly information generated during execution of the compression pipeline. AVAILABILITY: The MetaCRAM software is freely available at http://web.engr.illinois.edu/~mkim158/metacram.html. The website also contains a README file and other relevant instructions for running the code. Note that to run the code one needs a minimum of 16 GB of RAM. In addition, virtual box is set up on a 4GB RAM machine for users to run a simple demonstration.

We analyze a new group-testing scheme, termed semi-quantitative group testing, which may be viewed as a concatenation of an adder channel and a discrete quantizer. Our focus is on non-uniform quantizers with arbitrary thresholds. For the most general semi-quantitative group-testing model, we define three new families of sequences capturing the constraints on the code design imposed by the choice of the thresholds. The sequences represent extensions and generalizations of Bhand certain types of super-increasing and lexicographically ordered sequences, and they lead to code structures amenable for efficient recursive decoding. We describe the decoding methods and provide an accompanying computational complexity and performance analysis.

We consider the problem of storing and retrieving information from synthetic DNA media. We introduce the DNA storage channel and model the read process through the use of profile vectors. We provide an asymptotic analysis of the number of profile vectors and propose new asymmetric coding techniques to combat the effects of synthesis and sequencing noise. Furthermore, we construct two families of codes for this new channel model.

We consider the problem of synchronizing coded data in distributed storage networks undergoing insertion and deletion edits. We present modifications of distributed storage codes that allow updates in the parity-check values to be performed with one round of communication at low bit rates and with small storage overhead. Our main contributions are novel protocols for synchronizing frequently updated and semi-static data based on functional intermediary coding involving permutation and Vandermonde matrices.

We consider a new family of asymmetric Lee codes that arise in the design and implementation of DNA-based storage systems and systems with parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions are two-fold. First, we derive upper bounds on the size of the codes under the asymmetric Lee distance measure based on linear programming techniques. Second, we propose code constructions which imply lower bounds.

We consider the problem of storing information on synthetic DNA media and associated coding paradigms. The focal question of our analysis it how to construct and enumerate sequences that may be discriminated based on their collection of substrings observed through two types of noisy sequencing channels. In particular, we consider DNA sequences with balanced GC content, needed for chemical stability and desirable hybridization properties. We show that restricted de Bruijn graphs and Ehrhart theory for rational polytopes provide a suitable framework for studying such combinatorial questions.

We consider the problem of synchronizing data in distributed storage networks under edits that include deletions and insertions. We present modifications of codes on distributed storage systems that allow updates in the parity-check values to be performed with one round of communication at low bit rates and a small storage overhead. Our main contributions are novel protocols for synchronizing both frequently updated and semi-static data, and protocols for data deduplication applications, based on intermediary coding using permutation and Vandermonde matrices.

We continue our study of a new family of asymmetric Lee codes that arise in the design and implementation of emerging DNA-based storage systems and systems which use parallel string transmission protocols. The codewords are defined over a quaternary alphabet, although the results carry over to other alphabet sizes, and have symbol distances dictated by their underlying binary representation. Our contributions include deriving new bounds for the size of the largest code in this metric based on Delsarte-like linear programming methods and describing new constructions for non-linear asymmetric Lee codes.

We consider the problem of assembling a sequence based on a collection of its substrings observed through a noisy channel. This problem of reconstructing sequences from traces was first investigated in the noiseless setting under the name of “Markov type” analysis. Here, we explain the connection between the problem and the problem of DNA synthesis and sequencing, and introduce the notion of a DNA storage channel. We analyze the number of sequence equivalence classes under the channel mapping and propose new asymmetric coding techniques to combat the effects of synthesis noise. In our analysis, we make use of Ehrhart theory for rational polytopes.

UNLABELLED: Gene prioritization refers to a family of computational techniques for inferring disease genes through a set of training genes and carefully chosen similarity criteria. Test genes are scored based on their average similarity to the training set, and the rankings of genes under various similarity criteria are aggregated via statistical methods. The contributions of our work are threefold: (i) first, based on the realization that there is no unique way to define an optimal aggregate for rankings, we investigate the predictive quality of a number of new aggregation methods and known fusion techniques from machine learning and social choice theory. Within this context, we quantify the influence of the number of training genes and similarity criteria on the diagnostic quality of the aggregate and perform in-depth cross-validation studies; (ii) second, we propose a new approach to genomic data aggregation, termed HyDRA (Hybrid Distance-score Rank Aggregation), which combines the advantages of score-based and combinatorial aggregation techniques. We also propose incorporating a new top-versus-bottom (TvB) weighting feature into the hybrid schemes. The TvB feature ensures that aggregates are more reliable at the top of the list, rather than at the bottom, since only top candidates are tested experimentally; (iii) third, we propose an iterative procedure for gene discovery that operates via successful augmentation of the set of training genes by genes discovered in previous rounds, checked for consistency. MOTIVATION: Fundamental results from social choice theory, political and computer sciences, and statistics have shown that there exists no consistent, fair and unique way to aggregate rankings. Instead, one has to decide on an aggregation approach using predefined set of desirable properties for the aggregate. The aggregation methods fall into two categories, score- and distance-based approaches, each of which has its own drawbacks and advantages. This work is motivated by the observation that merging these two techniques in a computationally efficient manner, and by incorporating additional constraints, one can ensure that the predictive quality of the resulting aggregation algorithm is very high. RESULTS: We tested HyDRA on a number of gene sets, including autism, breast cancer, colorectal cancer, endometriosis, ischaemic stroke, leukemia, lymphoma and osteoarthritis. Furthermore, we performed iterative gene discovery for glioblastoma, meningioma and breast cancer, using a sequentially augmented list of training genes related to the Turcot syndrome, Li-Fraumeni condition and other diseases. The methods outperform state-of-the-art software tools such as ToppGene and Endeavour. Despite this finding, we recommend as best practice to take the union of top-ranked items produced by different methods for the final aggregated list. AVAILABILITY AND IMPLEMENTATION: The HyDRA software may be downloaded from: http://web.engr.illinois.edu/∼mkim158/HyDRA.zip. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Motivated by mass-spectrometry protein sequencing, we consider the problem of reconstructing a string from the multisets of its substring composition. We show that all strings of length 7, one less than a prime and one less than twice a prime, can be reconstructed uniquely up to reversal. For all other lengths, we show that unique reconstruction is not always possible and provide sometimes-tight bounds on the largest number of strings with given substring compositions. The lower bounds are derived by combinatorial arguments, while the upper bounds follow from algebraic approaches that lead to precise characterizations of the sets of strings with the same substring compositions in terms of the factorization properties of bivariate polynomials. Using results on the transience of multidimensional random walks, we also provide a reconstruction algorithm that recovers random strings over alphabets of size $\ge4$ from their substring compositions in optimal near-quadratic time. The problem considered is related to the well-known turnpike problem, and its solution may hence shed light on this longstanding open problem as well.

We introduce a novel probabilistic group testing framework, termed Poisson group testing, in which the number of defectives follows a right-truncated Poisson distribution. The Poisson model applies to a number of biological testing scenarios, where the subjects are assumed to be ordered based on their arrival times and where the probability of being defective decreases with time. Our main result is an information-theoretic upper bound on the minimum number of tests required to achieve an average probability of detection error asymptotically converging to zero.

Motivated by the problem of deducing the structure of proteins using mass-spectrometry, we study the reconstruction of a string from the multiset of its substring compositions. We specialize the backtracking algorithm used for the more general turnpike problem for string reconstruction. Employing well known results about transience of random walks in ≥ 3 dimensions, we show that the algorithm reconstructs random strings over alphabet size ≥ 4 with high probability in near-optimal quadratic time.

We present a new family of codes for non-uniformly quantized adder channels. Quantized adder channels are generalizations of group testing models, which were studied under the name of semi-quantitative group testing. We describe non-binary group testing schemes in which the test matrices are generated by concatenating scaled disjunct codebooks, with the scaling parameters determined through lexicographical ordering constraints. In addition, we propose simple iterative decoding methods for one class of such codes.

We present a multiset rank modulation scheme capable of correcting translocation errors, motivated by the fact that compared to permutation codes, multipermutation codes offer higher rates and longer block lengths. We show that the appropriate distance measure for code construction is the Ulam metric applied to equivalence classes of permutations, where each permutation class corresponds to a multipermutation. The paper includes a study of multipermutation codes in the Hamming metric, also known as constant composition codes, due to their use in constructing multipermutation codes in the Ulam metric. We derive bounds on the size of multipermutation codes in both the Ulam metric and the Hamming metric, compute their capacity, and present constructions for codes in the Ulam metric based on permutation interleaving, semi-Latin squares, and resolvable Steiner systems.

We address the problem of computing distances between rankings that take into account similarities between elements. The need for evaluating such distances arises in applications such as machine learning, social sciences and data storage. The problem may be summarized as follows: Given two rankings and a positive cost function on transpositions that depends on the similarity of the elements involved, find a smallest cost sequence of transpositions that converts one ranking into another. Our focus is on costs that may be described via special tree structures and on rankings modeled as permutations. The presented results include a quadratic-time algorithm for finding a minimum cost transform for a single cycle; and a linear time, 5/3-approximation algorithm for permutations that contain multiple cycles.

We consider the novel problem of exact synchronization of two rankings at remote locations connected by a two-way channel. Such synchronization problems arise when items in the data are distinguishable, as is the case for playlists, tasklists, crowdvotes and recommender systems rankings. Our model includes different constraints on the communication throughput of the forward and feedback links, resulting in different anchoring, syndrome and checksum computation strategies. Information editing is assumed of the form of deletions, insertions, block deletions/insertions, translocations and transpositions. The protocols developed under the given model are order-optimal with respect to genie aided lower bounds.

We address the problem of multipermutation code design in the Ulam metric for novel storage applications. Multipermutation codes are suitable for flash memory where cell charges may share the same rank. Changes in the charges of cells manifest themselves as errors whose effects on the retrieved signal may be measured via the Ulam distance. As part of our analysis, we study multipermutation codes in the Hamming metric, known as constant composition codes. We then present bounds on the size of multipermutation codes and their capacity, for both the Ulam and the Hamming metrics. Finally, we present constructions and accompanying decoders for multipermutation codes in the Ulam metric.

We propose a novel group testing method, termed semiquantitative group testing (SQGT), motivated by a class of problems arising in genome screening experiments. The SQGT is a (possibly) nonbinary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, representing generalizations of classical disjunct and separable codes. We describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions, we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the codes constructed in this paper, we describe a number of efficient decoding algorithms. In addition, we describe a belief propagation decoder for sparse SQGT codes for which no other efficient decoder is currently known.

We propose a new family of distance measures on rankings, derived through an axiomatic approach, that consider the nonuniform relevance of the top and bottom of ordered lists and similarities between candidates. The proposed distance functions include specialized weighted versions of the Kendall τ distance and the Cayley distance, and are suitable for comparing rankings in a number of applications, including information retrieval and rank aggregation. In addition to proposing the distance measures and providing the theoretical underpinnings for their applications, we also analyze algorithmic and computational aspects of weighted distance-based rank aggregation. We present an aggregation method based on approximating weighted distance measures by a generalized version of Spearman's footrule distance as well as a Markov chain method inspired by PageRank, where transition probabilities of the Markov chain reflect the chosen weighted distances.

In networked systems comprised of many agents, it is often required to reach a common operating point of all agents, termed the network consensus. We consider two iterative methods for reaching a ranking (ordering) consensus over a voter network, where the initial preference of every voter is of the form of a full ranking of candidates. The voters are allowed, one at a time and based on some random scheme, to change their votes to bring them “closer” to the opinions of selected subsets of peers. The first consensus method is based on changing votes one adjacent swap at a time; the second method is based on changing votes via averaging with the votes of peers, potentially leading to many adjacent swaps at a given time. For the first model, we characterize convergence points and conditions for convergence. For the second model, we prove convergence to a global ranking and derive the rate of convergence to this consensus.

We propose a new family of algorithms for bounding/approximating the optimal solution of rank aggregation problems based on weighted Kendall distances. The algorithms represent linear programming relaxations of integer programs that involve variables reflecting partial orders of three or more candidates. Our simulation results indicate that the linear programs give near-optimal performance for a number of important voting parameters, and outperform methods based on PageRank and Weighted Bipartite Matching.

We consider a novel approach to the information bottleneck problem where the goal is to perform compression of a noisy signal, while retaining a significant amount of information about a correlated auxiliary signal. To facilitate analysis, we cast compression with side information as an optimization problem involving an information measure, which for jointly Gaussian random variables equals the classical mutual information. We provide closed form expressions for locally optimal linear compression schemes; in particular, we show that the optimal solutions are of the form of the product of an arbitrary full-rank matrix and the left eigenvectors corresponding to smallest eigenvalues of a matrix related to the signals' covariance matrices. In addition, we study the influence of the sparsity level of the Bernoulli-Gaussian noise on the compression rate. We also highlight the similarities and differences between the noisy bottleneck problem and canonical correlation analysis (CCA), as well as the Gaussian information bottleneck problem.

We consider the problem of rank aggregation, where the goal is to assemble ordered lists into one consensus order. Our contributions consist of proposing a new family of distance measures that allow for incorporating practical ranking constraints into the aggregation problem formulation; showing how such distance measures arise from a generalization of Kemeny's axioms of the Kendall r distance; and proving that special classes of the proposed distances may be computed in polynomial time.

Metagenomics is an emerging field of molecular biology concerned with analyzing the genomes of environmental samples comprising many different diverse organisms. Given the nature of metagenomic data, one usually has to sequence the genomic material of all organisms in a batch, leading to a mix of reads coming from different DNA sequences. In deep high-throughput sequencing experiments, the volume of the raw reads is extremely high, frequently exceeding 600 Gb. With an ever increasing demand for storing such reads for future studies, the issue of efficient metagenomic compression becomes of paramount importance. We present the first known approach to metagenome read compression, termed MCUIUC (Metagenomic Compression at UIUC). The gist of the proposed algorithm is to perform classification of reads based on unique organism identifiers, followed by reference-based alignment of reads for individually identified organisms, and metagenomic assembly of unclassified reads. Once assembly and classification are completed, lossless reference based compression is performed via positional encoding. We evaluate the performance of the algorithm on moderate sized synthetic metagenomic samples involving 15 randomly selected organisms and describe future directions for improving the proposed compression method.

We consider rank modulation codes for flash memories that allow for handling arbitrary charge-drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation rank codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include derivation of the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes, as well as simple decoding methods for one class of constructed codes. As part of our exposition, we also highlight the close connections between the new code family and permutations with short common subsequences, deletion and insertion error-correcting codes for permutations, and permutation codes in the Hamming distance.

We describe a novel extension of subspace codes for noncoherent networks, suitable for use when the network is viewed as a communication system that introduces both dimension and symbol errors. We show that when symbol erasures occur in a significantly large number of different basis vectors transmitted through the network and when the min-cut of the network is much smaller than the length of the transmitted codewords, the new family of codes outperforms their subspace code counterparts. For the proposed coding scheme, termed hybrid network coding, we derive two upper bounds on the size of the codes. These bounds represent a variation of the Singleton and of the sphere-packing bound. We show that a simple concatenated scheme that consists of subspace codes and Reed-Solomon codes is asymptotically optimal with respect to the Singleton bound. Finally, we describe two efficient decoding algorithms for concatenated subspace codes that in certain cases have smaller complexity than their subspace decoder counterparts.

We consider a novel group testing procedure, termed semi-quantitative group testing, motivated by a class of problems arising in genome sequence processing. Semi-quantitative group testing (SQGT) is a non-binary pooling scheme that may be viewed as a combination of an adder model followed by a quantizer. For the new testing scheme we define the capacity and evaluate the capacity for some special choices of parameters using information theoretic methods. We also define a new class of disjunct codes suitable for SQGT, termed SQ-disjunct codes. We also provide both explicit and probabilistic code construction methods for SQGT with simple decoding algorithms.

We consider a class of small-sample distribution estimators over noisy channels. Our estimators are designed for repetition channels, and rely on properties of the runs of the observed sequences. These runs are modeled via special types of Markov chains, termed “alternating Markov chains”. We show that alternating chains have redundancy that scales sub-linearly with the lengths of the sequences, and describe how to use a distribution estimator for alternating chains for the purpose of distribution estimation over repetition channels.

We consider rank modulation codes for flash memories that allow for handling arbitrary charge drop errors. Unlike classical rank modulation codes used for correcting errors that manifest themselves as swaps of two adjacently ranked elements, the proposed translocation codes account for more general forms of errors that arise in storage systems. Translocations represent a natural extension of the notion of adjacent transpositions and as such may be analyzed using related concepts in combinatorics and rank modulation coding. Our results include deriving the asymptotic capacity of translocation rank codes, construction techniques for asymptotically good codes and a simple decoding algorithm.

The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise -type search procedures with provable performance guarantees. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence and hold with probability one for arbitrary matrix size.

The problem of finding a minimum decomposition of a permutation in terms of transpositions with predetermined non-uniform and non-negative costs is addressed. Alternatively, computing the transposition distance between two permutations, where transpositions are endowed with arbitrary non-negative costs, is studied. For such cost functions, polynomial-time, constant-approximation decomposition algorithms are described. For metric-path costs, exact polynomial-time decomposition algorithms are presented. The algorithms in this paper represent a combination of Viterbi-type algorithms and graph-search techniques for minimizing the cost of individual transpositions, and dynamic programing algorithms for finding minimum cost decompositions of cycles. The presented algorithms have a myriad of applications in information theory, bioinformatics, and algebra.

We consider the problem of noiseless and noisy low- rank tensor completion from a set of random linear measurements. In our derivations, we assume that the entries of the tensor belong to a finite field of arbitrary size and that reconstruction is based on a rank minimization framework. The derived results show that the smallest number of measurements needed for exact reconstruction is upper bounded by the product of the rank, the order, and the dimension of a cubic tensor. Furthermore, this condition is also sufficient for unique minimization. Similar bounds hold for the noisy rank minimization scenario, except for a scaling function that depends on the channel error probability.

The low-rank matrix completion problem can be stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. There exist several low-complexity algorithms for low-rank matrix completion which focus on the minimization of the Frobenius norm of the matrix projection residue. This optimization framework has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we propose a geometric objective function to replace the Frobenius norm: the new objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. Furthermore, using the geometric objective function and a simple gradient descent procedure, we are able to preclude the existence of local minimizers, and hence establish strong performance guarantees for special completion scenarios, which do not require matrix incoherence or large matrix size.

We consider the problem of finding the minimum cost transposition decomposition of a permutation. In this framework, arbitrary non-negative costs are assigned to individual transpositions and the task at hand is to devise polynomial-time, constant-approximation decomposition algorithms. We describe a polynomial-time algorithm based on specialized search strategies that constructs the optimal decomposition of individual transpositions. The analysis of the optimality of decompositions of single transpositions uses graphical models and Menger's theorem. We also present a dynamic programing algorithms that finds the minimum cost, minimum length decomposition of a cycle and show that this decomposition represents a 4-approximation of the optimal solution. The results presented for individual cycles extend to general permutations.

We describe a generalization of the group testing problem termed symmetric group testing. Unlike in classical binary group testing, the roles played by the input symbols zero and one are “symmetric” while the outputs are drawn from a ternary alphabet. Using an information-theoretic approach, we derive sufficient and necessary conditions for the number of tests required for noise-free and noisy reconstructions. Furthermore, we extend the notion of disjunct (zero-false-drop) and separable (uniquely decipherable) codes to the case of symmetric group testing. For the new family of codes, we derive bounds on their size based on probabilistic methods, and provide construction methods based on coding theoretic ideas.

We study the average distortion introduced by scalar, vector, and entropy coded quantization of compressive sensing (CS) measurements. The asymptotic behavior of the underlying quantization schemes is either quantified exactly or characterized via bounds. We adapt two benchmark CS reconstruction algorithms to accommodate quantization errors, and empirically demonstrate that these methods significantly reduce the reconstruction distortion when compared to standard CS techniques.

A new algorithm, termed subspace evolution and transfer (SET), is proposed for solving the consistent matrix completion problem. In this setting, one is given a subset of the entries of a low-rank matrix, and asked to find one low-rank matrix consistent with the given observations. We show that this problem can be solved by searching for a column space that matches the observations. The corresponding algorithm consists of two parts - subspace evolution and subspace transfer. In the evolution part, we use a line search procedure to refine the column space. However, line search is not guaranteed to converge, as there may exist barriers along the search path that prevent the algorithm from reaching a global optimum. To address this problem, in the transfer part, we design mechanisms to detect barriers and transfer the estimated column space from one side of the barrier to the another. The SET algorithm exhibits excellent empirical performance for very low-rank matrices.

One of the main computational challenges in digital fingerprinting systems is the complexity of colluder identification. Inspired by compressive sensing approaches for support recovery of sparse vectors, we propose a novel list-decoding approach for partial colluder identification. We also derive formulas for the minimum codelength required for identifying a nonzero fraction of colluders based on noiseless and noisy measurements, using simple single-step correlation maximization techniques.

Motivated by protein sequencing, we consider the problem of reconstructing a string from the compositions of its substrings. We provide several results, including the following. General classes of strings that cannot be distinguished from their substring compositions. An almost complete characterization of the lengths for which reconstruction is possible. Bounds on the number of strings with the same substring compositions in terms of the number of divisors of the string length plus one. A relation to the turnpike problem and a bivariate polynomial formulation of string reconstruction.

We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. For metric-path costs, we describe exact polynomial-time decomposition algorithms. For extended-metric-path cost functions, we describe polynomial-time constant-approximation decomposition algorithms. Our algorithms rely on graphical representations of permutations and graph-search techniques for minimizing the permutation decomposition cost. The presented algorithms have applications in information theory, bioinformatics, and algebra.

We introduce a new method for decoding short and moderate-length linear block codes with dense parity check matrix representations of cyclic form. This approach is termed multiple-bases belief-propagation. The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard belief-propagation decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the multiple-bases belief propagation decoding performance can be shown to closely follow that of the maximum-likelihood decoder.

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.

Information theory--a field at the intersection of applied mathematics and electrical engineering--was primarily developed for the purpose of addressing problems arising in data storage and data transmission over (noisy) communication media. Consequently, information theory provides the formal basis for much of today’s storage and communication infrastructure.

We study the average distortion introduced by scalar, vector, and entropy coded quantization of compressive sensing (CS) measurements. The asymptotic behavior of the underlying quantization schemes is either quantified exactly or characterized via bounds. We also modify two benchmark CS reconstruction algorithms to accommodate quantization effects, and empirically demonstrate that these methods significantly reduce the reconstruction distortion.

We consider the problem of estimating unknown source distributions based on a small number of possibly erroneous observations. Errors are modeled as arising from sticky channels, which introduce repetitions of transmitted source symbols. Both the problems of estimating the distribution for known and unknown channel parameters are considered. We propose three heuristic algorithms and a method based on Expectation-Maximization for solving the problem. These algorithms represent a combination of iterative optimization techniques and Good-Turing estimators.

We propose a new compressive sensing scheme, based on codes of graphs, that allows for joint design of sensing matrices and low complexity reconstruction algorithms. The compressive sensing matrices can be shown to offer asymptotically optimal performance when used in combination with OMP methods. For more elaborate greedy reconstruction schemes, we propose a new family of list decoding and multiple-basis belief propagation algorithms. Our simulation results indicate that the proposed CS scheme offers good complexity-performance tradeoffs for several classes of sparse signals.

We study the average distortion introduced by quantizing compressive sensing measurements. Both uniform quantization and non-uniform quantization are considered. The asymptotic distortion-rate functions are obtained when the measurement matrix belongs to certain random matrix ensembles. Furthermore, we adapt two well-known compressive sensing reconstruction algorithms to accommodate the quantization effects. The performance of the new reconstruction methods is assessed through extensive computer simulations.

Modeling the joint expression patterns of genes is a challenging task due to the large number of genes simultaneously studied, relative to the amount of microarray data available. To model the joint expression profiles of genes using a small number of observations, we use Ising models to approximate the joint expression profiles. This approach naturally lends itself to the study of gene interactions and has a close connection to clustering techniques, which we use to reconstruct E. coli gene interaction pathways from microarray data. In addition, we note that extending available partial network topology information can be done using very few microarray samples-logarithmic in the number of genes.

MOTIVATION: The problem of reverse engineering the dynamics of gene expression profiles is of focal importance in systems biology. Due to noise and the inherent lack of sufficiently large datasets generated via high-throughput measurements, known reconstruction frameworks based on dynamical systems models fail to provide adequate settings for network analysis. This motivates the study of new approaches that produce stochastic lists of explanations for the observed network dynamics that can be efficiently inferred from small sample sets and in the presence of errors. RESULTS: We introduce a novel algebraic modeling framework, termed stochastic polynomial dynamical systems (SPDSs) that can capture the dynamics of regulatory networks based on microarray expression data. Here, we refer to dynamics of the network as the trajectories of gene expression profiles over time. The model assumes that the expression data is quantized in a manner that allows for imposing a finite field structure on the observations, and the existence of polynomial update functions for each gene in the network. The underlying reverse engineering algorithm is based on ideas borrowed from coding theory, and in particular, list-decoding methods for so called Reed-Muller codes. The list-decoding method was tested on synthetic data and on microarray expression measurements from the M(3D) database, corresponding to a subnetwork of the Escherichia coli SOS repair system, as well as on the complete transcription factor network, available at RegulonDB. The results show that SPDSs constructed via list-decoders significantly outperform other algebraic reverse engineering methods, and that they also provide good guidelines for estimating the influence of genes on the dynamics of the network. AVAILABILITY: Software codes for list-decoding algorithms suitable for direct application to quantized expression data will be publicly available at the authors' web-pages.

We introduce a new family of codes, termed weighted superimposed codes (WSCs). This family generalizes the class of Euclidean superimposed codes (ESCs), used in multiuser identification systems. WSCs allow for discriminating all bounded, integer-valued linear combinations of real-valued codewords that satisfy prescribed norm and nonnegativity constraints. By design, WSCs are inherently noise tolerant. Therefore, these codes can be seen as special instances of robust compressed sensing schemes. The main results of the paper are lower and upper bounds on the largest achievable code rates of several classes of WSCs. These bounds suggest that, with the codeword and weighting vector constraints at hand, one can improve the code rates achievable by standard compressive sensing techniques.

We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of linear programming (LP) optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean-squared error of the reconstruction is upper-bounded by constant multiples of the measurement and signal perturbation energies.

We generalize the notion of the stopping redundancy in order to study the smallest size of a trapping set in Tanner graphs of linear block codes. In this context, we introduce the notion of the trapping redundancy of a code, which quantifies the relationship between the number of redundant rows in any parity-check matrix of a given code and the size of its smallest trapping set. Trapping sets with certain parameter sizes are known to cause error-floors in the performance curves of iterative belief propagation (BP) decoders, and it is therefore important to identify decoding matrices that avoid such sets. Bounds on the trapping redundancy are obtained using probabilistic and constructive methods, and the analysis covers both general and elementary trapping sets. Numerical values for these bounds are computed for the [2640, 1320] Margulis code and the class of projective geometry codes, and compared with some new code-specific trapping set size estimates.

Compressive sensing microarrays (CSM) are DNA-based sensors that operate using the principle of compressive sensing (CS). In contrast to conventional DNA microarrays, in which each genetic sensor is designed to respond to a single target, in a CSM each sensor responds to a group of targets. We study the problem of designing CS probes that simultaneously account for both the constraints from group testing theory and the biochemistry of probe-target DNA hybridization. Our results show that, in order to achieve accurate hybridization profiling, consensus probe sequences are required to have sequence homology of at least 80% with all targets to be detected. Furthermore, experiments show that out-of-equilibrium datasets are usually as accurate as those obtained from equilibrium conditions. Consequently, one can use CSMs in applications for which only short hybridization times are allowed.

We propose a novel algebraic method for reverse engineering the dynamics of gene regulatory networks of known topology, based on list-decoding and iterative model refinement algorithms. The crux of our approach is to describe the update functions for gene expressions in terms of polynomials over finite fields, or more precisely, codewords of Reed-Muller (RM) codes. In this setting, errors, missing data points, and small sample sizes of the measurements are accounted for via list-decoding of RM codes. We test the performance of the new method both on synthetic data and a regulatory sub-net of the E. coli gene control network responsible for DNA repair. The expression profiles used in the study are obtained through data fusion techniques over the many microbe microarray database. The list-decoding approach offers significant performance improvements over previously known algebraic methods, such as those based on Grobner bases techniques.

We introduce a new family of codes, termed weighted Euclidean superimposed codes (WESCs). This family generalizes the class of Euclidean superimposed codes, used in multiuser identification systems. WESCs allow for discriminating bounded, integer-valued linear combinations of real-valued codewords, and can therefore also be seen as a specialization of compressed sensing schemes. We present lower and upper bounds on the largest size of a member of the WESCs family, and show how to use classical coding-theoretic and new compressed sensing analytical tools to devise low-complexity decoding algorithms for these codes.

We provide an overview of known modeling approaches for gene regulatory networks, and introduce a new framework for analyzing such networks as probabilistic polynomial dynamical systems. In the latter context, we describe how list decoding methods for Reed-Muller codes can be used to cope with small DNA microarray sample set problems and measurement noise. We also describe possible future research directions at the interface of systems biology and coding theory, pertaining to probabilistic dynamical systems with memory and probabilistic factor graphs with local list-decoding components.

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via Lovasz's local lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.

A novel soft-decoding method for algebraic block codes is presented. The algorithm is designed for soft-decision decoding and is based on belief-propagation (BP) decoding using multiple bases of the dual code. Compared to other approaches for high-performance BP decoding, this method is conceptually simple and does not change at each stage of the decoding process. With its multiple BP decoders the proposed scheme achieves the performance of a standard BP algorithm with a significantly lower number of iterations per decoder realization. By this means the data delay introduced by decoding is reduced. Moreover, a significant improvement in decoding performance is achieved while keeping the data delay small. It is shown that for selected codes the proposed scheme approaches near maximum likelihood (ML) performance for very small data processing delays.

We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.

Constrained coding is a combinatorial technique for converting unrestricted sequences into sequences with a predefined set of properties. Traditionally, applications of this coding technique are confined to sequences drawn from regular languages. Nevertheless, there exist many families of words that cannot be described within this narrow setting. We propose to reformulate and extend a set of results from constrained coding theory in order to analyze sequences from context- free languages. For the purpose of computing the capacity of the context-free constraints, we use the DSV (Delest-Schutzenberger-Viennot) theory for grammars and attribute grammars. We illustrate the new approach on a problem related to enumerating RNA secondary structures that satisfy certain stability requirements.

Hybrid ARQ transmission schemes combine the conventional ARQ with forward error correction. Incremental redundancy hybrid ARQ schemes adapt their error correcting code redundancy to varying channel gains, and thus achieve better throughput performance than ordinary ARQ, particularly over wireless channels with fluctuating channel conditions. Consequently, the scheme has been adopted by a number of standards for mobile phone networks. We provide a brief survey of theory and state of the art of hybrid ARQ, and present some possible future directions keeping in mind practical considerations.

It is well known that certain combinatorial structures in the Tanner graph of a low-density parity-check (LDPC) code exhibit a strong influence on its performance under iterative decoding. These structures include cycles, stopping/trapping sets, and parameters such as the diameter of the code. In general, it is very hard to find a complete characterization of such configurations in an arbitrary code, and even harder to understand the intricate relationships that exist between these entities. It is, therefore, of interest to identify a simple setting in which all the described combinatorial structures can be enumerated and studied within a joint framework. One such setting is developed in this paper, for the purpose of analyzing the distribution of short cycles and the structure of stopping and trapping sets in Tanner graphs of LDPC codes based on idempotent and symmetric Latin squares. The parity-check matrices of LDPC codes based on Latin squares have a special form that allows for connecting combinatorial parameters of the codes with the number of certain subrectangles in the Latin squares. Subrectangles of interest can be easily identified, and in certain instances, completely enumerated. This study can be extended in several different directions, one of which is concerned with modifying the code design process in order to eliminate or reduce the number of configurations bearing a negative influence on the performance of the code. Another application of the results includes determining to which extent a configuration governs the behavior of the bit-error rate curve in the waterfall and error-floor regions

We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes

We analyze the effect of redundant parity-check equations on the error-floor performance of low-density parity- check (LDPC) codes used over the additive white Gaussian noise (AWGN) channel. Our findings show that a large number of iterative decoding errors in the [2640,1320] Margulis code, confined to point trapping sets in the standard Tanner graph, can be corrected if only one redundant parity-check equation is added to the decoder's matrix. We also derive an analytic expression relating the number of rows in the parity-check matrix of a code and the parameters of trapping sets in the code's graph.

Trapping sets represent subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor. We compute the asymptotic normalized distributions of trapping sets in random, irregular, binary low-density parity-check (LDPC) code ensembles. Our derivations rely on techniques from large deviation theory and statistical methods for enumeracting random-like matrices. Similar methods can be used for computing the spectra of other combinatorial entities in LDPC code, such as subcodes and/or minimal codewords.

We introduce a new family of unequal error protection (UEP) codes, based on low-density parity-check (LDPC) component codes and Plotkin-type constructions. The codes are decoded iteratively in multiple stages, and the order of decoding determines the level of error protection. The level of UEP among the code bits is also influenced by the choice of the LDPC component codes and by some new reliability features incorporated into the decoding process. The proposed scheme offers a very good tradeoff between code performance on one side and encoding/decoding and storage complexity on the other side. The novel approach to UEP also allows for finding simple approximations for the achievable degrees of UEP, which can be used to govern practical code design implementations

One approach to designing structured low-density parity-check (LDPC) codes with large girth is to shorten codes with small girth in such a manner that the deleted columns of the parity-check matrix contain all the variables involved in short cycles. This approach is especially effective if the parity-check matrix of a code is a matrix composed of blocks of circulant permutation matrices, as is the case for the class of codes known as array codes. We show how to shorten array codes by deleting certain columns of their parity-check matrices so as to increase their girth. The shortening approach is based on the observation that for array codes, and in fact for a slightly more general class of LDPC codes, the cycles in the corresponding Tanner graph are governed by certain homogeneous linear equations with integer coefficients. Consequently, we can selectively eliminate cycles from an array code by only retaining those columns from the parity-check matrix of the original code that are indexed by integer sequences that do not contain solutions to the equations governing those cycles. We provide Ramsey-theoretic estimates for the maximum number of columns that can be retained from the original parity-check matrix with the property that the sequence of their indices avoid solutions to various types of cycle-governing equations. This translates to estimates of the rate penalty incurred in shortening a code to eliminate cycles. Simulation results show that for the codes considered, shortening them to increase the girth can lead to significant gains in signal-to-noise ratio (SNR) in the case of communication over an additive white Gaussian noise (AWGN) channel.

In this paper, we consider the problem of designing codewords for DNA storage systems and DNA computers that are unlikely to fold back onto themselves to form undesirable secondary structures. Secondary structure formation causes a DNA codeword to become less active chemically, thus rendering it useless for the purpose of DNA computing. It also defeats the read-back mechanism in a DNA storage system, so that information stored in such a folded DNA codeword cannot be retrieved. Based on some simple properties of a dynamic-programming algorithm, known as Nussinov's method, which is an effective predictor of secondary structure given the sequence of bases in a DNA codeword, we identify some design criteria that reduce the possibility of secondary structure formation in a codeword. These design criteria can be formulated in terms of the requirement that the Watson-Crick distance between a DNA codeword and a number of its shifts be larger than a given threshold. This paper addresses both the issue of enumerating DNA sequences with such properties and the problem of practical DNA code construction

A family of unequal error-protection (UEP) low-density parity-check (LDPC) codes, based on Plotkin-type constructions, is introduced. The codes are decoded in multiple stages in such a manner that the order of decoding determines the level of error protection. The level of UEP among the code bits can be further increased by properly combining structured and random-like LDPC component codes with carefully chosen properties, and by using some new reliability features. The proposed scheme also offers a good trade-off between code performance on the one hand and encoding/decoding and storage complexity on the other. To the best of our knowledge, the proposed approach represents the first iterative UEP method with analytically provable properties.

In this paper, an efficient, fully-parallel network of programmable logic array (NPLA)-based realization of iterative decoders for structured LDPC codes is presented. The LDPC codes are developed in tandem with the underlying VLSI implementation technique, without compromising chip design constraints. The codes are based on a novel modification of array codes. This design methodology results in reduced routing congestion, a major problem in prior approaches. The operating power, delay and chip-size of the circuits are estimated, indicating that this implementation significantly outperforms presently used standard-cell based architectures. The described LDPC design method can accommodate widely different requirements, such as those arising from recording and wireless channel applications.

In this paper, we introduce a family of structured low-density parity-check (LDPC) codes based on a class of idempotent, symmetric Latin and modified Latin squares. The parity-check matrices of the codes have a block structure with permutation blocks which insures that both their corresponding girth and minimum distance are at least equal to six. The storage requirement for codes from this class is reduced to only one parameter. We also propose a structured method for shortening the codes by removing columns that break a large number of cycles of length six. The storage requirements for the codes obtained using the described procedure consist in memorizing only two integers, while their performance under iterative decoding matches that of random-like codes of comparable length.

It is well known that random-like low-density parity-check (LDPC) codes over the extension fields GF(2/sup m/) of GF(2), for m>1, tend to outperform their binary counterparts of comparable length and rate. At the same time, structured LDPC codes offer the advantage of reduced implementation and storage complexity, so that it is of interest to investigate mathematical design methods for codes on graphs over fields of large order. We propose a new class of combinatorially developed codes obtained by properly combining Reed-Solomon (RS) type parity-check matrices and sparse parity-check matrices based on permutation matrices. The proposed codes have large girth and minimum distance. In order to further reduce the decoding complexity of the proposed scheme, we introduce a new decoding algorithm based on matrix representations of the underlying field, which trades performance for complexity. The particular field representation described in this abstract is based on a power basis generated by a companion matrix of a primitive polynomial of the field GF(2/sup m/). It is observed that the choice of the primitive polynomial influences the cycle distribution of the code graph.

Bin models represent one of the most frequently used descriptive representations of phenomena as diverse as spreading of disease, financial market fluctuation, error burst generation in communication channels, or learning in neurological systems. When analyzing randomized bin models, it is usually of interest to evaluate some statistic depending on the characteristics of the distribution of objects (balls) into bins. Due to the inherent mutual dependence of the occupancy variables, determining this statistic may represent a challenging analytical task. In this paper, we describe a class of invertible probabilistic transforms that result in mapping dependent bin occupancies into independent random variables. The statistics of interest can be evaluated in the transform domain and then appropriately inverted to obtain an exact solution. Or, for problems with large values for the parameters, the asymptotic behavior of the statistics can be deduced from the transform itself. Possible analytical applications of these new transform techniques in coding theory include the binning schemes related to Luby transform (LT), Slepian-Wolf, and deletion-error correcting coding.

The aim of this paper is to describe a new class of problems and some new results in coding theory arising from the analysis of the composition and functionality of the genetic code. The major goal of the proposed work is to initiate research on investigating possible connections between the regulatory network of gene interactions (RNGI) and the proofreading (error-control) mechanism of the processes of the central dogma of genetics. New results include establishing a direct relationship between Boolean network (BN) models of RNGI and Gallager's LDPC decoding algorithms. The proposed research topics and described results are expected to have a two-fold impact on coding theory and genetics research. Firstly, they may provide a different setting in which to analyze standard LDPC decoding algorithms, by using dynamical systems and Boolean function theory. Secondly, they may be of use in establishing deeper relationships between the DNA proofreading mechanism, RNGI, and their joint influence on the development and possible treatment of genetic diseases like cancer.

This paper introduces several new combinatorial constructions of low-density parity-check (LDPC) codes, in contrast to the prevalent practice of using long, random-like codes. The proposed codes are well structured, and unlike random codes can lend themselves to a very low-complexity implementation. Constructions of regular Gallager codes based on cyclic difference families, cycle-invariant difference sets, and affine 1-configurations are introduced. Several constructions of difference families used for code design are presented, as well as bounds on the minimal distance of the codes based on the concept of a generalized Pasch configuration.

We investigate the computational complexity of the A* algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A* decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.

We present combinatorial methods for computing the third support weight enumerators of the five doubly-even, self-dual [32,16,8] codes. The methods exploit relationships that exist between support weight enumerators and complete coset weight enumerators of a self-dual code.

We introduce a new enumerative encoding method for (d,k) codes. The encoding algorithm, which is based on enumeration of multiset permutations, is conceptually simpler and computationally less expensive than other algorithms proposed thus far. We also describe a new application of enumerative encoding methods for phrase length distribution shaping of run-length-limited (RLL) sequences. We demonstrate that by reducing the probability of occurrence of long phrases in maxentropic RLL sequences, the frequency of patterns that account for most of the errors in magnetic recording systems can be decreased.

We consider multiamplitude, multitrack runlength-limited (d, k) constrained channels with and without clock redundancy. We calculate the Shannon capacities of these channels and present some simple 100% efficient codes. To compute capacity a constraint graph equivalent to the usual runlength-limited constraint graph is used. The introduced graph model has the vertex labeling independent of number of tracks to be written on (in parallel), which provides computational savings when the number of tracks is large. We show that increasing the number of tracks written on in parallel provides significant increase of per-track capacity for the more restrictive clocking constraint case, i.e., when k