Significant Pattern Mining
Data Mining, the search for new knowledge in form of statistical dependencies and patterns in big data sets, is omnipresent in modern society, in science and technology as much as in industry and finance. One of its most important branches is Pattern Mining, that is finding groups of co-occuring elements in a collection of sets. For instance, keywords that co-occur in many documents may form a pattern, or groups of atoms that reoccur in molecules with a particular biological function. Data Mining has brought about a huge body of literature on how to efficiently discover such patterns, even in very large datasets.
An unresolved open question is, however, to decide whether a given pattern is not only frequent, but statistically significantly enriched in a particular dataset or class of objects. This question is of essential relevance to all application domains of pattern mining, in particular the life sciences, as they are interested in selecting patterns for further experimental investigation and validation. It is one of our research goals to give an answer to this open problem of significant pattern mining.
Publications
Below you can find a list of our projects on this topic.
Software
We have developed several algorithms and software packages for significant pattern mining:
CASMAP
While the majority of prior work in association mapping searches for univariate or additive associations between genotype and phenotype, combinatorial association mapping instead aims to discover statistically significant higher-order interactions of genetic markers. In recent years, our group has been at the forefront of the development of new techniques for combinational association mapping, which span multiple publications.
In order to make our work in this domain more accessible to practitioners, we have developed CASMAP, a new software package for combinatorial association mapping in genome-wide association studies. Available both in Python and R, CASMAP allows users to easily carry out region-based association studies and to search for higher-order epistatic interactions of binary markers while correcting for the effect of categorical covariates.
The algorithm is available in our GitHub repository here.
FastCMH
The Fast Cochran-Mantel-Haenszel (FastCMH) algorithm discovers genomic regions of contiguous SNPs that are associated to a phenotype of interest under a model of genetic heterogeneity. It can search any contiguous set of SNPs in the genome while still properly correcting for mutiple testing and accounting for confounding factors.
The algorithm is available in our GitHub repository here. It is also included in the CASMAP software package.
FACS
The Fast Automatic Conditional Search (FACS) algorithm is a significant discriminative itemset mining method which conditions on categorical covariates and only scales as O(k log k), where k is the number of states of the categorical covariate. Based on the Cochran-Mantel-Haenszel Test, FACS demonstrates superior speed and statistical power on simulated and real-world datasets compared to the state of the art, opening the door to numerous applications in biomedicine.
The algorithm is available in our GitHub repository here. It is also included in the CASMAP software package.
Westfall-Young Light
Westfall-Young Light is a significant pattern mining algorithm that uses permutation-testing to account for the presence of redundant patterns, leading to an increase in statistical power. It uses a novel approach to apply permutation-testing in pattern mining, resulting in an algorithm that is drastically faster than prior work and which also requires considerably less memory to run.
The algorithm is available in our GitHub repository here.
Significant Subgraph Mining with Multiple Testing Correction
The algorithm is available in our GitHub repository here.
FAIS
The Fast Automatic Interval Search (FAIS) algorithm discovers contiguous sets of SNPs in a genome that are associated to a phenotype of interest under a model of genetic heterogeneity. It can search any contiguous set of SNPs in the genome and still properly correct for mutiple testing, while retaining statistical power.
The algorithm is available in our GitHub repository here. It is also included in the CASMAP software package.
Presentations
In the following you can find the slides from several talks we have given on this topic.
- Karsten Borgwardt in at the ISCVID Symposium in Lausanne (04.06.2019): Machine Learning for Personalized Medicine
- Karsten Borgwardt at the '15th Current Topics in Bioinformatics' symposium at MDC Berlin (20.05.2019): Machine Learning for Biomarker Discovery in Clinical Time Series (PDF, 9.2 MB)
- Karsten Borgwardt at the Siemens Healthineers Summit in Zürich (14.03.2019): Dr. Algorithmus - wie KI die Medizin verändert
- Karsten Borgwardt at Roche Basel (19.02.2019): Machine Learning for Personalized Medicine (PDF, 9.7 MB)
- Karsten Borgwardt at the IMM seminar at the University of Zürich (25.10.2018): Machine Learning for Personalized Medicine (PDF, 4.2 MB)
- Karsten Borgwardt at the Huawei-ETH workshop in Zürich (25.05.2018): Machine Learning for Biomarker Discovery (PDF, 3.9 MB)
- Karsten Borgwardt at Roche Basel (18.04.2018): Machine Learning for Biomarker Discovery (PDF, 3.9 MB)
- Karsten Borgwardt at the SFB/TRR 209 seminar at the University Hospital Tübingen (16.04.2018): Machine Learning for Biomarker Discovery: Combinatorial Association Mapping (PDF, 3.9 MB)
- Karsten Borgwardt at the seminar series 'Software Trends' at Hochschule Esslingen (13.04.2018): Die 'Daten-Medizin' (PDF, 3.6 MB)
- Karsten Borgwardt at the Fassberg Seminar Series at MPI Göttingen (13.03.2018): Data Mining in the Life Sciences: Combinatorial Association Mapping (PDF, 3.9 MB)
- Karsten Borgwardt at Google Research Zürich (27.02.2018): Machine Learning in Medicine: Combinatorial Association Mapping (PDF, 3.8 MB)
- Karsten Borgwardt at the DPPH Meeting in Lausanne (15.02.2018): Personalized Swiss Sepsis Study (PDF, 2.7 MB)
- Karsten Borgwardt at the SIB Virtual Computational Biology Seminar Series (20.9.2017): Significant Pattern Mining for Combinatorial Association Mapping
- Karsten Borgwardt at the Distinguished Speaker Series at the Center for Bioinformatics, Saarbrücken (10.5.2017): Combinatorial Association Mapping (PDF, 2.2 MB)
- Karsten Borgwardt at IBT seminar at the Institute for Biomedical Engineering at ETH Zürich (25.4.2017):
Network Mining in Biology and Medicine (PDF, 2.3 MB) - Karsten Borgwardt at the Felix Klein Conference "Mathematical Methods in Big Data" at the Fraunhofer Institute for Industrial Mathematics ITWM in Kaiserslautern (30.09.2016): Machine Learning for Personalized Medicine (PDF, 8.7 MB) (from slide 46)
- Felipe Llinare López at Krupp symposium 2017 (21.10.2016): Significant Pattern Mining for Biomarker Discovery (PDF, 14.3 MB)
- Karsten Borgwardt at the ECCB workshop on "Complex Network Analysis for Precision Medicine" in The Hague (03.09.2016): Network Mining for Personalized Medicine (PDF, 2 MB)
- Karsten Borgwardt at the Computational Biology (BC2) seminar at the Biozentrum at the University of Basel (25.04.2016): Machine Learning for Personalized Medicine (PDF, 7.2 MB) (in particular slide 18ff)
- Karsten Borgwardt at the Computer Science Colloquium of the University of Basel (21.04.2016): Significant Pattern Mining (PDF, 6.1 MB)
- Karsten Borgwardt at TU Dortmund (12.11.2015): Significant Pattern Mining (PDF, 6.1 MB)
- Keynote lecture by Karsten Borgwardt at meeting of the Competence Center for Personalized Medicine of ETH Zürich & the University of Zürich at Kartause Ittingen. (02.11.2015): Machine Learning for Personalized Medicine (PDF, 7.2 MB) (in particular slide 18ff)
Part of this work was funded by the SNSF Starting Grant “Significant Pattern Mining”.