Data Mining for Biologists

Data Mining for Biologists

Koji Tsuda (Max Planck Institute for Biological Cybernetics, Germany)
Copyright: © 2009 |Pages: 14
DOI: 10.4018/978-1-60566-398-2.ch002
OnDemand PDF Download:
No Current Special Offers


In this tutorial chapter, the author reviews basics about frequent pattern mining algorithms, including itemset mining, association rule mining, and graph mining. These algorithms can find frequently appearing substructures in discrete data. They can discover structural motifs, for example, from mutation data, protein structures, and chemical compounds. As they have been primarily used for business data, biological applications are not so common yet, but their potential impact would be large. Recent advances in computers including multicore machines and ever increasing memory capacity support the application of such methods to larger datasets. The author explains technical aspects of the algorithms, but do not go into details. Current biological applications are summarized and possible future directions are given.
Chapter Preview


As new techniques for obtaining biological data continue to be introduced and a huge amount of data is accumulated in a large number of databases, the importance of data mining is ever increasing (Han & Kamber 2000). Modern high throughput technologies create comprehensive information about genome sequences, gene expression, polymorphism, protein interactions etc. However, extracting important information is not a trivial task. It is not only because of the huge amount of data. It is hard to define what is the important information in a current context mathematically. In collaboration among computer scientists and biologists, clear definition of the task is the key to success. It is often the case that computer scientists require biologists to define the mathematical definition of what they want from data. For example, it might be a statistical classifier predicting some phenotype from SNP data. But when biologists do not have sufficient knowledge about data mining methods, or computer scientists do not understand the biologists’ motivation well, such collaboration might end up in failure. One typical failure is to define an impossible task which cannot be solved by any reasonable data mining method. This tutorial chapter is supposed to give computational biologists some background knowledge about data mining methods.

There are many different classes of methods in data mining. Most popular ones include clustering, supervised classification, regression, sequence alignment etc. There are good introductory books about data mining methods in biology, for example, (Schoelkopf et al., 2004). In this chapter, we cannot focus on all techniques, but concentrate on frequent pattern mining algorithms and their possible applications to biological data.

The most popular method of pattern mining algorithms is itemset mining (Agrawal & Srikant, 1994), which has been extensively applied to market basket analysis. Suppose a supermarket welcoming many customers every day. Each customer buys more than one item. When each item is indexed by an integer, each transaction (i.e., the items bought by a customer) is summarized as a set of integers (Figure 1). Then, the goal of itemset mining is to enumerate the subsets of items which occurred in more than m transactions. The frequency threshold m is called the minimum support parameter. Found subsets are called patterns. In a popular example of market basket analysis, it is discovered that beer and diaper are likely to be sold simultaneously. The frequent co-occurrence of two items is considered as very strong signal of association between them. Biological objects are often represented as an itemset. For example, a promoter sequence can be represented as a set of sequence motifs. A patient is a set of genotypes at several quantitative loci. Applications to gene expression data can be seen, e.g., in (Creighton & Hanash, 2003; Tamura and D’haeseleer, 2008).

Figure 1.

Examples of frequent itemsets


The idea of frequently appearing substructure is commonly exploited in sequence motif analysis (Bailey et al., 2006). Their objective is to find a frequently appearing substring from a set of strings. One point which discriminates motif analysis from frequent pattern mining is that the motif analysis finds only one motif at a time, whereas frequent pattern mining enumerates all frequently appearing patterns. For example, MEME (Bailey et al., 2006) can derive a probabilistic motif from a set of k-mers. Even though there are many possible motifs, it can extract one motif because it is based on a mixture model of two components, one of which is the background model. It could be extended to deal with multiple motifs by increasing the number of components, but then the optimization of parameters gets more difficult (Blekas et al., 2003).

Complete Chapter List

Search this Book: