论文部分内容阅读
摘 要：针对DNA序列类别的分属问题，提出采用支持向量机（Support Vector Machine, SVM）的方法进行分类。根据SVM分类器的要求建立特征属性空间，首先由每个DNA中4个碱基的含量得到4个特征属性，然后在此空间中扩充DNA序列长度的属性，最后根据SVM分类器对已知的DNA分类样本做训练得到分类超平面。利用此超平面检测所要分类的DNA序列，实验结果表明这种方法具有很好的分类精度。
关键词：SVM；DNA分类；特征属性空间；分类超平面
中图分类号：TP181文献标识码：A文章编号：1672-1098(2009)01-0058-05
收稿日期：2008-05-16
基金项目：国家自然科学基金资助项目（10501009）；安徽财经大学青年基金资助项目（ACKYQ0843ZC）
作者简介：徐健（1982-），男，安徽凤阳人，讲师，硕士，主要研究方向：支持向量机、模式识别、数据挖掘等。
A Classification Method of DNA Sequence Based on
Support Vector Machine
XU Jian1,LI Bai-nian1,ZHANG Kong-sheng1,JIANG Li-hua2
(1. School of Statistics and Applied Mathematics, Anhui University of Finance and Economics, Bengbu Anhui 233030,China;2. School of Sciences, Anhui University of Science and Technology,Huainan Anhui 232001,China)
Abstract:A new classification method of DNA sequence based on SVM was presented. The feature attribute space was established according to requirement of SVC. At first, four feature attributes were built by content of DNA’s four bases. By increasing length attribute of DNA sequence in the space to extent the feature attribute space. Finally, the classification of hyperplane was obtained on the basis of available samples training by using SVC in the feature attribute space. The DNA sequence to be classified was verified by the hyperplane. The results show that the classification method accuracy is very good.
Key words: SVM; classification of DNA; feature attribute space; classification hyperplane
基于统计学习理论的支持向量机(Support Vector Machine，SVM)是新近研究机器学习、数据挖掘和人工智能领域的一个热点。SVM将求解的问题最终归结为一个线性约束的凸二次规划问题，求出的解是全局最优的唯一解。SVM基于结构风险最小化原则，利用核函数将非线性问题转化为特征空间的线性问题。所以SVM在处理分类问题中一直有很好的表现。
2000年6月，人类基因组计划中DNA全序列草图完成，每条DNA序列由A、T、C、G按一定顺序排成长约30亿的序列，这4个字符表示了4种碱基。研究DNA全序列具有的结构和隐藏的规律，一直是生物信息学（Bioinformatics）最重要的课题之一。近年来使用SVM方法分析DNA序列的研究也在进行中，一些是对SVM方法进行改进并应用到DNA序列分类中，例如：使用SVM的几何修正法对DNA序列进行分析［1］；一些是对分类DNA序列中SVM所使用的特征属性提取方法进行讨论，例如：用窗口滑动来计算重复序列的出现频率，从而构造分类属性［2］；还用一些是针对DNA序列本身某一特性，结合SVM和其他方法进行比较得到更好的精度，例如：使用RS-GA-SVM方法分析DNA翻译起始点位置［3］，以及使用SGBP方法分析QSAMs模型，并采用部分最小二乘法（PLS）和SVM方法共同进行分类，并对两种方法的分类精度进行比较，最终提出SGBP-GA-SVM的处理步骤［4］。针对2000年全国大学生数学建模中提出的DNA序列分类问题，使用含量特征表示对DNA进行解构，结合SVM分类特性提出一种新的分类DNA序列的方法，此方法操作简便，分类效果精确，是一种对分类模型建模的有效方法。
1 SVM线性分类学习机
定义1 训练集T=｛(x1,y1)，…，(xm,ym)｝∈(X×Y)m,其中xi∈X=Rn，yi∈Y=｛1,-1｝，i=1,…，m。若存在w∈Rn，b∈R和正数ε，使得对所有使yi=1的下标i，有(w·xi)+b≥ε，而对所有使yi=-1的下标i，有(w·x1)+b≤-ε，则称训练集T线性可分。同时也称相应的分类问题是线性可分的［5］（见图1）。
图1 线性可分的情况
由图1可知，法向量为w时分类超平面并不唯一，l，l1和l2就是三个典型的超平面，最优化方法选取w使l1和l2的间隔达到最大。l1和l2分别为(w·x)+b=1和(w·x)+b=-1，与此对应的分类超平面l为(w·x)+b=0，间距为2‖w‖，得到如下规划。
minw,b12‖w‖2(1)
s.t.
yi((w·xi)+b)≥1,i=1,…,m(2)
求解其对偶问题得最优解w*和b*，分类超平面(w*·x)+b*=0和决策函数f(x)=sgn((w*·x)+b*)，式（1）和式（2）的求解可以转换为求解对偶问题中lagrange乘子，有如下的定理来说明。
定理1 若(w*,b*)为原始最优化问题(式（1）和式（2）)的解，其对偶问题有解α*=(α*1,α*2,…,α*m)，使得w*=∑mi=1α*iyixi，b*=yj-∑mi=1yiα*i(xi·xj)，其中下标j∈｛j｜α*j＞0｝。或者w*=∑mi=1α*iyixi，b*=-(w*·∑mi=1α*ixi)/(2∑yi=1α*i)，反之也成立。
但对于大规模数据分类一般不容易做到线性可分（见图2），可以对算法做如下的改进。
图2 非线性可分的情况
（1） 引入松弛变量ξ=(ξ1，…，ξm)T，∑mi=1ξi用来描述训练集错分程度，同时引入惩罚参数C平衡∑mi=1ξi和12‖w‖2。式（1）和式（2）变为
minw,b,ξ 12‖w‖2+C∑mi=1ξi(3)
yi((w·xi)+b)+ξi≥1,ξi＞0
i=1,…,m(4)
（2） 当问题是非线性可分时，通过使用核函数K(xi,xj)将线性不可分问题变为线性可分问题，将原训练集中的点映射到更高维的Hilbert空间中：Φ(x)∶x→X，令核函数K(xi,xj)=(Φ(xi)·Φ(xj))，即将内积(xi·xj)用核函数代替K(xi,xj)，则可以得到支持向量分类机。常用核函数有Gauss径向基核K(xi，xj)=exp(-‖xi-xj‖2/σ2)等。
2 基于SVM的DNA序列分类的方法
2.1 特征属性空间的构造与改进
由前面的叙述可以发现，使用SVM进行数据的分类，首先需要确立一个训练集T=｛(x1,y1),…,(xm,ym)｝∈(X×Y)m，其中xi∈X=Rn是一个特征属性向量空间；第二需要知道这部分训练集所属类别信息yi∈Y=(1,-1)，这是一种先验的数据分类问题。即构造出一个分类超平面(w·x)+b=0，其中w∈Rn为法向量，b∈R为偏度阈值。并利用此超平面实现对DNA序列集进行分类。
首要的问题是构造特征属性向量空间，每条DNA序列都是由4个字符A，T，C，G按一定顺序连续排成的长约30亿的序列，其中没有断点，这4个字符表示4种碱基。从现有的研究结果中发现，在不用于编码蛋白质的序列片段中，A和T的含量特别多，于是以某些碱基的含量作为分类特征去研究DNA序列可以是一种很好的选择。将构造出每条DNA序列的A，T，C，G含量作为四个特征属性。
定义2 当训练的DNA序列样本点集为(xi,yi)，i=1,…,l，则称X=(x1,x2,x3,x4)∈R4，为DNA序列的一个四维特征属性空间，xi=(xi1,xi2,xi3,xi4)∈X表示第i条DNA序列的四维特征属性值。
若设Length(xi)表示第i个DNA序列的长度，设countbases(xi) ，bases=A，T，C，G分别表示第i个DNA序列所含有的碱基对A，T，C，G的数量，那么令
x1i=countA(xi)Length(xi) x2i=countT(xi)Length(xi)
x3i=countC(xi)Length(xi) x4i=countG(xi)Length(xi)
则xi=(xi1,xi2,xi3,xi4)∈X称为碱基对A，T，C，G含量的百分比属性值，X为DNA序列的含量特征属性空间。
通过定义2可以得到一个特征属性空间X，其中属性值表示碱基对的百分比含量。通过观察数据发现不同种类的DNA序列的长度可能也存在差异性，所以希望也将此特性加入到分类因素中改进属性特征向量空间。
定义3 对DNA序列的含量特征属性空间X=(x1, x2, x3, x4)∈R4， 加入另外属性组X*=(x1,…,xn)到X中，得到X′=(X,X*)，称X′为X的扩充空间。
若令xi5=Length（xi）表示第i个DNA序列的长度，将此属性扩充到DNA序列的含量特征属性空间中得到新的特征属性空间X′=(xi1,xi2,xi3,xi4，xi5)。
2.2 分类超平面的求解
对于训练DNA序列样本集T=｛(x1,y1),…,(xm,ym)｝∈(X×Y)m，按照前面的方法构造特征属性空间X=(xi1,xi2,xi3,xi4，xi5)，由最优化问题式（3）和式（4）得到其对偶问题。
minα 12∑mi=1∑mj=1yiyjαiαjK(xi·xj)-∑mj=1αj(5)
∑mi=1yiαi=0,C≥αi≥0,i=1,…,m（6）
其中所选取的正分量α*j要求C＞α*j＞0。采用定理1得到分类超平面(w*·x)+b*=0和决策函数f(x)=sgn((w*·x)+b*)
3 相关数据实验
实验相关数据来自文献［6］，实验分为检测分类器精度实验和DNA大样本数据分类实验。已知类别的DNA序列即训练数据有20个，序号1~10 为A类，11~20为B类。其中一条A类和B类序列分为“aggcacggaaaaacgggaataacggaggaggacttggcac
ggcattacacggaggacgaggtaaaggaggcttgtctacggccgga
agtgaagggggatatgaccgcttgg”
“gttagatttaacgttttttatggaatttatggaattataaattta
aaaatttatattttttaggtaagtaatccaacgtttttattactttttaaa
attaaatatttatt”
分类数据共两组，第一组是序号为21~40的20条未知DNA序列样本；第二组是一个大样本集合，共182条DNA序列（见图3）。图3 实验流程图实验环境采用CPU为AMD Turion (tm) 642.01 GHz,512 M 内存，Microsoft Windows XP(SP2)系统， Matlab 7.0进行编程设计。
3.1 小样本分类器精度实验
首先使用前20条训练数据采用本文提出的方法构造特征属性空间，并采用SVM分类器训练得到分类超平面，并将原20条已知类别的DNA序列样本回带得到的分类结果与真实结果做比较，得到分类精确度。采用线性分类器，设置参数平衡因子C=300，得到最大间隔为：0.116 424。
使用分类器对20条训练样本的检测结果为1111111111-1-1-1-1-1-1-1-1-1-1，其中1代表A类样本点，-1代表B类样本点，分类正确率为100%。
上面实验表示由20个小样本空间构成的分类超平面，对检测集预测的结果可以发现本方法构造的分类器拥有很好的分类正确率，可以作为判别DNA序列类别的方法之一。
3.2 大样本分类及精度实验
采用前20个样本构造出的分类器进行判别实验（见表1）。
表1 分类结果表
类 别序 号A类DNA
序列样本23，25，27，29，34，35，37B类DNA
序列样本21，22，24，26，28，30，31，32，33，36，38，39，40
对182个大样本空间的分类（见表2），处理的步骤如下：
(1) 预处理数据集部分 对182个样本进行处理成matlab可以执行的数据格式；
(2) 学习产生分类器部分 使用已知的20个训练样本得到的分类器对这182个样本进行分类，其中采用line线性分类器和非线性rbf分类核函数，并设置相应的参数；
(3) 对分类器进行检测部分 对得到的182个已分的样本作为标准分类数据，并由此作为标准再次产生分类器，做精度测试实验：第一，产生分类器对已知的20个样本进行检测；第二，对182个样本进行回代检测。从而得到一系列的分类正确率。表2 分类器检测精度表
核函数参数设置结 果分类精度20个样本检验/%182个样本检验/%Line
Rbf
rbfC=300
C=300,P1=3
C>=8 000,P1<=3-1-1-1-1-1-11-1-1-1-11-1-1-1-1……
-1-1-1-11-1-111-1-1-11111……
-1-1-1-1-1-11-1-1-1-11-1-1-1-1……100
95
10097.25
关键词：SVM；DNA分类；特征属性空间；分类超平面
中图分类号：TP181文献标识码：A文章编号：1672-1098(2009)01-0058-05
收稿日期：2008-05-16
基金项目：国家自然科学基金资助项目（10501009）；安徽财经大学青年基金资助项目（ACKYQ0843ZC）
作者简介：徐健（1982-），男，安徽凤阳人，讲师，硕士，主要研究方向：支持向量机、模式识别、数据挖掘等。
A Classification Method of DNA Sequence Based on
Support Vector Machine
XU Jian1,LI Bai-nian1,ZHANG Kong-sheng1,JIANG Li-hua2
(1. School of Statistics and Applied Mathematics, Anhui University of Finance and Economics, Bengbu Anhui 233030,China;2. School of Sciences, Anhui University of Science and Technology,Huainan Anhui 232001,China)
Abstract:A new classification method of DNA sequence based on SVM was presented. The feature attribute space was established according to requirement of SVC. At first, four feature attributes were built by content of DNA’s four bases. By increasing length attribute of DNA sequence in the space to extent the feature attribute space. Finally, the classification of hyperplane was obtained on the basis of available samples training by using SVC in the feature attribute space. The DNA sequence to be classified was verified by the hyperplane. The results show that the classification method accuracy is very good.
Key words: SVM; classification of DNA; feature attribute space; classification hyperplane
基于统计学习理论的支持向量机(Support Vector Machine，SVM)是新近研究机器学习、数据挖掘和人工智能领域的一个热点。SVM将求解的问题最终归结为一个线性约束的凸二次规划问题，求出的解是全局最优的唯一解。SVM基于结构风险最小化原则，利用核函数将非线性问题转化为特征空间的线性问题。所以SVM在处理分类问题中一直有很好的表现。
2000年6月，人类基因组计划中DNA全序列草图完成，每条DNA序列由A、T、C、G按一定顺序排成长约30亿的序列，这4个字符表示了4种碱基。研究DNA全序列具有的结构和隐藏的规律，一直是生物信息学（Bioinformatics）最重要的课题之一。近年来使用SVM方法分析DNA序列的研究也在进行中，一些是对SVM方法进行改进并应用到DNA序列分类中，例如：使用SVM的几何修正法对DNA序列进行分析［1］；一些是对分类DNA序列中SVM所使用的特征属性提取方法进行讨论，例如：用窗口滑动来计算重复序列的出现频率，从而构造分类属性［2］；还用一些是针对DNA序列本身某一特性，结合SVM和其他方法进行比较得到更好的精度，例如：使用RS-GA-SVM方法分析DNA翻译起始点位置［3］，以及使用SGBP方法分析QSAMs模型，并采用部分最小二乘法（PLS）和SVM方法共同进行分类，并对两种方法的分类精度进行比较，最终提出SGBP-GA-SVM的处理步骤［4］。针对2000年全国大学生数学建模中提出的DNA序列分类问题，使用含量特征表示对DNA进行解构，结合SVM分类特性提出一种新的分类DNA序列的方法，此方法操作简便，分类效果精确，是一种对分类模型建模的有效方法。
1 SVM线性分类学习机
定义1 训练集T=｛(x1,y1)，…，(xm,ym)｝∈(X×Y)m,其中xi∈X=Rn，yi∈Y=｛1,-1｝，i=1,…，m。若存在w∈Rn，b∈R和正数ε，使得对所有使yi=1的下标i，有(w·xi)+b≥ε，而对所有使yi=-1的下标i，有(w·x1)+b≤-ε，则称训练集T线性可分。同时也称相应的分类问题是线性可分的［5］（见图1）。
图1 线性可分的情况
由图1可知，法向量为w时分类超平面并不唯一，l，l1和l2就是三个典型的超平面，最优化方法选取w使l1和l2的间隔达到最大。l1和l2分别为(w·x)+b=1和(w·x)+b=-1，与此对应的分类超平面l为(w·x)+b=0，间距为2‖w‖，得到如下规划。
minw,b12‖w‖2(1)
s.t.
yi((w·xi)+b)≥1,i=1,…,m(2)
求解其对偶问题得最优解w*和b*，分类超平面(w*·x)+b*=0和决策函数f(x)=sgn((w*·x)+b*)，式（1）和式（2）的求解可以转换为求解对偶问题中lagrange乘子，有如下的定理来说明。
定理1 若(w*,b*)为原始最优化问题(式（1）和式（2）)的解，其对偶问题有解α*=(α*1,α*2,…,α*m)，使得w*=∑mi=1α*iyixi，b*=yj-∑mi=1yiα*i(xi·xj)，其中下标j∈｛j｜α*j＞0｝。或者w*=∑mi=1α*iyixi，b*=-(w*·∑mi=1α*ixi)/(2∑yi=1α*i)，反之也成立。
但对于大规模数据分类一般不容易做到线性可分（见图2），可以对算法做如下的改进。
图2 非线性可分的情况
（1） 引入松弛变量ξ=(ξ1，…，ξm)T，∑mi=1ξi用来描述训练集错分程度，同时引入惩罚参数C平衡∑mi=1ξi和12‖w‖2。式（1）和式（2）变为
minw,b,ξ 12‖w‖2+C∑mi=1ξi(3)
yi((w·xi)+b)+ξi≥1,ξi＞0
i=1,…,m(4)
（2） 当问题是非线性可分时，通过使用核函数K(xi,xj)将线性不可分问题变为线性可分问题，将原训练集中的点映射到更高维的Hilbert空间中：Φ(x)∶x→X，令核函数K(xi,xj)=(Φ(xi)·Φ(xj))，即将内积(xi·xj)用核函数代替K(xi,xj)，则可以得到支持向量分类机。常用核函数有Gauss径向基核K(xi，xj)=exp(-‖xi-xj‖2/σ2)等。
2 基于SVM的DNA序列分类的方法
2.1 特征属性空间的构造与改进
由前面的叙述可以发现，使用SVM进行数据的分类，首先需要确立一个训练集T=｛(x1,y1),…,(xm,ym)｝∈(X×Y)m，其中xi∈X=Rn是一个特征属性向量空间；第二需要知道这部分训练集所属类别信息yi∈Y=(1,-1)，这是一种先验的数据分类问题。即构造出一个分类超平面(w·x)+b=0，其中w∈Rn为法向量，b∈R为偏度阈值。并利用此超平面实现对DNA序列集进行分类。
首要的问题是构造特征属性向量空间，每条DNA序列都是由4个字符A，T，C，G按一定顺序连续排成的长约30亿的序列，其中没有断点，这4个字符表示4种碱基。从现有的研究结果中发现，在不用于编码蛋白质的序列片段中，A和T的含量特别多，于是以某些碱基的含量作为分类特征去研究DNA序列可以是一种很好的选择。将构造出每条DNA序列的A，T，C，G含量作为四个特征属性。
定义2 当训练的DNA序列样本点集为(xi,yi)，i=1,…,l，则称X=(x1,x2,x3,x4)∈R4，为DNA序列的一个四维特征属性空间，xi=(xi1,xi2,xi3,xi4)∈X表示第i条DNA序列的四维特征属性值。
若设Length(xi)表示第i个DNA序列的长度，设countbases(xi) ，bases=A，T，C，G分别表示第i个DNA序列所含有的碱基对A，T，C，G的数量，那么令
x1i=countA(xi)Length(xi) x2i=countT(xi)Length(xi)
x3i=countC(xi)Length(xi) x4i=countG(xi)Length(xi)
则xi=(xi1,xi2,xi3,xi4)∈X称为碱基对A，T，C，G含量的百分比属性值，X为DNA序列的含量特征属性空间。
通过定义2可以得到一个特征属性空间X，其中属性值表示碱基对的百分比含量。通过观察数据发现不同种类的DNA序列的长度可能也存在差异性，所以希望也将此特性加入到分类因素中改进属性特征向量空间。
定义3 对DNA序列的含量特征属性空间X=(x1, x2, x3, x4)∈R4， 加入另外属性组X*=(x1,…,xn)到X中，得到X′=(X,X*)，称X′为X的扩充空间。
若令xi5=Length（xi）表示第i个DNA序列的长度，将此属性扩充到DNA序列的含量特征属性空间中得到新的特征属性空间X′=(xi1,xi2,xi3,xi4，xi5)。
2.2 分类超平面的求解
对于训练DNA序列样本集T=｛(x1,y1),…,(xm,ym)｝∈(X×Y)m，按照前面的方法构造特征属性空间X=(xi1,xi2,xi3,xi4，xi5)，由最优化问题式（3）和式（4）得到其对偶问题。
minα 12∑mi=1∑mj=1yiyjαiαjK(xi·xj)-∑mj=1αj(5)
∑mi=1yiαi=0,C≥αi≥0,i=1,…,m（6）
其中所选取的正分量α*j要求C＞α*j＞0。采用定理1得到分类超平面(w*·x)+b*=0和决策函数f(x)=sgn((w*·x)+b*)
3 相关数据实验
实验相关数据来自文献［6］，实验分为检测分类器精度实验和DNA大样本数据分类实验。已知类别的DNA序列即训练数据有20个，序号1~10 为A类，11~20为B类。其中一条A类和B类序列分为“aggcacggaaaaacgggaataacggaggaggacttggcac
ggcattacacggaggacgaggtaaaggaggcttgtctacggccgga
agtgaagggggatatgaccgcttgg”
“gttagatttaacgttttttatggaatttatggaattataaattta
aaaatttatattttttaggtaagtaatccaacgtttttattactttttaaa
attaaatatttatt”
分类数据共两组，第一组是序号为21~40的20条未知DNA序列样本；第二组是一个大样本集合，共182条DNA序列（见图3）。图3 实验流程图实验环境采用CPU为AMD Turion (tm) 642.01 GHz,512 M 内存，Microsoft Windows XP(SP2)系统， Matlab 7.0进行编程设计。
3.1 小样本分类器精度实验
首先使用前20条训练数据采用本文提出的方法构造特征属性空间，并采用SVM分类器训练得到分类超平面，并将原20条已知类别的DNA序列样本回带得到的分类结果与真实结果做比较，得到分类精确度。采用线性分类器，设置参数平衡因子C=300，得到最大间隔为：0.116 424。
使用分类器对20条训练样本的检测结果为1111111111-1-1-1-1-1-1-1-1-1-1，其中1代表A类样本点，-1代表B类样本点，分类正确率为100%。
上面实验表示由20个小样本空间构成的分类超平面，对检测集预测的结果可以发现本方法构造的分类器拥有很好的分类正确率，可以作为判别DNA序列类别的方法之一。
3.2 大样本分类及精度实验
采用前20个样本构造出的分类器进行判别实验（见表1）。
表1 分类结果表
类 别序 号A类DNA
序列样本23，25，27，29，34，35，37B类DNA
序列样本21，22，24，26，28，30，31，32，33，36，38，39，40
对182个大样本空间的分类（见表2），处理的步骤如下：
(1) 预处理数据集部分 对182个样本进行处理成matlab可以执行的数据格式；
(2) 学习产生分类器部分 使用已知的20个训练样本得到的分类器对这182个样本进行分类，其中采用line线性分类器和非线性rbf分类核函数，并设置相应的参数；
(3) 对分类器进行检测部分 对得到的182个已分的样本作为标准分类数据，并由此作为标准再次产生分类器，做精度测试实验：第一，产生分类器对已知的20个样本进行检测；第二，对182个样本进行回代检测。从而得到一系列的分类正确率。表2 分类器检测精度表
核函数参数设置结 果分类精度20个样本检验/%182个样本检验/%Line
Rbf
rbfC=300
C=300,P1=3
C>=8 000,P1<=3-1-1-1-1-1-11-1-1-1-11-1-1-1-1……
-1-1-1-11-1-111-1-1-11111……
-1-1-1-1-1-11-1-1-1-11-1-1-1-1……100
95
10097.25