Information Technology Journal

Year: 2012 | Volume: 11 | Issue: 1 | Page No.: 134-140
DOI: 10.3923/itj.2012.134.140

A Novel Pattern Recognition Approach Based on Immunology

Shulin Liu, Yinghui Liu, Youfu Tang and Ruihong Jiang

Abstract: Artificial Immune System (AIS) inspired from Biological Immune System was widely used in many fields. In this research work, a novel pattern recognition approach was proposed based on AIS. In process of antigen epitopes recognition in antibody, it was actually combination between corresponding chemical bonds. The recognition rate was correlated positively with combination forces of chemical bonds. The pattern recognition algorithm was tested using famous benchmark Fisher’s Iris data and wine data. Preliminary results demonstrated that the new approach had better performances comparing to other pattern recognition methods.

Keywords: pattern recognition, recognition algorithm, Artificial immune system, local binding energy and local binding sites

INTRODUCTION

In recently years, researchers in many fields have paid considerable attention to Artificial Immune System (AIS) which inspired from immune system (Timmis et al., 2008). Metaphor of Immune System was firstly applied in the area of fault diagnosis by Ishida (1990). the famous Negative Selection Algorithm (NSA) applying in the field of computer security and virus detection proposed by Forest et al. (1994) which seemed to set off a renaissance in further investigation of immune system. Most existing AIS algorithms mimic one of the following metaphors of the immune system: Negative selection, immune network, clonal selection, danger theory, etc. Ji and Dasgupta (2009) proposed detectors with variable-sized and variable-shaped which reduced false alarm rate as well as raised coverage in non-self space. Inspired from immune network, MOBAIS and GAIS which applied in multi-objective optimization problems were proposed (Castro and Von Zuben, 2008, 2010). Recently, some new immune theories are proposed including Pattern Recognition Receptors (PRRs) Model and Danger Theory. Conserved Self Pattern Recognition Algorithm (CSPRA) is proposed inspired by the PRRs Model, by which false positive error rate is reduced greatly (Yu and Dasgupta, 2009). Danger Theory solved some phenomenon which Immune Negative Selection (INS) and Self-Nonself Selection (SNS) can’t explain (Matzinger, 1994). Inspired from Danger Theory, the DCA is proposed and it has been evaluated by the KDD Cup’s 99 which is referred by Muda et al. (2011) and the experimental result is convincing (Greensmith et al., 2010). Yap et al. (2011) proposed Hybrid AIS (HAIS) combining the good features of AIS and Particle Swarm Optimization (PSO), which solved the rate of convergence and the local minima. The immune based approach has also been used in finding pure Nash equilibrium and mixed Nash equilibrium (Cheheltani and Ebadzadeh, 2010).

Pattern recognition has caused extensive concern in many fields. In language pattern recognition or classification, Artificial Neural Network is widely used (Lotfi et al., 2006; Khanale, 2010; Khanale and Chitnis, 2011). Jalil et al. (2003) proposed an unsupervised learning algorithm in feature extracting, which is a basic of pattern recognition. Al-Bashish et al. (2011) proposed a Neural-networks -based method to plant leaf diseases classification. Al-Daoud (2009) has done some comparisons between three Neural Network models for classification problems.

These days, attention has been paid in combination metaphors between antigen and antibody. Relationships between paratopes of antibody and epitopes of antigen are considered by Ji-zhong and Bo (2005). According to calculate sub-affinity, high affinity antibodies can be obtained more rapidly. In process of epitopes of antigen recognition in antibody, it is actually combination between corresponding chemical bonds. Chemical bonds include hydrogen bonds, electrostatic bonds, Van der Waals forces and hydrophobic bonds. The combination forces of chemical bonds influence the recognition rate. Based on those metaphors, antibody and epitopes of antigen are considered to be feature vectors, chemical bonds are attributes. The higher combination forces of chemical bonds, the better recognition of antigen epitopes. The main purpose of this paper is to enhance the recognition rate according to secondary recognition by evaluating combination forces of chemical bonds. Preliminary results demonstrate the new approach has better performances comparing to other methods (Srinivasa et al., 2007; Chang and Lilly, 2004) under the same experimental condition.

THEORETICAL BASIS OF IMMUNOLOGY

Immune system is a typical defense system which effectively resists and kills infectious agents. The substances which can provoke an immune response are antigens. There are nonspecific (innate) and specific (adaptive) basic types of immunity. The adaptive immune system mainly consists of B and T lymphocytes cells. These cells play an important role in recognizing and destroying antigens. Each B cell secretes multiple copies of one kind of antibody. Activated B cells become memory cells or plasma cells, the latter actively secret antibodies (Fig. 1) (Dasgupta and Nino, 2009). For antigen, there are a set of epitopes which have the distinct molecular surface features that bound by an antibody. Epitopes in one antigen (Ag1) are always different from another (Ag2) and some antigens (Ag3) even have reduplicative epitopes. Especially, a type of antibody can recognize only one kind of antigen epitopes (Fig. 2) (Zhou, 2002). Combination of antigen epitopes and antibody is a complex chemical process and the combination forces are all non-covalent in nature. The combination forces between antigen epitopes and antibody ensures that the antigen will be bound tightly to the antibody (Zhou, 2002). Chemical bonds between antibody and antigen are shown in Fig. 3.

As mentioned above, antibody and epitopes of antigen are considered to be feature vectors, chemical bonds are attributes. Firstly, the affinity between antibody and antigen epitopes is calculated. Later, the combination forces of chemical bonds are considered.

An algorithm is proposed to describe the process.

PROPOSED PATTERN RECOGNITION APPROACH

Some definitions:

Description of pattern recognition approach: The feature space T will be expressed by a set of antibodies X, there are q classes in X, X = [X₁, X₂, ..., X_q]^T. For each class, There are antibodies, X_i = [X_i1, X_i2, ..., X_ikm]^T, i = 1,2, ..., q. For each antibody, there are n local binding sites, X_ik = (x_ik1, x_ik2, ..., x_ikn) εRⁿ, I = 1,2, ..., q, k = 1,2, ..., m, where x_ikl, l = 1,2, ..., n, represents local binding site l of k-th antibody in class i. Each local binding site should reflect the main information of antibody.

Antigen epitope Y_j1 = (y_j1, y_j2, ..., y_jn), j = 1,2, ..., p, Affinity between and every antibody is calculated to recognize what class it is. The affinity is calculated by Euclidean distance as follows:

where, |Y_—X|_ikj, represent affinity between antigen epitope Y_j and the k-th antibody in class i. The mean affinity between antigen epitope Y_j and all of the antibodies in i-th class as follows:

From Eq. 2, the mean affinity is obtained and the antigen epitope will be divided into the class which has maximum mean affinity value.

But there are still some of antigen epitopes classified in error. As stated above, the local binding energy is considered whether the local binding sites between antibodies and antigen epitopes meet match coefficient. In what follows, it will be illustrated in detail.

For antigen epitope Y_j1 = (y_j1, y_j2, ..., y_jn), j = 1,2, ..., p, Antibody in k-th class X_ik = (x_ik1, x_ik2, ..., x_ikn) ∈Rⁿ, k = 1,2, ..., m, the local binding energy between y_jl and x_ikl is calculated, l = 1,2, ..., n, i = 1,2, ..., p. If |Y_jl-x_ikl|<sx|x_ikl| comes true, where s is the match coefficient. The antibody and its location l are stored inmatrix C, then sum l up. The more locations do antibody have, the more possible do antigen epitope belongs to the class where the antibody in. The algorithm process outlined below.

Define the ith class antibody set X_i = [X_i1, X_i2, ..., X_im]^T, i = 1,2, ..., q. For each antibody X_ik, there are n local binding sites, X_ik = (x_ik1, x_ik2, ..., x_ikn)∈Rⁿ. Antigen epitopes Y_j = (y_j1, y_j2, ..., y_jn), j = 1,2, ..., p.

Calculate affinity between antigen epitopes Y_j and every antibody X_ik in ith class with Eq. 1. Then put every affinity in matrix F where f₁₁₁ represents affinity between Y₁ and X₁₁, f_qmp represents affinity between Y_p and X_qm and so on:

The mean affinity can be obtained with Eq.2 and put them in matrix . Where represents mean affinity between X₁ and the first class antibody samples, represents mean affinity between Y_p and the q-th class antibodies. Antigens classified according to the max mean affinity:

For the wrong classified antigen epitopes Y_w = (y_w1, y_w2, ..., y_wn), w∈[1,p]. Local binding energy is calculated and locations meet match coefficient is accumulated, storing them in matrix C. W= w+1, then do step 3 again until reach termination.

The flow chart of the algorithm is displayed in Fig. 4.

Discussion the range of match coefficients: Iris, wine and breast cancer data are used to decide the best values of match coefficient s, which is firstly chosen from 0.13 to 0.7. Different data of pattern recognition accuracy curve is shown in Fig. 5.

Integrated effect of different curves is considered. At last, s is chosen from 0.18 to 0.3 according to the mean effect curves where the recognition rate is relatively high.

NUMERICAL RESULTS AND COMPARISONS

The famous benchmark Fisher’s data (Fisher, 1988) is used to illustrate and test the proposed approach. The Iris data set is almost the best known database in the area of pattern recognition. The data set contains 3 classes, where each class refers to a type of iris plant. There are 50 instances in each class and 4 attributes in each feature vector. The first 10 instances in each class are chosen as antibodies and the remaining 40 instances as antigen epitopes.

The affinity between every antigen epitope in Y_j and antibodies in X_ik are calculated by Eq. 1. Most of them can be classified in correct class, but some of them still classified in error. The value in italic indicates correct class, but have been classified in wrong class in bold (Table 1).

In Table 1ocal binding sites meet match coefficient is accumulated. Take the Y₈₁ wrong classified antigen epitope:

for example, local binding energy between Y₈₁ and k-th class antibody paratope X_ik, i = 1,2, ..., 30 is calculated. Then matrix C can be obtained which shows how many local binding sites in the antibody meet match coefficient. The results which 4 local binding sites are all meet match coefficient are in Table 2. The match coefficient s = 0.2.

According to depiction before, antigen epitopes Y₁ to y₄₀ belong to class 1, antigen epitopes Y₄₁ to Y₈₀ belong to class 2 and the rest belong to class 3. From Table 2, antibodies X_22,3, X_23,3, X_24,3, X_25,3, X_28,3 are all having 4 local binding sites meet match coefficient to bind antigen epitope Y₈₁. Consequently, antigen epitope Y₈₁ should be classified in class 3. Antigen epitope Y₉₀ is classified in class 3 as the same way. Antibody X_17,2 belongs to class 2 but X_22,3, X_23,3, X_24,3, X_25,3, X_29,3, are all in class 3. There is 83.33% that conclude the antigen epitope Y₉₀ should be classified in class 3. Antibodies X_11,2, X_12,2, X_13,2, X_15,2, X_16,2, X_17,2, X_19,2 are all in class 2, antibodies X_24,3, X_28,3, X_29,3, in class 3, 70% shows the antigen epitope possibility should be classified in class 2. Antigen epitope Y₁₄₀ classified in wrong class in this way.

Overall, the wrong classified antigen epitopes are reduced to 1 and accuracy is enhanced from 95% to 99.17% (one misclassification). Then do the test in another way, the middle 10 instances are chosen in each Iris class as antibodies and the remaining 40 instances as antigen epitopes. Most of the antigen epitopes can be recognized correctly, but there are still some of them wrong classified antigen epitopes which are shown in Table 3. The match coefficient s = 0.2.

Antigen epitope Y₆₄ should be in class 2 but classified in class 3, antigen epitope Y₈₇, Y₁₀₀, Y₁₀₄ should be in class 3 but classified in class 2 incorrectly. Antibodies in X_ik whose 4 local binding sites are all meet match coefficient are shown in Table 4.

Antigen epitopes Y₁ to Y₁₀ belong to class 1, antigen epitopes Y₁₁ to Y₂₀ belong to class 2 and the rest belong to class 3. According to Table 4, antibodies X_11,2, X_13,2, X_16,2, X_17,2, X_18,2, X_19,2, X_24,3, X_26,3, X_27,3, X_28,3, X_30,3 are all having 4 local binding sites meet match coefficient to bind error classified antigen epitope Y₆₄.

From above results, antigen epitope Y₆₄ can be classified in class 2 and the same to Y₈₇. The same way to analysis other wrong classified antigen epitopes. The recognition rate is 98.33% (two misclassifications). The average recognition rate for iris data set is 98.75%. There are some comparisons with other pattern recognition method is illustrated in Table 5.

The wine data is also used to test the algorithm. These data are the results of a chemical analysis of wines grown in the same region in Italy but derived from three different cultivars, so there are 59 instances in class 1, 71 instances in class 2 and the rest 48 instances in class 3. There are 13 attributes in the data set. The first 40 instances are chosen from each class as antibodies and the remaining of each class are deemed to antigen epitopes. The mean affinity between antigen epitopes and antibodies are calculated. The results are listed in Table 6.

The affinity between wrong classified antigen epitopes and antibodies are calculated. According to the antibody whose local binding sites have the maximum number meeting match coefficient, the antigen epitopes is classified again. Match coefficient s = 0.25. The result is illustrated in detail in Table 7.

For wine data set, the first 40 instances from each class are chosen as antibodies and the remaining are deemed to antigen epitopes. There are 13 local binding sites in antigen epitope meet match coefficient to bind antibody, so antigen epitope should be classified in class 1. Similarly, antigen epitope belongs to class 1 because it has 12 local binding sites meet match coefficient to bind antibody. So other false classified antigen epitopes are all classified again in right class except antigen epitope. Anyway, the recognition accuracy rate is 98.25% (one misclassification).

CONCLUSION

Biological immune system as the most important part of organisms plays an indispensable role in defending invaders. Relationships between antibodies and antigen epitopes, especially, the chemical bonds of them are considered more. The higher combination forces of chemical bonds, the better recognition of antigen epitopes. In this study, a novel pattern recognition approach is proposed and also the range of match coefficient is discussed. Iris and wine data sets from UCI machine learning repository are used to test the proposed approach. The numerical results show patterns can be recognized effectively. In our future work, some real-world data should be applied to the proposed pattern recognition approach.

ACKNOWLEDGMENT

This work is supported by National Natural Science Foundation of China (Grant No. 51175316), the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20103108110006), Shanghai Talent Development Fund (Grant No. 047) and Innovation Fund of Shanghai University.

REFERENCES