Machine Learning & Computational Biology Lab

Search

EN

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.

Cover Bioinformatics journal

Thomas Gumbsch, Christian Bock, Michael Moor, Bastian Rieck, and Karsten Borgwardt

external page Enhancing statistical power in temporal biomarker discovery through representative shapelet mining

Cover of the Bioinformatics journal

Anja C. Gumpinger, Bastian Rieck, Dominik G. Grimm, International Headache Genetics Consortium, and Karsten M. Borgwardt

external page Network-guided search for genetic heterogeneity between gene pairs (Bioinformatics 2020)

Cover of the "Analyzing Network Data in Biology and Medicine: An Interdisciplinary Textbook for Biological, Medical and Computational Scientists"

Felipe Llinares-Lopez and Karsten Borgwardt

external page Machine Learning for Biomarker Discovery: Significant Pattern Mining (in "Analyzing Network Data in Biology and Medicine: An Interdisciplinary Textbook for Biological, Medical and Computational Scientists" 2019)

Cover of the Bioinformatics journal

Felipe Llinares-Lopez, Laetitia Papaxanthos, Damian Roquiero, Dean Bodenham and Karsten Borgwardt

CASMAP: Detection of statistically significant combinations of SNPs in association mapping (Bioinformatics 2018)

Cover of the Bioinformatics journal

Christian Bock, Thomas Gumbsch, Michael Moor, Bastian Rieck, Damian Roquiero and Karsten Borgwardt

external page Association Mapping in Biomedical Time Series via Statistically Significant Shapelet Mining (ISMB and Bioinformatics 2018)

Cover of the Bioinformatics journal

Felipe Llinares-Lopez, Laetitia Papaxanthos, Dean Bodenham, Damian Roqueiro, COPDGene Investigators and Karsten Borgwardt

Genome-wide genetic heterogeneity discovery with categorical covariates (Bioinformatics 2017)

Enlarged view: NIPS logo

Laetitia Papaxanthos, Felipe Llinares-López, Dean Bodenham and Karsten Borgwardt

Finding significant combinations of features in the presence of categorical covariates (NIPS 2016)

Enlarged view: KDD logo

Felipe Llinares-López, Mahito Sugiyama, Laetitia Papaxanthos and Karsten Borgwardt

Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing (SIGKDD 2015)

Enlarged view: Logo of SIAM Data Mining 2015

Mahito Sugiyama, Felipe Llinares López, Niklas Kasenburg and Karsten Borgwardt

external page Significant Subgraph Mining with Multiple Testing Correction (SIAM Data Mining 2015)

Enlarged view: Cover of the Bioinformatics journal

Felipe Llinares-López, Dominik G. Grimm, Dean A. Bodenham, Udo Gieraths, Mahito Sugiyama, Beth Rowan and Karsten Borgwardt

Genome-wide detection of intervals of genetic heterogeneity associated with complex traits (Bioinformatics/ISMB 2015)

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 external page 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 external page 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 external page 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 external page here.

Significant Subgraph Mining with Multiple Testing Correction

The algorithm is available in our GitHub repository external page 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 external page 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.

Team

The following members of the MLCB lab have been working on Significant Pattern Mining:

  • Christian Bock (alumnus)
  • Karsten Borgwardt
  • Thomas Gumbsch
  • Anja Gumpinger (alumna)
  • Max Horn (alumnus)
  • Felipe Llinares López (alumnus)
  • Michael Moor (alumnus)
  • Laetitia Papaxanthos (alumna)
  • Bastian Rieck (alumnus)
  • Damian Roqueiro (alumnus)
  • Dean Bodenham (alumnus)
  • Xiao He (alumnus)
  • Mahito Sugiyama (alumnus and collaborator)

Part of this work was funded by the SNSF Starting Grant “Significant Pattern Mining”.