SUMMARY: Multiple sequence alignment is an important problem in computational biology with applications that include phylogeny and the detection of remote homology between protein sequences. UPP is a popular software package that constructs accurate multiple sequence alignments for large datasets based on ensembles of hidden Markov models (HMMs). A computational bottleneck for this method is a sequence-to-HMM assignment step, which relies on the precise computation of probability scores on the HMMs. In this work, we show that we can speed up this assignment step significantly by replacing these HMM probability scores with alternative scores that can be efficiently estimated. Our proposed approach utilizes a multi-armed bandit algorithm to adaptively and efficiently compute estimates of these scores. This allows us to achieve similar alignment accuracy as UPP with a significant reduction in computation time, particularly for datasets with long sequences. AVAILABILITY AND IMPLEMENTATION: The code used to produce the results in this paper is available on GitHub at: https://github.com/ilanshom/adaptiveMSA.

In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that$\exp (\tilde {O}(n^{1/5}))$traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a “density map” that indicates the locations of each length-k substring throughout s. We show that when$k = c \log n$where c is constant,$\epsilon ^{-2}\cdot \text { poly} (n)$traces suffice to recover the density map with error at most$\epsilon $. As a result, when restricted to a set of source strings whose minimum “density map distance” is at least$1/\text {poly}(n)$, the trace reconstruction problem can be solved with polynomially many traces.

In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that exp(Õ(n1/5)) traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map" that indicates the locations of each length-k substring throughout s. We show that ϵ–2• poly(n) traces suffice to recover the density map with error at most ϵ. As a result, when restricted to a set of source strings whose minimum "density map distance" is at least 1/poly(n), the trace reconstruction problem can be solved with polynomially many traces.

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

When an individual's DNA is sequenced, sensitive medical information becomes available to the sequencing laboratory. A recently proposed way to hide an individual's genetic information is to mix in DNA samples of other individuals. We assume these samples are known to the individual but unknown to the sequencing laboratory. Thus, these DNA samples act as "noise" to the sequencing laboratory, but still allow the individual to recover their own DNA samples afterward. Motivated by this idea, we study the problem of hiding a binary random variable X (a genetic marker) with the additive noise provided by mixing DNA samples, using mutual information as a privacy metric. This is equivalent to the problem of finding a worst-case noise distribution for recovering X from the noisy observation among a set of feasible discrete distributions. We characterize upper and lower bounds to the solution of this problem, which are empirically shown to be very close. The lower bound is obtained through a convex relaxation of the original discrete optimization problem, and yields a closed-form expression. The upper bound is computed via a greedy algorithm for selecting the mixing proportions.

For any code, the set of received words generated by insertion errors is infinitely large. We prove that infinitely many of these words are uniquely decodable. We proceed to analyze how often unique decoding from insertions occurs for arbitrary codes. These questions are relevant because insertion errors frequently occur in synchronization and DNA, a medium which is beginning to be used for long term data storage. For a codeword c of length n, we are interested in two particular measures. The first is the probability of unique decoding when t insertions occur, if each distinct length n + t received word is output with equal probability. The second is the probability of unique decoding when t sequential insertions occur, and each insertion position and element are selected uniformly at random. This paper attempts to better understand the behavior of the measures for arbitrary codewords, placing a particular emphasis on limiting behavior as t or n increases. Our most substantial contribution is the derivation of upper bounds on both measures, which are mathematically related to Levenshtein's reconstruction problem.

We study the problem of perfectly reconstructing sequences from traces. The sequences are codewords from a deletion/insertion-correcting code and the traces are the result of corruption by a fixed number of symbol insertions (larger than the minimum edit distance of the code.) This is the general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding a tight upper bound on the number of distinct traces necessary to guarantee exact reconstruction. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT codeword pairs achieve the worst-case number of outputs needed for exact reconstruction.