Black-box algorithms aim to optimize functions without access to their analytical structure or gradient information, making them essential when gradients are unavailable or computationally expensive to obtain. Traditional methods for black-box optimization (BBO) primarily utilize non-parametric models, but these approaches often struggle to scale effectively in large input spaces. Conversely, parametric approaches, which rely on neural estimators and gradient signals via backpropagation, frequently encounter substantial gradient estimation errors, limiting their reliability. Explicit Gradient Learning (EGL), a recent advancement, directly learns gradients using a first-order Taylor approximation and has demonstrated superior performance compared to both parametric and non-parametric methods. However, EGL inherently remains local and myopic, often faltering on highly non-convex optimization landscapes. In this work, we address this limitation by integrating global statistical insights from the evolutionary algorithm CMA-ES into the gradient learning framework, effectively biasing gradient estimates towards regions with higher optimization potential. Moreover, we enhance the gradient learning process by estimating the Hessian matrix, allowing us to correct the second-order residual of the Taylor series approximation. Our proposed algorithm, EvoGrad2 (Evolutionary Gradient Learning with second-order approximation), achieves state-of-the-art results on the synthetic COCO test suite, exhibiting significant advantages in high-dimensional optimization problems. We further demonstrate EvoGrad2's effectiveness on challenging real-world machine learning tasks, including adversarial training and code generation, highlighting its ability to produce more robust, high-quality solutions. Our results underscore EvoGrad2's potential as a powerful tool for researchers and practitioners facing complex, high-dimensional, and non-linear optimization problems.

Multiple deterministic and probabilistic solutions have been proposed for the max-clique (MC) and max-planted-clique (MPC) problems. However, those remain prohibitively expensive in large graphs. The problem can be simplified if one assumes a coloring of the graph and a regular coloring of the clique (a rainbow clique). However, to date, no rainbow clique algorithm has been proposed. We propose SPHERA (Search Space Limitation Efficient Rainbow Clique Algorithm) to find rainbow cliques using a combination of greedy growth, backtracking, and an efficient minimization of the search space using colored k − C o r e s . We show in G ( n , p ) and real-world colored graphs that SPHERA detects the maximal rainbow clique with a much higher probability and much faster than current non-rainbow clique algorithms. We further propose multiple heuristics for the initial vertex selection in real-world graphs and show that those improve the clique detection speed in SPHERA. The code is available in GitHub at https://github.com/louzounlab/SPHERA .

Survival analysis (SA) prediction involves the prediction of the time until an event of interest occurs (TTE), based on input attributes. The main challenge of SA is instances where the event is not observed (censored), typically through an alternative (censoring) event. Most SA prediction methods suffer from drawbacks limiting the usage of advanced machine learning methods: Ignoring the input of the censored samples, no separation between model and loss, and typical small datasets and high input dimensions. We propose a loss function, denoted suRvival Analysis lefT barrIer lOss (RATIO), that explicitly incorporates the censored samples input in the prediction. RATIO accounts for the difference between censored and uncensored samples, by only considering censoring events occurring after the predicted, and through a linear term on the uncensored data event time. RATIO can be used with any prediction model. We further propose FIESTA a data augmentation method, combining the TTE of uncensored samples with the input of censored samples. We show that RATIO drastically improves the precision and reduces the bias of SA prediction in both models and real-life SA problems, and FIESTA allows for the inclusion of high-dimension data in SA methods even with a small number of uncensored samples.

B cell epitope prediction methods are separated into linear sequence-based predictors and conformational epitope predictions that typically use the measured or predicted protein structure. Most linear predictions rely on the translation of the sequence to biologically based representations and the applications of machine learning on these representations. We here present CALIBER 'Conformational And LInear B cell Epitopes pRediction', and show that a bidirectional long short-term memory with random projection produces a more accurate prediction (test set AUC=0.789) than all current linear methods. The same predictor when combined with an Evolutionary Scale Modeling-2 projection also improves on the state of the art in conformational epitopes (AUC = 0.776). The inclusion of the graph of the 3D distances between residues did not increase the prediction accuracy. However, the long-range sequence information was essential for high accuracy. While the same model structure was applicable for linear and conformational epitopes, separate training was required for each. Combining the two slightly increased the linear accuracy (AUC 0.775 versus 0.768) and reduced the conformational accuracy (AUC = 0.769).

The Hardy-Weinberg equilibrium (HWE) assumption is essential to many population genetics models. Multiple tests were developed to test its applicability in observed genotypes. Current methods are divided into exact tests applicable to small populations and a small number of alleles, and approximate goodness-of-fit tests. Existing tests cannot handle ambiguous typing in multi-allelic loci. We here present a novel exact test Unambiguous Multi Allelic Test (UMAT) not limited to the number of alleles and population size, based on a perturbative approach around the current observations. We show its accuracy in the detection of deviation from HWE. We then propose an additional model to handle ambiguous typing using either sampling into UMAT or a goodness-of-fit test test with a variance estimate taking ambiguity into account, named Asymptotic Statistical Test with Ambiguity (ASTA). We show the accuracy of ASTA and the possibility of detecting the source of deviation from HWE. We apply these tests to the HLA loci to reproduce multiple previously reported deviations from HWE, and a large number of new ones.

Graph embedding algorithms (GEA) project each vertex in a graph to a real-valued vector. Dynamic GEA (DGEA) are used to project dynamic graphs, where vertices and edges can appear and disappear. Such graphs are mostly divided into snapshots. Current DGEAs are often offline, and computationally expensive, and most do not ensure a slow change in vertices projection.

Multiple methods of finding the vertices belonging to a planted dense subgraph in a random dense G(n, p) graph have been proposed, with an emphasis on planted cliques. Such methods can identify the planted subgraph in polynomial time, but are all limited to several subgraph structures. Here, we present PYGON, a graph neural network-based algorithm, which is insensitive to the structure of the planted subgraph. This is the first algorithm that uses learning tools for recovering dense subgraphs. We show that PYGON can recover cliques of sizes Θ (√ n), where n is the size of the background graph, comparable with the state of the art. We also show that the same algorithm can recover multiple other planted subgraphs of size Θ (√ n), in both directed and undirected graphs. We suggest a conjecture that no polynomial time PAC-learning algorithm can detect planted dense subgraphs with size smaller than O ( √ n), even if in principle one could find dense subgraphs of logarithmic size.

Recent advances in T cell repertoire (TCR) sequencing allow for the characterization of repertoire properties, as well as the frequency and sharing of specific TCR. However, there is no efficient measure for the local density of a given TCR. TCRs are often described either through their Complementary Determining region 3 (CDR3) sequences, or theirV/J usage, or their clone size. We here show that the local repertoire density can be estimated using a combined representation of these components through distance conserving autoencoders and Kernel Density Estimates (KDE). We present ELATE-an Encoder-based LocAl Tcr dEnsity and show that the resulting density of a sample can be used as a novel measure to study repertoire properties. The cross-density between two samples can be used as a similarity matrix to fully characterize samples from the same host. Finally, the same projection in combination with machine learning algorithms can be used to predict TCR-peptide binding through the local density of known TCRs binding a specific target.

Black-Box Optimization (BBO) methods can find optimal policies for systems that interact with complex environments with no analytical representation. As such, they are of interest in many Artificial Intelligence (AI) domains. Yet classical BBO methods fall short in high-dimensional non-convex problems. They are thus often overlooked in real-world AI tasks. Here we present a BBO method, termed Explicit Gradient Learning (EGL), that is designed to optimize high-dimensional ill-behaved functions. We derive EGL by finding weak spots in methods that fit the objective function with a parametric Neural Network (NN) model and obtain the gradient signal by calculating the parametric gradient. Instead of fitting the function, EGL trains a NN to estimate the objective gradient directly. We prove the convergence of EGL to a stationary point and its robustness in the optimization of integrable functions. We evaluate EGL and achieve state-of-the-art results in two challenging problems: (1) the COCO test suite against an assortment of standard BBO methods; and (2) in a high-dimensional non-convex image generation task.

MOTIVATION: RNA viruses generate a cloud of genetic variants within each host. This cloud contains high-frequency genotypes, and many rare variants. The dynamics of these variants is crucial to understand viral evolution and their effect on their host. RESULTS: We use an experimental evolution system to show that the genetic cloud surrounding the Coxsackie virus master sequence slowly, but steadily, evolves over hundreds of generations. This movement is determined by strong context-dependent mutations, where the frequency and type of mutations are affected by neighboring positions, even in silent mutations. This context-dependent mutation pattern serves as a spearhead for the viral population's movement within the adaptive landscape and affects which new dominant variants will emerge. The non-local mutation patterns affect the mutated dinucleotide distribution, and eventually lead to a non-uniform dinucleotide distribution in the main viral sequence. We tested these results on other RNA viruses with similar conclusions. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: For over 10 years allele-level HLA matching for bone marrow registries has been performed in a probabilistic context. HLA typing technologies provide ambiguous results in that they could not distinguish among all known HLA alleles equences; therefore registries have implemented matching algorithms that provide lists of donor and cord blood units ordered in terms of the likelihood of allele-level matching at specific HLA loci. With the growth of registry sizes, current match algorithm implementations are unable to provide match results in real time. RESULTS: We present here a novel computationally-efficient open source implementation of an HLA imputation and match algorithm using a graph database platform. Using graph traversal, the matching algorithm runtime is practically not affected by registry size. This implementation generates results that agree with consensus output on a publicly-available match algorithm cross-validation dataset. AVAILABILITY AND IMPLEMENTATION: The Python, Perl and Neo4j code is available at https://github.com/nmdp-bioinformatics/grimm. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The major histocompatibility complex (MHC) contains the most polymorphic genetic system in humans, the human leukocyte antigen (HLA) genes of the adaptive immune system. High allelic diversity in HLA is argued to be maintained by balancing selection, such as negative frequency-dependent selection or heterozygote advantage. Selective pressure against immune escape by pathogens can maintain appreciable frequencies of many different HLA alleles. The selection pressures operating on combinations of HLA alleles across loci, or haplotypes, have not been extensively evaluated since the high HLA polymorphism necessitates very large sample sizes, which have not been available until recently. We aimed to evaluate the effect of selection operating at the HLA haplotype level by analyzing HLA A~C~B~DRB1~DQB1 haplotype frequencies derived from over six million individuals genotyped by the National Marrow Donor Program registry. In contrast with alleles, HLA haplotype diversity patterns suggest purifying selection, as certain HLA allele combinations co-occur in high linkage disequilibrium. Linkage disequilibrium is positive (Dij'>0) among frequent haplotypes and negative (Dij'<0) among rare haplotypes. Fitting the haplotype frequency distribution to several population dynamics models, we found that the best fit was obtained when significant positive frequency-dependent selection (FDS) was incorporated. Finally, the Ewens-Watterson test of homozygosity showed excess homozygosity for 5-locus haplotypes within 23 US populations studied, with an average Fnd of 28.43. Haplotype diversity is most consistent with purifying selection for HLA Class I haplotypes (HLA-A, -B, -C), and was not inferred for HLA Class II haplotypes (-DRB1 and-DQB1). We discuss our empirical results in the context of evolutionary theory, exploring potential mechanisms of selection that maintain high linkage disequilibrium in MHC haplotype blocks.

MOTIVATION: Spatial learning is one of the most widely studied cognitive domains in neuroscience. The Morris water maze and the Barnes maze are the most commonly used techniques to assess spatial learning and memory in rodents. Despite the fact that these tasks are well-validated paradigms for testing spatial learning abilities, manual categorization of performance into behavioral strategies is subject to individual interpretation, and thus to bias. We have previously described an unbiased machine-learning algorithm to classify spatial strategies in the Morris water maze. RESULTS: Here, we offer a support vector machine-based, automated, Barnes-maze unbiased strategy (BUNS) classification algorithm, as well as a cognitive score scale that can be used for memory acquisition, reversal training and probe trials. The BUNS algorithm can greatly benefit Barnes maze users as it provides a standardized method of strategy classification and cognitive scoring scale, which cannot be derived from typical Barnes maze data analysis. AVAILABILITY AND IMPLEMENTATION: Freely available on the web at http://okunlab.wix.com/okunlab as a MATLAB application. CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

Measures of allele and haplotype diversity, which are fundamental properties in population genetics, often follow heavy tailed distributions. These measures are of particular interest in the field of hematopoietic stem cell transplant (HSCT). Donor/Recipient suitability for HSCT is determined by Human Leukocyte Antigen (HLA) similarity. Match predictions rely upon a precise description of HLA diversity, yet classical estimates are inaccurate given the heavy-tailed nature of the distribution. This directly affects HSCT matching and diversity measures in broader fields such as species richness. We, therefore, have developed a power-law based estimator to measure allele and haplotype diversity that accommodates heavy tails using the concepts of regular variation and occupancy distributions. Application of our estimator to 6.59 million donors in the Be The Match Registry revealed that haplotypes follow a heavy tail distribution across all ethnicities: for example, 44.65% of the European American haplotypes are represented by only 1 individual. Indeed, our discovery rate of all U.S. European American haplotypes is estimated at 23.45% based upon sampling 3.97% of the population, leaving a large number of unobserved haplotypes. Population coverage, however, is much higher at 99.4% given that 90% of European Americans carry one of the 4.5% most frequent haplotypes. Alleles were found to be less diverse suggesting the current registry represents most alleles in the population. Thus, for HSCT registries, haplotype discovery will remain high with continued recruitment to a very deep level of sampling, but population coverage will not. Finally, we compared the convergence of our power-law versus classical diversity estimators such as Capture recapture, Chao, ACE and Jackknife methods. When fit to the haplotype data, our estimator displayed favorable properties in terms of convergence (with respect to sampling depth) and accuracy (with respect to diversity estimates). This suggests that power-law based estimators offer a valid alternative to classical diversity estimators and may have broad applicability in the field of population genetics.

MOTIVATION: Many secondary messengers, receptors and transcription factors are related to cell differentiation. Their role in cell differentiation can be affected by their position in the gene regulatory network. Here, we test whether the properties of the gene regulatory network can highlight which genes and proteins are associated with cell differentiation. We use a previously developed purely theoretical algorithm built to detect nodes that can induce a state change in Boolean gene regulatory networks, and show that most genes predicted to participate in differentiation in the theoretical framework are also experimentally known to be associated with such differentiation. These results show that genes related to differentiation are associated with specific features of the genetic regulatory network. The proposed algorithm produces a better classification than simple network measures such as the nodes degree or centrality. Boolean networks were used in many previous theoretical models. Here, we show a direct application of such networks to the detection of genes and subnetworks related to differentiation. The subnetwork emerging from the genes and edges that are predicted to be associated with differentiation are the most active molecular pathways experimentally described to be involved in cell differentiation. AVAILABILITY AND IMPLEMENTATION: http://peptibase.cs.biu.ac.il/homepage/Boolean_network_conversion_code.zip.

The main adaptive immune response to bacteria is mediated by B cells and CD4+ T-cells. However, some bacterial proteins reach the cytosol of host cells and are exposed to the host CD8+ T-cells response. Both gram-negative and gram-positive bacteria can translocate proteins to the cytosol through type III and IV secretion and ESX-1 systems, respectively. The translocated proteins are often essential for the bacterium survival. Once injected, these proteins can be degraded and presented on MHC-I molecules to CD8+ T-cells. The CD8+ T-cells, in turn, can induce cell death and destroy the bacteria's habitat. In viruses, escape mutations arise to avoid this detection. The accumulation of escape mutations in bacteria has never been systematically studied. We show for the first time that such mutations are systematically present in most bacteria tested. We combine multiple bioinformatic algorithms to compute CD8+ T-cell epitope libraries of bacteria with secretion systems that translocate proteins to the host cytosol. In all bacteria tested, proteins not translocated to the cytosol show no escape mutations in their CD8+ T-cell epitopes. However, proteins translocated to the cytosol show clear escape mutations and have low epitope densities for most tested HLA alleles. The low epitope densities suggest that bacteria, like viruses, are evolutionarily selected to ensure their survival in the presence of CD8+ T-cells. In contrast with most other translocated proteins examined, Pseudomonas aeruginosa's ExoU, which ultimately induces host cell death, was found to have high epitope density. This finding suggests a novel mechanism for the manipulation of CD8+ T-cells by pathogens. The ExoU effector may have evolved to maintain high epitope density enabling it to efficiently induce CD8+ T-cell mediated cell death. These results were tested using multiple epitope prediction algorithms, and were found to be consistent for most proteins tested.

MOTIVATION: The topology of the network induced by the neurons connectivity's in the Caenorhabditis elegans differs from most common random networks. The neurons positions of the C.elegans have been previously explained as being optimal to induce the required network wiring. We here propose a complementary explanation that the network wiring is the direct result of a local stochastic synapse formation process. RESULTS: We show that a model based on the physical distance between neurons can explain the C.elegans neural network structure, specifically, we demonstrate that a simple model based on a geometrical synapse formation probability and the inhibition of short coherent cycles can explain the properties of the C.elegans' neural network. We suggest this model as an initial framework to discuss neural network generation and as a first step toward the development of models for more advanced creatures. In order to measure the circle frequency in the network, a novel graph-theory circle length measurement algorithm is proposed.

MOTIVATION: Viruses employ various means to evade immune detection. One common evasion strategy is the removal of CD8+cytotoxic T-lymphocyte epitopes. We here use a combination of multiple bioinformatic tools and large amount of genomic data to compute the epitope repertoire presented by over 1300 viruses in many HLA alleles. We define the 'Size of Immune Repertoire score', which represents the ratio between the epitope density within a protein and the expected density. This score is used to study viral immune evasion. RESULTS: We show that viral proteins in general have a higher epitope density than human proteins. This difference is due to a good fit of the human MHC molecules to the typical amino-acid usage of viruses. Among different viruses, viruses infecting humans present less epitopes than non-human viruses. This selection is not at the amino-acid usage level, but through the removal of specific epitopes. Within a single virus, not all proteins express the same epitopes density. Proteins expressed early in the viral life cycle have a lower epitope density than late proteins. Such a difference is not observed in non-human viruses. The removal of early epitopes and the targeting of the cellular immune response to late viral proteins, allow the virus a time interval to propagate before its host cells are destroyed by T cells.

MOTIVATION: An 8-10mer can become a cytotoxic T lymphocyte epitope only if it is cleaved by the proteasome, transported by TAP and presented by MHC-I molecules. Thus most of the epitopes presented to cytotoxic T cells in the context of MHC-I molecules are products of intracellular proteasomal cleavage. These products are not random, as peptide production is a function of the precise sequence of the proteins processed by the proteasome. RESULTS: We have developed a score for the probability that a given peptide results from proteasomal cleavage. High scoring peptides are those that are cleaved in their extremities and not in their center, while low scoring peptides are either cleaved in their centers or not cleaved in their extremities. The current work differs from most previous works, in that it determines the production probability of an entire peptide, rather than trying to predict specific cleavage sites. We further present different score functions for the constitutive and the immunoproteasome. Our results were validated to have low error levels against multiple epitope databases. We provide here a novel computational tool and a website to use it-http://peptibase.cs.biu.ac.il/PepCleave_II/ to assess the probability that a given peptide indeed results from proteasomal cleavage.

UNLABELLED: We study two kinds of networks: genetic regulatory networks and the World Wide Web. We systematically test microscopic mechanisms to find the set of such mechanisms that optimally explain each networks' specific properties. In the first case we formulate a model including mainly random unbiased gene duplications and mutations. In the second case, the basic moves are website generation and rapid surf-induced link creation (/destruction). The different types of mechanisms reproduce the appropriate observed network properties. We use those to show that different kinds of networks have strongly system-dependent macroscopic experimental features. The diverging properties result from dissimilar node and link basic dynamics. The main non-uniform properties include the clustering coefficient, small-scale motifs frequency, time correlations, centrality and the connectivity of outgoing links. Some other features are generic such as the large-scale connectivity distribution of incoming links (scale-free) and the network diameter (small-worlds). The common properties are just the general hallmark of autocatalysis (self-enhancing processes), while the specific properties hinge on the specific elementary mechanisms. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics Online.

Economic and cultural globalization is one of the most important processes humankind has been undergoing lately. This process is assumed to be leading the world into a wealthy society with a better life. However, the current trend of globalization is not unprecedented in human history, and has had some severe consequences in the past. By applying a quantitative analysis through a microscopic representation we show that globalization, besides being unfair (with respect to wealth distribution), is also unstable and potentially dangerous as one event may lead to a collapse of the system. It is proposed that the optimal solution in controlling the unwanted aspects and enhancing the advantageous ones lies in limiting competition to large subregions, rather than making it worldwide.