English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Mining groups of genes that consistently co-express is an important problemin biomedical research, where it is critical for applications such asdrug-repositioning and designing new disease treatments. Recently, Cooley etal. modeled this problem as Exact Weighted Clique Decomposition (EWCD) inwhich, given an edge-weighted graph $G$ and a positive integer $k$, the goal isto decompose $G$ into at most $k$ (overlapping) weighted cliques so that anedge's weight is exactly equal to the sum of weights for cliques itparticipates in. They show EWCD is fixed-parameter-tractable, giving a$4^k$-kernel alongside a backtracking algorithm (together called cricca) toiteratively build a decomposition. Unfortunately, because of inherentexponential growth in the space of potential solutions, cricca is typicallyable to decompose graphs only when $k \leq 11$.  In this work, we establish reduction rules that exponentially decrease thesize of the kernel (from $4^k$ to $k2^k$) for EWCD. In addition, we useinsights about the structure of potential solutions to give new search rulesthat speed up the decomposition algorithm. At the core of our techniques is aresult from combinatorial design theory called Fisher's inequalitycharacterizing set systems with restricted intersections. We deploy ourkernelization and decomposition algorithms (together called DeCAF) on a corpusof biologically-inspired data and obtain over two orders of magnitude speed-upover cricca. As a result, DeCAF scales to instances with $k \geq 17$.

Faster Decomposition of Weighted Graphs into Cliques using Fisher's Inequality