# Identifying the Risky SNP of Osteoporosis with ID3-PEP Decision Tree Algorithm

Authors: Jincai Yang; Huichao Gu; Xingpeng Jiang; Qingyang Huang; Xiaohua Hu; Xianjun Shen
Journal: Complexity
 (2017)

---

## Abstract

In the past 20 years, much progress has been made on the genetic analysis of osteoporosis. A number of genes and SNPs associated with osteoporosis have been found through GWAS method. In this paper, we intend to identify the suspected risky SNPs of osteoporosis with computational methods based on the known osteoporosis GWAS-associated SNPs. The process includes two steps. Firstly, we decided whether the genes associated with the suspected risky SNPs are associated with osteoporosis by using random walk algorithm on the PPI network of osteoporosis GWAS-associated genes and the genes associated with the suspected risky SNPs. In order to solve the overfitting problem in ID3 decision tree algorithm, we then classified the SNPs with positive results based on their features of position and function through a simplified classification decision tree which was constructed by ID3 decision tree algorithm with PEP (Pessimistic-Error Pruning). We verified the accuracy of the identification framework with the data set of GWAS-associated SNPs, and the result shows that this method is feasible. It provides a more convenient way to identify the suspected risky SNPs associated with osteoporosis.


---

## Body

## 1. Introduction

Osteoporosis is a type of systemic skeletal disease that is characterized by reduced bone mass and microarchitecture deterioration of bone tissues, thereby leading to the loss of strength and increased risk of fractures [1]. It is one of the age-related diseases with arteriosclerosis, hypertension, diabetes, and cancer. Currently, none of the medical methods is safe and effective to cure osteoporosis. Therefore, it is necessary to provide theoretical basis for developing a medical strategy to cure the disease from the pathogenesis of osteoporosis.With the completion of the International HapMap Project and 1000 Genomes Project, about ten millions SNPs of human were annotated, among which more than 3 million are common SNPs. Genetic analysis has reached the stage of genome-wide association study (GWAS). The GWAS is applied to the study of 40 kinds of diseases that are related to more than 500 thousands SNPs [2].Osteoporosis is a complex and polygenic disease of bone system with the heritability of bone mass is about 60–80% [3]. Much progress has been made on the genetic analysis of osteoporosis in the past 20 years and it has been found that a lot of genes and SNPs are associated with osteoporosis through GWAS [4, 5].Computational biology refers to the development and application of data analysis, the theory of data method, mathematical modeling, and computer simulation technology, used in the study of biology, behavioral, and social group system of a discipline [6]. The rapid mass of biological data accumulation is unprecedented in the history of human science. Now, a variety of methods and tools of computational biology through the Internet have been successfully applied in every aspect in the field of biological research. They are powerful for post-GWAS studies [7] and could identify the potential and promising causal SNPs that require experimental tests for follow-up functional studies. Extensive work has been done in this area in recent years. The performances were well validated through identifying numerous disease-associated SNPs for further study and revealing previously unknown mechanisms for complex diseases [8].The method of computational biology can also be used to study and understand these osteoporosis-susceptible genes and the function of SNP. All the osteoporosis associated genes and SNPs (including linkage disequilibrium (LD) SNPs) sequence information were collected and aggregated from the national center for biological information (NCBI) database, and the effects of osteoporosis GWAS-associated lead SNPS and their linked SNPs to transcription factor (TF) binding affinity were studied through JASPAR database. At the same time, the osteoporosis GWAS-associated genes have also been analyzed with Protein-Protein Interaction (PPI) network analysis tool in the study of the osteoporosis GWAS-associated SNPs associated by the online PPI tool named String. Combining with GO and pathway analysis, we found that the hub proteins associated and the Wnt signaling pathway were related to the mesenchymal stem cell differentiation and hormone signaling that was related to the metabolism of osteoporosis [9]. Finally, it was found that the osteoporosis GWAS-associated SNPs in special region of genes had long-range interaction signal with other locus by analyzing the long-range interaction of osteoporosis associated SNPs on GWAS3D [10].In the BIBM workshop paper [11], we utilized the known osteoporosis GWAS-associated SNPs and genes as the data set to identify the osteoporosis suspected risky SNPs. The process for identification was achieved by computation method. In this extension, we made some improvements on the paper. Firstly, we had achieved graphical description for the SNPs identification process. We added a flow chart for the paper to describe the process of identification method that made the method more intuitive. Secondly, we used ID3 decision tree algorithm with PEP method instead of ID3 decision tree algorithm in the second part of the method. We made the improvement to solve the overfitting problem in ID3 decision tree algorithm; we used the C4.5 algorithm to make a comparison with our ID3-PEP algorithm. Finally, we added type 2 diabetes (T2D) GWAS-associated SNPs and genes as the negative data set based on osteoporosis GWAS-associated SNPs and genes to verify the accuracy of the method comprehensively.


## 2. Material and Method

We identified the suspected risky SNPs associated with osteoporosis by algorithm based on the analysis of osteoporosis GWAS-associated SNPs with the method mentioned above [9]. It is assumed that the SNPs that are similar to the osteoporosis GWAS-associated SNPs are possible risky SNPs associated with osteoporosis. The identification process of the suspected risky SNPs includes two steps in general. Firstly, we constructed a Protein-Protein Interaction (PPI) network based on the Protein-Protein Interaction analysis of the osteoporosis GWAS-associated genes and the genes associated with suspected risky SNPs and identify whether the genes associated with the suspected risky SNPs are associated with osteoporosis through random walk algorithm based on Markov chain. By the algorithm, we also selected the suspected risky SNPs whose associated genes are identified to be associated with osteoporosis. We then classified those SNPs based on their characteristics of function and their loci features by a classification decision tree, and the decision tree was constructed by ID3 decision tree algorithm with Pessimistic-Error Pruning. Figure 1 describes the process to identify the osteoporosis risky SNPs.Figure 1
Process to identify the suspected risky SNPs associated with osteoporosis.


### 2.1. The Identification of Genes Associated with Suspected Risky SNPs

According to the modular property of the genetic diseases, many scholars have proposed prioritization algorithms to predict the disease-causing genes based on the PPI, Human Disease Network, and DISEASOME recently [12–16]. Similarly, we obtained the scores of the genes associated with the suspected risky SNPs through the random walk algorithm based on the PPI of the osteoporosis GWAS-associated genes and the genes associated with suspected risky SNPs. Then, the result was acquired by setting up a threshold k, and the genes associated with suspected risky SNPs are probably the osteoporosis associated genes if their scores are greater than k.


### 2.2. The Random Walk Algorithm Based on Markov Chain

Kohler proposed a method for the problem of candidate-gene prioritization by random walk algorithm based on the global network distance of PPI. The results indicate that the algorithm is more effective than the local network distance algorithm [17]. The random walk algorithm was applied to Protein-Protein Interaction network of all associated genes.An undirected graphG=(V,E) is defined for the Protein-Protein Interaction network of all associated genes. In the undirected graph G, V is the set of vertices for the interactors of the network. And V is defined as V={v1,v2,…,vn}; E is the set of edges; and E is defined as E={vi,vj∣vi,vj∈V}. Every edge in the set of edges corresponds to two nodes of the set of vertices for the interaction between the interactors. Moreover, it is assumed that a random process meets the condition of Markov chain. The random process should be as follows:(a)
The probability distribution of timet+1 is only related to the state of time t, and it is not related to the state before time t.(b)
The state transition is not related to the value oft from the time t to time t+1. Therefore, the Markov chain model is defined as (1)S,P,Q.S is a nonempty set that consists of all the possible states of the system. It is a state space that can be a limited and denumerable set or a nonempty set. P=[Pij]n×n is the state transfer-probability matrix, Pij is the probability that the system is in the state i at time t to the state j at time t+1. N is the number of system states. Q={q0,q1,…,qn-1} is the initial probability distribution of the system, qi is the probability that the system in state i at the initial time, and ∑i=0Nqi=1.Based on the above theory model, the random walk on graphs is defined as an iterative walk’s transition from its current node to a randomly selected neighbor starting at given source node [17]. The random walk is defined as(2)Pt+1=1-αPtW+αP0.Pt is a vector in which the ith element holds the probability of being at node i at time step t. α is a constant between 0 and 1 that it is the restart of the walk in every step at the node i with probability α, and α∈(0,1] [17]. P0 is a row vector of 1×n which is the initial state of the system, and n is the element number of V. The value of known elements of P0 is equal, and the sum of them is 1. And the value of other elements is 0. W is the transition probability matrix which is defined as(3)W=D-1A.A is an adjacency matrix of undirected graph V. Every element aij of A is defined as follows: if there is interaction between vi and vj in the network, the element aij=1; otherwise, aij=0 the formula is defined as(4)aij=1,vi,vj∈E0,otherwise.D is a diagonal matrix. Each element dij of D is defined as follows: if i=j then it should have dij=dii; otherwise dij=0. dij is the degree of vi in the network. The formula is defined as(5)dij=∑k=1naik,i=j0,otherwise.The transition probability matrixW is also a row-normalized adjacency matrix of the graph. Formula (2) meets the state of stationary distribution of Markov train model obviously, so the central point of random walk algorithm is evaluating the stationary distribution state of the probability of the nodes in the undirected network G which consists of PPI. Firstly, the transition probability matrix W should be obtained and the initial value is set for P0. Then, process t times iteration based on formula (2) until lim(pt+1-pt)=0, pt+1 is a convergence vector. A threshold is set for the probability value, and if the probability value of the nodes (or genes) is greater than the threshold, they are osteoporosis associated genes.


### 2.3. Classify the Suspected Risky SNPs by ID3 Decision Tree Algorithm

ID3 decision tree algorithm is a classification algorithm for tree structure [18, 19]. The goal of the algorithm is to predict target variable based on multiple input variables and deduce a classification rule with decision tree form from a group of irregular samples. We assume that all input characteristic elements have a limited discrete domain and need an individual characteristic element as a category. The nonleaf nodes of a classification decision tree classify the samples by characteristics of samples, and each leaf node of the tree is a class or classes of probability distribution. Therefore, we chose decision tree to classify the SNP based on the condition of the training set and algorithm characteristics.SNPs located within the promoter or distant enhancer region of genes may alter the binding of TFs with DNA and subsequently regulate gene expression [20]. The suspected risky SNPs are classified by ID3 decision tree algorithm based on four features of significant position on genes, mapping on putative enhancer region, mapping on distal interaction, and the region where the SNPs are located [21].The decision tree algorithm chooses the attribute with the maximum information gain after it is split, and the algorithm searches the decision-space by way of top-down greedy algorithm.S is defined as the training set of SNPs with their loci features, and the training set is divided into n classes. That is, C={S1,S2,…,Sn}. The number of the training instances in ith class is defined as Si=Ci. The number of the training instances in S is S. The probability that a training instance belongs to the ith class is P(Si). And a formula is defined as(6)PSi=CiS.For the training setS, H(S) is defined as the information entropy of C, and we have the formula(7)HS=-∑i=1nPSilog2⁡PSi.The greater the value of information entropyH(S) is, the smaller the degree of uncertainty for the division of C is. The attribute T is selected as the test attribute which is the loci features of the training set SNPs, and the value set for attribute T is T={t1,t2,…,tm}. The probability of the attribute belongs to ith class when T=tj can be formulated as(8)PSi∣T=tj=CijS.Cij is the number of training instances which belongs to ith class.When the attributeT=tj, a formula is used to define the conditional entropy of the attribute T as(9)HXj=-∑i=1nPSi∣T=tjlog2⁡PSi∣T=tj.Xj is the training instances set of training set S.The information entropy of attributeT is defined as(10)IGT=HS-∑j=1mPSi∣T=tjHXj.We built a top-down decision tree and classified the training instances by choosing the attribute with the maximum information entropy based on the formulas above.However, the overfitting problem could not be avoided if there were many noise samples in the training set, because of a complicated classification decision tree constructed by ID3 decision tree algorithm with a fair amount of noise samples in the training set. To solve the problem, a PEP (Pessimistic-Error Pruning) algorithm was exerted on the ID3 decision tree classification algorithm. PEP is the most accurate top-down pruning strategy which deals with the pruning problem without separating the training set.We define a decision treeT which grows on a large scale based on the training set of SNPs with their loci features. T1 is a nonleaf node set, T2 is a leaf node set, and T3 is for all nodes of T. The formula is T3=T1∪T2.Before pruning, we definer(t) as the error rate of node t in the decision tree. The formula is(11)rt=etnt.n(t) is the number of samples in node t, and e(t) is the number of samples that does not belong to node t actually.We defineTt as a subtree of the decision tree T, and t is the root node of Tt. So the error rate of the subtree Tt is(12)rTt=∑s∈Stes∑s∈Stns.St is the leaf node set of subtree Tt, and we define St={s1,s2,…,sn}.Apparently, the formula for error rate of the subtreeTt is binomial distribution. We define a continuity correction factor r′(t) in order to make the binomial distribution approach the normal distribution. And the formula is(13)r′t=et+1/2nt.Therefore, we deduce the continuity correction factor for the subtreeTt. The formula is(14)r′Tt=∑s∈Stes+1/2∑s∈Stns=∑s∈Stes+St/2∑s∈Stns.In order to simplify the formula, we definee′(t) as the error sample number instead of error rate. So the error sample number of node t in the decision tree T is(15)e′t=et+12.Therefore, the error sample number of the subtreeTt is(16)e′Tt=∑s∈Stes+St2.Similarly, the formula for the error sample number of subtreeTt is binomial distribution. And the standard deviation for e′(Tt) is defined as(17)SEe′Tt=e′Tt×nt-e′Ttnt1/2.Finally, we deduce from formulas above that the subtreeTt will be cut if the node t meets the condition:(18)e′t≤e′Tt+SEe′Tt.The process of the PEP algorithm is as follows:Algorithm: PEPBeginInput: decision treeTbefore prunedOutput: decision treeTafter pruned(1) Get the nonleaf node setT1of the decision treeT(2) Fork=1to length(T1)(3)   Do get a subtreeTtwhose root node ist[k](t[k]∈T1)(4)    If(e′(t)≤e′(Tt)+SE(e′(Tt)))(5)    Then deleteTt(6)    Elsek++(7)   EndEndWe classified the suspected risky SNPs effectively based on their loci characteristics and studied their functions according the ID3 decision tree algorithm and PEP.


## 2.1. The Identification of Genes Associated with Suspected Risky SNPs

According to the modular property of the genetic diseases, many scholars have proposed prioritization algorithms to predict the disease-causing genes based on the PPI, Human Disease Network, and DISEASOME recently [12–16]. Similarly, we obtained the scores of the genes associated with the suspected risky SNPs through the random walk algorithm based on the PPI of the osteoporosis GWAS-associated genes and the genes associated with suspected risky SNPs. Then, the result was acquired by setting up a threshold k, and the genes associated with suspected risky SNPs are probably the osteoporosis associated genes if their scores are greater than k.


## 2.2. The Random Walk Algorithm Based on Markov Chain

Kohler proposed a method for the problem of candidate-gene prioritization by random walk algorithm based on the global network distance of PPI. The results indicate that the algorithm is more effective than the local network distance algorithm [17]. The random walk algorithm was applied to Protein-Protein Interaction network of all associated genes.An undirected graphG=(V,E) is defined for the Protein-Protein Interaction network of all associated genes. In the undirected graph G, V is the set of vertices for the interactors of the network. And V is defined as V={v1,v2,…,vn}; E is the set of edges; and E is defined as E={vi,vj∣vi,vj∈V}. Every edge in the set of edges corresponds to two nodes of the set of vertices for the interaction between the interactors. Moreover, it is assumed that a random process meets the condition of Markov chain. The random process should be as follows:(a)
The probability distribution of timet+1 is only related to the state of time t, and it is not related to the state before time t.(b)
The state transition is not related to the value oft from the time t to time t+1. Therefore, the Markov chain model is defined as (1)S,P,Q.S is a nonempty set that consists of all the possible states of the system. It is a state space that can be a limited and denumerable set or a nonempty set. P=[Pij]n×n is the state transfer-probability matrix, Pij is the probability that the system is in the state i at time t to the state j at time t+1. N is the number of system states. Q={q0,q1,…,qn-1} is the initial probability distribution of the system, qi is the probability that the system in state i at the initial time, and ∑i=0Nqi=1.Based on the above theory model, the random walk on graphs is defined as an iterative walk’s transition from its current node to a randomly selected neighbor starting at given source node [17]. The random walk is defined as(2)Pt+1=1-αPtW+αP0.Pt is a vector in which the ith element holds the probability of being at node i at time step t. α is a constant between 0 and 1 that it is the restart of the walk in every step at the node i with probability α, and α∈(0,1] [17]. P0 is a row vector of 1×n which is the initial state of the system, and n is the element number of V. The value of known elements of P0 is equal, and the sum of them is 1. And the value of other elements is 0. W is the transition probability matrix which is defined as(3)W=D-1A.A is an adjacency matrix of undirected graph V. Every element aij of A is defined as follows: if there is interaction between vi and vj in the network, the element aij=1; otherwise, aij=0 the formula is defined as(4)aij=1,vi,vj∈E0,otherwise.D is a diagonal matrix. Each element dij of D is defined as follows: if i=j then it should have dij=dii; otherwise dij=0. dij is the degree of vi in the network. The formula is defined as(5)dij=∑k=1naik,i=j0,otherwise.The transition probability matrixW is also a row-normalized adjacency matrix of the graph. Formula (2) meets the state of stationary distribution of Markov train model obviously, so the central point of random walk algorithm is evaluating the stationary distribution state of the probability of the nodes in the undirected network G which consists of PPI. Firstly, the transition probability matrix W should be obtained and the initial value is set for P0. Then, process t times iteration based on formula (2) until lim(pt+1-pt)=0, pt+1 is a convergence vector. A threshold is set for the probability value, and if the probability value of the nodes (or genes) is greater than the threshold, they are osteoporosis associated genes.


## 2.3. Classify the Suspected Risky SNPs by ID3 Decision Tree Algorithm

ID3 decision tree algorithm is a classification algorithm for tree structure [18, 19]. The goal of the algorithm is to predict target variable based on multiple input variables and deduce a classification rule with decision tree form from a group of irregular samples. We assume that all input characteristic elements have a limited discrete domain and need an individual characteristic element as a category. The nonleaf nodes of a classification decision tree classify the samples by characteristics of samples, and each leaf node of the tree is a class or classes of probability distribution. Therefore, we chose decision tree to classify the SNP based on the condition of the training set and algorithm characteristics.SNPs located within the promoter or distant enhancer region of genes may alter the binding of TFs with DNA and subsequently regulate gene expression [20]. The suspected risky SNPs are classified by ID3 decision tree algorithm based on four features of significant position on genes, mapping on putative enhancer region, mapping on distal interaction, and the region where the SNPs are located [21].The decision tree algorithm chooses the attribute with the maximum information gain after it is split, and the algorithm searches the decision-space by way of top-down greedy algorithm.S is defined as the training set of SNPs with their loci features, and the training set is divided into n classes. That is, C={S1,S2,…,Sn}. The number of the training instances in ith class is defined as Si=Ci. The number of the training instances in S is S. The probability that a training instance belongs to the ith class is P(Si). And a formula is defined as(6)PSi=CiS.For the training setS, H(S) is defined as the information entropy of C, and we have the formula(7)HS=-∑i=1nPSilog2⁡PSi.The greater the value of information entropyH(S) is, the smaller the degree of uncertainty for the division of C is. The attribute T is selected as the test attribute which is the loci features of the training set SNPs, and the value set for attribute T is T={t1,t2,…,tm}. The probability of the attribute belongs to ith class when T=tj can be formulated as(8)PSi∣T=tj=CijS.Cij is the number of training instances which belongs to ith class.When the attributeT=tj, a formula is used to define the conditional entropy of the attribute T as(9)HXj=-∑i=1nPSi∣T=tjlog2⁡PSi∣T=tj.Xj is the training instances set of training set S.The information entropy of attributeT is defined as(10)IGT=HS-∑j=1mPSi∣T=tjHXj.We built a top-down decision tree and classified the training instances by choosing the attribute with the maximum information entropy based on the formulas above.However, the overfitting problem could not be avoided if there were many noise samples in the training set, because of a complicated classification decision tree constructed by ID3 decision tree algorithm with a fair amount of noise samples in the training set. To solve the problem, a PEP (Pessimistic-Error Pruning) algorithm was exerted on the ID3 decision tree classification algorithm. PEP is the most accurate top-down pruning strategy which deals with the pruning problem without separating the training set.We define a decision treeT which grows on a large scale based on the training set of SNPs with their loci features. T1 is a nonleaf node set, T2 is a leaf node set, and T3 is for all nodes of T. The formula is T3=T1∪T2.Before pruning, we definer(t) as the error rate of node t in the decision tree. The formula is(11)rt=etnt.n(t) is the number of samples in node t, and e(t) is the number of samples that does not belong to node t actually.We defineTt as a subtree of the decision tree T, and t is the root node of Tt. So the error rate of the subtree Tt is(12)rTt=∑s∈Stes∑s∈Stns.St is the leaf node set of subtree Tt, and we define St={s1,s2,…,sn}.Apparently, the formula for error rate of the subtreeTt is binomial distribution. We define a continuity correction factor r′(t) in order to make the binomial distribution approach the normal distribution. And the formula is(13)r′t=et+1/2nt.Therefore, we deduce the continuity correction factor for the subtreeTt. The formula is(14)r′Tt=∑s∈Stes+1/2∑s∈Stns=∑s∈Stes+St/2∑s∈Stns.In order to simplify the formula, we definee′(t) as the error sample number instead of error rate. So the error sample number of node t in the decision tree T is(15)e′t=et+12.Therefore, the error sample number of the subtreeTt is(16)e′Tt=∑s∈Stes+St2.Similarly, the formula for the error sample number of subtreeTt is binomial distribution. And the standard deviation for e′(Tt) is defined as(17)SEe′Tt=e′Tt×nt-e′Ttnt1/2.Finally, we deduce from formulas above that the subtreeTt will be cut if the node t meets the condition:(18)e′t≤e′Tt+SEe′Tt.The process of the PEP algorithm is as follows:Algorithm: PEPBeginInput: decision treeTbefore prunedOutput: decision treeTafter pruned(1) Get the nonleaf node setT1of the decision treeT(2) Fork=1to length(T1)(3)   Do get a subtreeTtwhose root node ist[k](t[k]∈T1)(4)    If(e′(t)≤e′(Tt)+SE(e′(Tt)))(5)    Then deleteTt(6)    Elsek++(7)   EndEndWe classified the suspected risky SNPs effectively based on their loci characteristics and studied their functions according the ID3 decision tree algorithm and PEP.


## 3. Results

By the end of 2014, nine GWAS and nine meta-analyses had reported 107 genes and 129 SNPs (lead SNP) that were associated with BMD, osteoporosis, or fractures with a significant threshold of5×10-8. 222 SNPs linked to osteoporosis GWAS-associated lead SNPs had also been identified by using LD information in the Caucasians population via HapMap website [9]. Moreover, we obtained 107 known osteoporosis GWAS-associated genes which showed significant connectivity among proteins. And there were interactions between osteoporosis GWAS-associated genes and interactors. We used the common Protein-Protein Interaction databases, such as Human Protein Interaction database (HPID) and General Repository for Interaction Data (GRID), to find the interactors which had interactions with the osteoporosis GWAS-associated genes and their interactions. Then, we obtained the interaction network graph by Cytoscape v3.4.0. Figure 2 is the PPI of osteoporosis GWAS-associated genes.Figure 2
PPI of osteoporosis GWAS-associated genes (the pink nodes indicated those which had interactions with the osteoporosis GWAS-associated genes, and the yellow nodes indicated the osteoporosis GWAS-associated genes).The result was verified by 10-fold cross-validation based on the data set of osteoporosis GWAS-associated genes and SNPs. We divided the data set of 129 osteoporosis GWAS-associated lead SNPs and 222 SNPs linked with them into 10 samples. One sample was then randomly chosen and saved as the validation set to verify the model from the 10 samples, and the other 9 samples were saved as training set. The verification process was repeated 10 times so that each sample was the validation set once, and the accuracy was calculated every time. A 10-fold cross-validation was completed by the process above.We set a thresholdk (k>10-3) as a result of the validation. The recall was calculated, which was the true positive result to positive result ratio. The 10-fold cross-validation was repeated for ten times and the average recall rate of every validation was calculated. The result was shown in Figure 3.Figure 3
Result of random walk (the ten colors of the points indicated ten 10-fold cross-validation, and the same color of points indicated the validation process. The points connected by a line were the average recall value of ten experiments. Thex-axis was the 10-step verification of the 10-fold cross-validation process).The classification result was also verified by 10-fold cross-validation. The osteoporosis GWAS-associated SNPs were used as the data set. The SNPs of training set were classified based on their loci features. Part of classification of the training set was shown in Table1. We classified the SNPs of validation set through ID3 decision tree algorithm and recorded the accuracy of classification, which was the proportion of classification accurate samples to all the samples.Table 1
Part of the classification of training set.
SNP
bda
td
Enhancer
Gene region
Class
rs7524102
Y
Y
Y
Intergenic
C
rs34920465
Y
Y
Y
Control region
D
rs6426749
Y
N
Y
Control region
G
rs1430742
N
N
N
Cording sequence
B
rs6929137
Y
Y
Y
Missense
A
rs479336
Y
Y
N
Cording sequence
K
rs11898505
Y
N
Y
Intergenic
F
rs17040773
Y
Y
Y
Cording sequence
E
rs344081
Y
N
Y
Cording sequence
H
rs6909279
Y
Y
N
Intergenic
I
(a) The first column is part of osteoporosis GWAS-associated SNPs; (b) the column of “bda,” “td,” and “enhancer” means whether the SNP is on significant TFs binding affinity, mapping on distal interaction, and mapping on putative enhancer region; (c) the last column is the category the SNP belong to.Then, the process of validation was repeated for ten times and calculated the average accuracy rate and average classification reliability. The result was shown in Figure4.Figure 4
Result of ID3 decision tree (the blue credibility refers to the average accuracy values of 10-fold cross-validation, and the orange credibility refers to the average reliability value).We also used genome-wide association studies (GWAS) of type 2 diabetes (T2D) data as negative data to verify our method [22]. 50 lead SNPs of T2D were obtained with their position features and associated genes. We searched the interactors of the associate genes from the PPI database and constructed the PPI network with the known osteoporosis GWAS-associated genes. The random walk algorithm was used on the PPI network.We then used PEP for ID3 decision tree to construct a simplified classification decision tree. We combined the two steps of the risky SNPs identification method and verified the method by 10-fold cross-validation. Finally, we found that not only was the computation efficiency improved, but also the accuracy rate of the result by using ID3 decision tree algorithm with PEP in the identification method was higher. The improvement is due to the fact that we had cut the subtrees which were constructed by the noise samples and solved the overfitting problem. While we defined ID3 decision tree algorithm with PEP in the identification method as ID3-PEP and ID3 decision tree algorithm as ID3, the result comparison of these two classification algorithm in the identification method was described by Figure5. According to the result, we concluded that the ID3-PEP in the identification method was more stable than ID3 algorithm, and it had better effect for the classification problem.Figure 5
Comparison of two classification algorithm (the blue credibility refers to the classification accuracy by ID3 algorithm, and the yellow credibility refers to the classification accuracy by ID3 decision tree algorithm with PEP).C4.5 is the optimization of ID3. They have the same way to learn training set and build a classification decision tree, but the difference of them is the way of choosing split attribute. C4.5 algorithm chooses the maximum attribute with information gain ratio to split. In order to solve the problem of overfitting in ID3 decision tree algorithm, C4.5 algorithm needs to scan the data set and rank them in every step. This calculation method and process of the algorithm have low operational efficiency. ID3-PEP algorithm solved the problem and was more accurate than C4.5. We made a comparison of these two algorithms through ROC curve, which is shown in Figure6. Result shows that ID3-PEP is better than C4.5 in our classification.Figure 6
The comparison of ID3-PEP and C4.5.


## 4. Discussion and Conclusion

Since SNP plays a key role in the process of pathology and susceptibility of osteoporosis [23], it is necessary to find the unknown risky SNPs. Using the data set of known osteoporosis GWAS-associated SNPs and genes ‎[8], we identified the genes of suspected risky SNPs associated with osteoporosis by random walk algorithm on the PPI network constructed by osteoporosis GWAS-associated genes and the genes associated with suspected risky SNPs. The suspected risky SNPs were classified based on the features of their loci position and function. We used 10-fold cross-validation to verify our method.The result of the experiment above showed that the identification method for risky SNPs of osteoporosis was correct and effective. Our method efficiently achieved the process of identifying osteoporosis suspected risky SNPs.However, there is still a need to perfect the identification method. First of all, we need to search the loci features of suspected risky SNPs associated with osteoporosis and the interactors of associated genes manually. The training set for our method is the known osteoporosis GWAS-associated SNPs, which is not large enough to identify the risky SNPs accurately. Therefore, further research is needed. Firstly, a workflow can be constructed to improve the identification process, aiming to automatically identify the suspected risky SNPs’ features. In order to improve the accuracy of our method, more features of the SNPs should be examined, such as the conservation of SNPs and the influence of the SNPs on miRNA binding site. Finally, we use our method to predict risky SNPs associated with osteoporosis by constructing the PPI network of all the human genes.



---

*Source: 9194801-2017-08-07.xml*