Network-based methods to identify highly discriminating subsets of biomarkers

To identify highly discriminating biomarkers for better disease prognosis and diagnosis, we present two new network-based methods that search for the cliques with the maximum node and edge weights that integrate both individual discriminating power and pairwise synergistic interactions. Under this novel framework of Maximum Weighted Multiple Clique Problem (MWMCP), we have derived the first analytical algorithm based on column generation method for its optimal solution. We also have developed a sequential heuristic solution for large-scale networks. In a preliminary study of immunologic and metabolic indices regarding the development of Type-1 Diabetes (T1D) from the Diabetes Prevention Trial-Type 1 (DPT-1) study, we have shown that the proposed methods can identify important biomarkers for T1D onset.