A SPECTRAL-GEOMETRIC FRAMEWORK FOR NON-REDUNDANT DRUG TARGET SELECTION VIA THE WEIGHTED LOV´ ASZ THETA FUNCTION

Abstract

Identifying non-redundant therapeutic target combinations in Mycobacterium tuberculosis is both a pressing clinical problem, driven by obligate multi-drug regimens and escalating resis tance. This is a natural instance of the maximum weighted independent set (MWIS) problem on a biologically structured graph. We present a spectral-geometric framework that formalises this correspondence and exploits it computationally. From the Mtb H37Rv protein-protein in teraction (PIP) network, constructed by integrating multiple experimental evidence sources, we derive a composite target relevance score encoding Tn-seq essentiality, structural drugga bility, and host-specificity. Embedding the network spectrally through the graph Laplacian, we construct a target-interference graph Hω =(U,Fω) by connecting candidate proteins whose pairwise spectral distance falls below a threshold ω, encoding functional proximity as the in terference relation. The weighted Lov´asz theta function ε( ¯ Hω,p) then provides a polynomial time SDP upper bound on the MWISofHω, witharounded solution approximating the optimal non-redundant target combination. We establish that when Hω is constructed from the Fiedler coordinate alone, it is an interval graph and therefore perfect. By the Lov´asz sandwich theorem, ε( ¯Hω,p)=ϑ(Hω,p) exactly, and the SDP solves the weighted target selection problem in poly nomial time. For embeddings of dimension k → 2, Hω is a unit ball intersection graph in Rk and we characterise the resulting integrality gap as a function of k, establishing a formal trade-off between spectral expressiveness and algorithmic tractability. Applied to the Mtb H37Rv inter actome, the SDP-rounded target sets recover established drug targets, including KatG, InhA, and DprE1, within the computed independent set, and the identified combinations span func tionally disjoint subsystems encompassing cell wall biosynthesis, central carbon metabolism, and DNA replication, consistent with the network-pharmacological rationale underlying com bination anti-TB therapy.