Microbial natural products represent a major source of bioactive compounds for drug discovery. Among these molecules, nonribosomal peptides (NRPs) represent a diverse class that include antibiotics, immunosuppressants, anticancer agents, toxins, siderophores, pigments, and cytostatics. The discovery of novel NRPs remains a laborious process because many NRPs consist of nonstandard amino acids that are assembled by nonribosomal peptide synthetases (NRPSs). Adenylation domains (A-domains) in NRPSs are responsible for selection and activation of monomers appearing in NRPs. During the past decade, several support vector machine-based algorithms have been developed for predicting the specificity of the monomers present in NRPs. These algorithms utilize physiochemical features of the amino acids present in the A-domains of NRPSs. In this article, we benchmarked the performance of various machine learning algorithms and features for predicting specificities of NRPSs and we showed that the extra trees model paired with one-hot encoding features outperforms the existing approaches. Moreover, we show that unsupervised clustering of 453 560 A-domains reveals many clusters that correspond to potentially novel amino acids. While it is challenging to predict the chemical structure of these amino acids, we developed novel techniques to predict their various properties, including polarity, hydrophobicity, charge, and presence of aromatic rings, carboxyl, and hydroxyl groups.

MOTIVATION: Untargeted mass spectrometry experiments enable the profiling of metabolites in complex biological samples. The collected fragmentation spectra are the metabolite's fingerprints that are used for molecule identification and discovery. Two main mass spectrometry strategies exist for the collection of fragmentation spectra: data-dependent acquisition (DDA) and data-independent acquisition (DIA). In the DIA strategy, all the metabolites ions in predefined mass-to-charge ratio ranges are co-isolated and co-fragmented, resulting in multiplexed fragmentation spectra that are challenging to annotate. In contrast, in the DDA strategy, fragmentation spectra are dynamically and specifically collected for the most abundant ions observed, causing redundancy and sub-optimal fragmentation spectra collection. Yet, DDA results in less multiplexed fragmentation spectra that can be readily annotated. RESULTS: We introduce the MS2Planner workflow, an Iterative Optimized Data Acquisition strategy that optimizes the number of high-quality fragmentation spectra over multiple experimental acquisitions using topological sorting. Our results showed that MS2Planner increases the annotation rate by 38.6% and is 62.5% more sensitive and 9.4% more specific compared to DDA. AVAILABILITY AND IMPLEMENTATION: MS2Planner code is available at https://github.com/mohimanilab/MS2Planner. The generation of the inclusion list from MS2Planner was performed with python scripts available at https://github.com/lfnothias/IODA_MS. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Finding associations between pairs of variables in large datasets is crucial for various disciplines. The brute force method for solving this problem requires computing the mutual information between $\binom{N}{2}$ pairs. In this paper, we consider the problem of finding pairs of variables with high mutual information in sub-quadratic complexity. This problem is analogous to the nearest neighbor search, where the goal is to find pairs among $N$ variables that are similar to each other. To solve this problem, we develop a new algorithm for finding associations based on constructing a decision tree that assigns a hash to each variable, in a way that for pairs with higher mutual information, the chance of having the same hash is higher. For any $1 \leq \lambda \leq 2$, we prove that in the case of binary data, we can reduce the number of necessary mutual information computations for finding all pairs satisfying $I(X, Y) > 2- \lambda$ from $O(N^2)$ to $O(N^\lambda)$, where $I(X,Y)$ is the empirical mutual information between variables $X$ and $Y$. Finally, we confirmed our theory by experiments on simulated and real data. The implementation of our method and experiments is publicly available at \href{https://github.com/mohimanilab/HashMI}{https://github.com/mohimanilab/HashMI}.

Let${\bf A}$be an$n \times m$matrix with$m > n$, and suppose that the underdetermined linear system${\bf A} {\bf s} = {\bf x}$admits a sparse solution${\bf s}_0$for which$\Vert {\bf s}_0\Vert_0 < {1\over 2} {\rm spark}({\bf A})$. Such a sparse solution is unique due to a well-known uniqueness theorem. Suppose now that we have somehow a solution$\mathhat{\bf s}$as an estimation of${\bf s}_0$, and suppose that$\mathhat{\bf s}$is only “approximately sparse,” that is, many of its components are very small and nearly zero, but not mathematically equal to zero. Is such a solution necessarily close to the true sparsest solution? More generally, is it possible to construct an upper bound on the estimation error$\Vert \mathhat{\bf s}-{\bf s}_0\Vert_2$without knowing${\bf s}_0$? The answer is positive, and in this paper, we construct such a bound based on minimal singular values of submatrices of${\bf A}$. We will also state a tight bound, which is more complicated, but besides being tight, enables us to study the case of random dictionaries and obtain probabilistic upper bounds. We will also study the noisy case, that is, where${\bf x} = {\bf A} {\bf s}+{\bf n}$. Moreover, we will see that where$\Vert{{\bf s}_0}\Vert_0$grows, to obtain a predetermined guaranty on the maximum of$\Vert{\mathhat{\bf s}-{\bf s}_0}\Vert_2,$$\mathhat{\bf s}$is needed to be sparse with a better approximation. This can be seen as an explanation to the fact that the estimation quality of sparse recovery algorithms degrades where$\Vert{{\bf s}_0}\Vert_0$grows.

We describe two algorithms for calculating the probability of m-symbol length-n patterns over k-element distributions, a partition-based algorithm with complexity roughly 2O(m log m)and a recursive algorithm with complexity roughly 2O(m+log n)with the precise bounds provided in the text. The problem is related to symmetric-polynomial evaluation, and the analysis reveals a connection to the number of connected graphs.

In this paper we present an algorithm for complex-valued sparse representation. In our previous work we presented an algorithm for sparse representation based on smoothed lscrdeg- norm. Here we extend that algorithm to complex-valued signals. The proposed algorithm is compared to FOCUSS algorithm and it is experimentally shown that the proposed algorithm is about two or three orders of magnitude faster than FOCUSS while providing approximately the same accuracy.