Machine Learning Approaches to Bioinformatics

The following sections are included:

• Preface

• Contents

The following sections are included:

• Brief history of bioinformatics

• Database application in bioinformatics

• Web tools and services for sequence homology alignment
  • Web tools and services for protein functional site identification
  • Web tools and services for other biological data

• Pattern analysis

• The contribution of information technology

• Chapters

In many real-world applications, available data may have little domain knowledge (signature) associated, for instance, the data structure and the inference rule of a data set may be missing or yet to be discovered. Such a data set is categorised as incomplete data for which inference on novel data becomes difficult. In order to make data, particularly experimental data, useful for inference it is necessary to explore signatures for a data set, which should fit well the inference purposes. For instance, a mass spectrometry experiment on a set of plant samples can generate many thousands metabolites. Each metabolite is represented by a mass and a number of abundance values for replicates. Based on masses we can infer a number of the chemical formulas of candidate compounds from different pathways. In theory, one mass corresponds to one compound. However one metabolite may be mapped to multiple compounds. A selection process is commonly conducted manually in a laboratory to identify the true compound of the metabolite. A manual verification is prone to error and is also cost demanding. An automatic process can therefore be helpful to cover these two issues. It is understood that molecules in the same pathway should have similar responses to the treatment induced in an experiment. It is possible to study the clusters of metabolites according to abundance values. If some metabolites in a cluster have definite compound/pathway annotations, a metabolite with multiple mappings in the same cluster can then be identified. Another example in studying metabolite data is the identification of a proportion of important metabolites which can discriminate between experimental and control groups of samples. To fulfil this purpose, we can model the density functions of the differential intensities of metabolites from the experimental and control groups. By setting a threshold, say 1%, we can identify a subset of the most important metabolites for discrimination…

The importance of density estimation has been discussed in the last Chapter. In this Chapter, the relevant algorithms and their applications to bioinformatics are detailed. The simplest approach, called the histogram approach, is introduced at the beginning. Further discussion then follows towards three categories. First, a parametric approach is introduced with which we assume that data follow a Gaussian distribution as a hidden or missing data structure and two parameters (a mean and a standard deviation) as the inference rule of it are estimated.

Second, two non-parametric approaches are discussed. In contrast to parametric approaches, non-parametric approaches do not try to explore the explicit form of a data structure for a data set. The inference rule is therefore algorithm-oriented. Third, a semi-parametric approach is also introduced. Unlike parametric and non-parametric approaches, semi-parametric approaches explore a flexible data structure with inference rules for future decision making. For each of these three categories, a number of applications will be discussed. The data used for learning is referred to as training data.

Dimension reduction is a technique widely used in many applications. The main objective is to reveal data structure which is hard to obtain from a high-dimensional space through mapping the high-dimensional space to a low-dimensional space. The mapping is commonly conducted by a machine learning algorithm which uses various metrics and various learning strategies. After learning, the new space is commonly 2-dimensional (or 3-dimensional); working in this space we can study how data are clustered and how clusters are mutually correlated. This then provides a basis for further studies including classification analysis, knowledge extraction and hypothesis generation. In this chapter, we discuss two basic dimension reduction algorithms. Importantly, their difference and strengths will be emphasised. The applications to bioinformatics projects are demonstrated as well.

This chapter focuses on one fundamental issue in analysing biological data, i.e. how to find scientific laws which are hidden in data. Grouping and partitioning data are two very powerful approaches for discovering relevant biological regulations which can then be used in late hypothesis verification. In machine learning, such an approach is called cluster analysis, a type of unsupervised learning approach. The grouping data approach puts the emphasis on data relationship reconstruction i.e. exploring how data are clustered through a learning process. Partitioning data, on the other hand, is to discover hidden data structure through a learning process. Compared with the grouping data approach, the partitioning data approach puts the emphasis on a comprehensive data structure and the predictive capability of the discovered data structure. In this chapter, four fundamental clustering algorithms are introduced and their applications to bioinformatics are demonstrated. The four algorithms are the hierarchical clustering approach, the K-means algorithm, the fuzzy C-means algorithm, and the mixture models.

In the previous two chapters, data reduction (visualisation) and data partitioning algorithms were discussed. A data reduction algorithm may not provide data for data partitioning while a data partitioning algorithm may not visualise data. Self-organising map (SOM) is a neural learning algorithm which is able to combine two categories of algorithms into one system. In this chapter, we study the basic structure and learning rules of SOM. Because SOM has a close relationship to vector quantization, we first introduce vector quantization in this chapter. Demonstrations and case study are also given in relevant places.

Supervised learning is a subject in which a model is estimated from data for mapping explanatory variables to predictive variables. The explanatory variables in bioinformatics often refer to genotypic data which are used to describe underlying properties of a set of molecules within an organism. The predictive variables in bioinformatics are often used to describe phenotypic data which are observed. One of the most important targets in scientific research is to explain phenotypic phenomenon using genotypic data. This is very similar to most of our human intelligence activities, i.e. finding reasons that explain observed events, for instance, interpreting what causes the climate to change, understanding the genetic reasons leading to aging disease, deducing the underlying regulation of the financial market, and studying species diversity. Supervised learning is then searching for the most appropriate explanatory variables for interpreting predictive variables using a model. Such a model is often called a predictive model. Whenever such a model is established, its predictive function can be used for inference. This chapter focuses on the general concept of supervised learning. The discussion covers general concepts, rules, data organisation, model evaluation, and model feasibility.

In this chapter, two important machine learning approaches which can be used for supervised learning are introduced. One is called discriminant analysis including linear discriminant analysis and quadratic discriminant analysis and the other is called the K-nearest neighbour algorithm. Linear or quadratic discriminant analysis is a simple learning algorithm which has the advantages of simplicity and intuitiveness. The K-nearest neighbour algorithm has the advantage of low learning cost. This chapter will discuss the principles of these algorithms and the procedures of their applications to bioinformatics.

This chapter discusses one typical supervised learning approach. This type of algorithms aims to mimic human-like decision-making systems for specific applications. The popularity of this type of algorithms results from its simplicity and intuitiveness. A model built this way enjoys some distinct features in interpreting predictions and displays data structures which are very welcome in many applications.

This chapter mainly discusses multi-layer perceptron (MLP) for supervised learning. Compared with many other nonlinear artificial neural learning algorithms, it has the advantages of modelling arbitrary nonlinear data. MLP has been widely used in many applications including bioinformatics. This chapter will focus on the history of MLP, the structure of MLP, the learning algorithm of MLP and its applications to bioinformatics.

This chapter will discuss two popular machine learning approaches. They are basis function neural networks and vector machine algorithms. These two approaches have a similar background in machine learning, i.e. being non-parametric approaches for model construction. However, they have a fundamental difference in that the former will keep all the training data but the latter will use part of the training data for the inference process. This fundamental difference has given vector machine models better generalisation capability for unseen data. Their applications to bioinformatics are discussed as well in this chapter.

This chapter discusses the hidden Markov model (HMM) which can be used to explore hidden series states for a sequence of observations. The basic principle and learning algorithm are discussed. The Markov model is discussed first as it provides the basis for understanding the hidden Markov model. Three basic tasks of HMM are discussed. They are the likelihood evaluation, decoding or prediction, and model parameter learning. Applications to bioinformatics are discussed as well.

Feature selection has long been studied in machine learning [376-379]. When analysing gene expression data and metabolite data it is common that a data set has a few samples with many genes or metabolites as variables. In order to focus on some highly differentially expressed genes or active metabolites for investigating biological insight, a feature selection process must be considered. The main task of feature selection is to reduce the number of features while maintaining or improving model predictive capability. This chapter discusses three types of feature selection strategy. The first is the built-in strategy. The second is the exhaustive strategy. The third is the heuristic strategy. The built-in strategy embeds a feature selection process in model construction. The typical algorithms include principal component analysis, the classification and regression tree as well as the random forest algorithm plus three other algorithms discussed in this chapter. The exhaustive strategy is to exhaust all possible models with different features and then select a model with the smallest number of features and best model performance. The evaluation is commonly based on AIC or BIC discussed in chapter 5. The heuristic strategy selects features step by step using an additive performance measure. This strategy includes forward and backward selection.

To present a biological data set to a machine learning model, we are required to make sure that the data are representative, quantitative, and informative. This requires four focal points. First, the process must be as consistent as possible, i.e. providing invariant format and required resolution at any time. Second, the process must be as accurate as possible, i.e. if a new process is able to explore more information from biological data, it should replace the old one. Third, the process must be as effective as possible, i.e. taking into account the machine learning time cost. Fourth, the process should use as much biological knowledge as possible for the presentation of biological data. This process is similar to most applications in other disciplines and is called feature extraction. Note that feature extraction is often confused with feature selection. Feature selection is mainly to reduce noise in data by removing irrelevant variables in learning. However, feature extraction is to find a better way to present data to machine learning algorithms. Feature extraction is commonly a process done prior to feature selection. Unlike feature selection which is closely related to machine learning, feature extraction is closely related to subjects. Different disciplines will need different feature extraction approaches. This is why feature extraction is hardly a hot subject in machine learning. Rather, it is an important subject in some areas, such as image analysis, ECG signal processing, and sensor data analysis. We use a separate chapter for biological feature extraction to emphasise the importance of this topic in bioinformatics. In this chapter, the targets are molecular sequences and chemical compounds which are generally a chain of non-numerical components.

In this chapter we discuss the foundation of sequence/structural bioinformatics through peptide classification. The discussion is conducted by covering two different applications. They are posttranslational modification site prediction and promoter region identification. Although they are very different in nature, the basic concept is to look at local regions (or segments or peptides) to study functionality of a molecule. The aim of the chapter is to demonstrate how to conduct independent bioinformatics research using machine learning algorithms through feature extraction, feature selection, model construction, model evaluation, and model selection.

A traditional point of view of structure-function relation is

It is argued that this simple flow is too reductionistic [490]. This is because any biological function is completed by a network of molecules in a cell. A network is always composed of complicated interactions among molecules in a cell. Even more complicated are the dynamics of the interactions, some being more transient and some taking more time to complete. The complexity can increase when crosstalk happens unexpectedly. The post-genomic approach towards studying biological functions has a new flow expression as below [490] A gene network is a typical one among various molecular networks. This chapter focuses on the topic of causal network construction and the concept of Bayesian network.

Biochemical System Theory (BST) defines a mathematical model to study the dynamics of a biochemical system. The theory was introduced by Mike Savageau in the 1960s. Using BST to study a biochemical system does not need equations defining the exact mechanism of reactions. In a BST model, the relation between reactants and regulatory interactions is modelled by the power-law theory. The approach is referred to as S-systems or generalised mass action (GMA). There are two subjects closely related to S-system research. The first is how to learn the structure of an S-system given data. The second is how to learn system parameters given an S-system structure.

Although bioinformatics has been well-developed for a few decades with the enhancement of machine learning approaches, there are still some challenges. Many of these result from the gap between fast technology development and slow software development. For instance, the next-generation sequencing technology can speed up sequencing, but leaves a problem of fragment errors and sequence assembly. This is because fragment assembly algorithms have to be adapted to handle very short fragments. This kind of issue is related to computing skills and parallel computing concept and will not be discussed in this book. However, in using machine learning algorithms for modelling biological data, we also have many challenges. The most typical ones are the multi-source data and data size. Most machine learning algorithms deal with single-source data. Systems biology research, which is one of the major research themes this century, aims to analyse a biological system systematically. Multiple data sources certainly need consideration. The data size is always a huge challenge in bioinformatics. Handling hundreds of thousands or millions of DNA fragments for species diversity study is an example. Even modern computers still face challenges in modelling entire data and some specific data treatment has to be introduced. One such treatment is to lose possible resolution, for instance reducing 64 bits to 32 bits for representing numerical data. Gene expression data analysis for cancer diagnosis and drug development is also a challenge in using machine learning approaches for bioinformatics. One of the challenges in this area is to deal with heterogeneity in data. Most existing algorithms assume homogeneity in data and have missed one important issue in cancer diagnosis that each patient may develop a distinct biochemical system to develop cancer disease. Ignoring such heterogeneity may lead to the developed drug being hardly applicable to a large variety of patients. How to handle this challenge has been one of the most important subjects of the century. In this chapter we discuss these typical challenges in bioinformatics.

The following sections are included:

• References

• Index