# Molecular Subtyping and Outlier Detection in Human Disease Using the Paralique Algorithm
## 1 Introduction  
It has long been established that many disease families exhibit a wide range of heterogeneity. This is especially true in cancer. Lung cancers, for example, fall into two overall types based on histological characteristics: small cell lung cancer (SCLC) and non-small cell lung cancer (NSCLC). Although histological classification remains crucial, significant advances in the treatment of NSCLC over the last decade have centered around the development of therapies targeting subtypes at the molecular level, such as those defined by genetic mutations [1]. In particular, therapies targeting alterations in the epidermal growth factor receptor (EGFR) and anaplastic lymphoma kinase (ALK) genes have produced dramatic improvements in outcomes for patients in the underlying subgroups [2, 3]. In addition to providing new paths for treatment, advances in molecular subtyping allow practitioners to avoid needless high-risk therapies. For example, studies have identified transcriptomic signatures for chemo-resistance in both acute myeloid leukemia and breast cancer [4, 5]. Recent research has made positive steps towards targeted care for a variety of diseases, including Asthma, Alzheimer's, and Crohn's disease [6, 7, 8]. A key development driving these advances is the successful identification of molecular subtypes. Given the potential impact of disease subtype identification, it is not surprising therefore, that the search for effective clustering methods has become an intense area of interest. Traditional approaches, such as \(k\)-means and hierarchical clustering, have long been used to identify sets of genes or samples that exhibit similar expression patterns [9, 10, 11]. Machine learning techniques based on neural networks have been investigated as well [12, 13, 14]. Latent variable and mixture models have also been used [15, 16, 17]. Meanwhile, a graph theoretical approach is to model a set of genes or samples as vertices in a graph, with edges connecting them based on thresholding some similarity metric. A systematic comparison of clustering methods over well-annotated _S. cerevisiae_ (baker's yeast) gene co-expression data can be found in [18], where it was shown that clique-centric graph theoretical algorithms generally outperform other approaches. Moreover, the top-down paraclique algorithm(see Supplementary Materials) introduced in [19] was found to possess considerable computational advantages over other clique-based tools. Maximal clique [20], for example, is output bound, while k-clique communities [21] are hobbled by bottom-up inefficiencies. Paraclique has seen prior application in transcriptomics [22], proteomics [23], epigenetics [24] and the exposome [25], as well as in the study of specific diseases including lung cancer [26], diabetes [27], allergic rhinitis [28] and community-acquired pneumonia [29], and even in investigations of the effects of radiation on living organisms [30]. Nevertheless, to the best of our knowledge, this paper represents the first attempt to gauge paraclique's potential merit in the context of molecular disease subtyping. To address this gap, we describe an initial study of putative subtypes based on molecular signatures using the paraclique method. Our technique is general and applies easily to other types of data such as protein interaction, metabolite abundance, or DNA methylation profiles, but we focus our experimentation on gene co-expression data thanks to its relative quality and ubiquity. In addition to subtype discovery, we will show how our techniques can be used to help pinpoint potential outliers, providing an automatic means for the identification of suspected data collection errors such as mislabeled samples or misdiagnosed patients. We hasten to observe, however, that biological variation can be incrutable, inconsistent, and unpredictable. No method is therefore likely to be extraordinarily accurate. We will address this and related issues in the sequel. This paper is organized as follows.