Search bioRxiv⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/300012

Connectivity Problems on Heterogeneous Graphs

Wu, J.·Khodaverdian, A.·Weitz, B.·Yosef, N.
View original source ↗Export metadata ↓

Abstract

BackgroundNetwork connectivity problems are abundant in computational biology research, where graphs are used to represent a range of phenomena: from physical interactions between molecules to more abstract relationships such as gene co-expression. One common challenge in studying biological networks is the need to extract meaningful, small subgraphs out of large databases of potential interactions. A useful abstraction for this task turned out to be the Steiner network problems: given a reference \"database\" graph, find a parsimonious subgraph that satisfies a given set of connectivity demands. While this formulation proved useful in a number of instances, the next challenge is to account for the fact that the reference graph may not be static. This can happen for instance, when studying protein measurements in single cells or at different time points, whereby different subsets of conditions can have different protein milieu.\n\nResults and DiscussionWe introduce the condition Steiner network problem in which we concomitantly consider a set of distinct biological conditions. Each condition is associated with a set of connectivity demands, as well as a set of edges that are assumed to be present in that condition. The goal of this problem is to find a minimal subgraph that satisfies all the demands through paths that are present in the respective condition. We show that introducing multiple conditions as an additional factor makes this problem much harder to approximate. Specifically, we prove that for C conditions, this new problem is NP-hard to approximate to a factor of C -{epsilon} , for every C [≥] 2 and{epsilon} > 0, and that this bound is tight. Moving beyond the worst case, we explore a special set of instances where the reference graph grows monotonically between conditions, and show that this problem admits substantially improved approximation algorithms. We also developed an integer linear programming solver for the general problem and demonstrate its ability to reach optimality with instances from the human protein interaction network.\n\nConclusionOur results demonstrate that in contrast to most connectivity problems studied in computational biology, accounting for multiplicity of biological conditions adds considerable complexity, which we propose to address with a new solver. Importantly, our results extend to several network connectivity problems that are commonly used in computational biology, such as Prize-Collecting Steiner Tree, and provide insight into the theoretical guarantees for their applications in a multiple condition setting.\n\nAvailabilityOur solver for the general condition Steiner network problem is available at https://github.com/YosefLab/condition_connectivity_problems

Source connections

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Wu, J., Khodaverdian, A., Weitz, B., Yosef, N.. 2018-04-13. Connectivity Problems on Heterogeneous Graphs. https://doi.org/10.1101/300012

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

PHATE-Derived Ancestry Coordinates Capture Continuous Population Structure in Human Genomic Data

Population genetic data are increasingly visualized using low-dimensional embeddings as ancestry coordinates, yet how these methods represent population structure can depend strongly on sampling and construction choices. Principal component analysis (PCA), when visualized using only leading components, can obscure fine-scale structure, while nonlinear neighbor-based methods such as uniform manifold approximation and projection (UMAP) often fragment geographic and admixture gradients into discrete clusters. Here, we introduce a framework for constructing ancestry coordinates using potential of heat-diffusion for affinity-based trajectory embedding (PHATE), a diffusion-based method that preserves relationships across scales. Across synthetic benchmarks and large genomic datasets, we show that appropriate scale tuning and population balancing allow PHATE to recover geographic organization and admixture gradients. We show that incorrectly tuned neighborhood scale and population imbalance can distort the resulting representations of population structure. These results therefore provide a methodological framework and practical guidance for constructing ancestry visualizations that better reflect continuous human genetic diversity.

bioinformatics↗
bioRxiv2026

FedEpitope: Parameter-Efficient Federated Protein Language Models for Linear B-Cell Epitope Prediction

Linear B-cell epitopes are antigenic regions recognised by antibodies that play crucial roles in vaccine development, antibody production, and other therapeutic applications.Their prediction can support peptide-based vaccine candidate screening and diagnostic assay development, but the experimental data required for model development may be distributed across institutions that cannot freely pool their records. We present FedEpitope, a federated framework that adapts the ESM-2 protein language model for peptide-level linear B-cell epitope prediction using Low-Rank Adaptation (LoRA), keeping client-partitioned data local and restricting the communicated trainable model state to approximately 1.11 MB. Simulated benchmarks of FedAvg and FedProx algorithms, evaluated using homology-aware data splits of five biologically heterogeneous, organism-partitioned clients, achieve promising global test performance without centralising training data, with FedAvg outperforming all single-client models in mean AP, F1, and MCC. Additional experiments characterise post-federation personalisation, record-level differential privacy, sensitivity to controlled client heterogeneity, LoRA rank, and generalisation to the independent BCPreds and NetBCE benchmarks, demonstrating the feasibility of parameter-efficient federated protein language model adaptation for data-localised B-cell epitope prediction and the associated trade-offs among predictive performance, personalisation, privacy, communication efficiency, and distribution shift.

bioinformatics↗
bioRxiv2026

Parameter-Efficient Adaptation of Protein Language Models for Dual-Target Antimicrobial Peptide Discovery Under Strict Homology Constraints

The worldwide escalation of antimicrobial resistance (AMR) poses a severe challenge to modern public health, necessitating novel classes of therapeutic agents. Antimicrobial peptides (AMPs) represent highly promising alternatives to small-molecule antibiotics due to their co-evolutionary resilience and rapid membrane disruption dynamics. However, translating computational AMP leads into clinical drug candidates remains bottlenecked by off-target cytotoxicity, predominantly hemolytic activity against mammalian erythrocytes. Although pretrained foundational protein language models (PLMs) have rapidly advanced molecular property prediction, current architectures frequently isolate antibacterial potency and cytotoxicity into disconnected single-task pipelines or succumb to catastrophic performance drops under strict homology-controlled evaluations. Recently, the Quantitative Mapping of Antimicrobial Peptides (QMAP) benchmark proposed that frozen PLM embeddings show weak linearly accessible features for hemolytic activity (HC50) resulting in poor rank correlation ({rho} < 0.25) on out-of-distribution sequence splits. In this work, we introduce an end-to-end multi-task parameter-efficient transfer learning framework designed to simultaneously optimize antibacterial potency and minimize mammalian cytotoxicity without sequence leakage. Built upon ESM-2 (150M), our architecture incorporates Low-Rank Adaptation (LoRA) into self-attention projections, fine-tuning approx 0.70% of model weights. To restore gradient interference originating from disparate membrane lysis mechanisms, we implement an adaptive multi-task loss guided by Kendall homoscedastic uncertainty weighting. Evaluated across predefined QMAP benchmark splits enforcing a 60% maximal sequence identity threshold, our joint architecture remarkably outperforms conventional linear probes, tree-based regressors, and frozen foundational models. The framework achieves an E. coli potency rank correlation of {rho} = 0.6132 (r = 0.6816) and successfully elevates hemolytic toxicity correlation to {rho} = 0.5374 (r = 0.5541). To establish real world utility, we deploy the optimized joint network to screen a curated in silico library of 749 de-novo designed peptides, successfully isolating selective cationic-amphipathic candidates possessing Therapeutic Indices (TI = HC50/MIC) up to 144.03 while effectively deprioritizing broadly lytic motifs (TI < 2.0). These findings demonstrate that parameter-efficient adaptation unlocks fine-grained bioactive structural semantics in foundational PLMs, providing an accurate, scalable framework for therapeutic peptide engineering.

bioinformatics↗