1、2023 年1 月Jan2023DigitalTechnology&Application第 41 卷第 1 期Vol.41No.1数字技术与应用6中图分类号:Q523 文献标识码:A 文章编号:1007-9416(2023)01-0006-04DOI:10.19695/12-1369.2023.01.02基于位置信息的 DNA 序列特征提取*深圳大学陈煜元周小安DNA 序列的分类是生物信息学的主要研究任务之一，如何提取 DNA 序列中的特征是影响分类精度的重要因素。为了更好地保留序列中碱基的信息，本文提出了一种基于碱基距离和相关性的特征提取方法。以 H1N1、H5N1、COVID-19 等
2、6 种病毒作为研究对象，将 DNA序列转化为特征向量，并用 KNN 算法对冠状和非冠状病毒进行分类。实验结果表明该方法能提高分类的准确率。据估计地球上约有 1000 万 1 亿种生物，如此庞大的数据使得生物分类面临着巨大挑战1，因此 DNA 序列的分类成为了人们的研究热点，也是当前生物信息学的主要研究任务之一。特征提取是 DNA 序列分类研究中至关重要的一环，旨在最大限度保留原序列数据的基础上将序列转化为数值特征，以挖掘其中所存在的生物规律。随着计算机技术的发展和测序技术的不断进步，碱基的组成和分布信息在 DNA 序列特征提取中备受关注2。最基本的特征提取方法为 K-mers3，该方法随着 k
3、 的增大特征维数呈现指数级的增长，而在训练样本不足的情况下高维数据的研究会带来“过拟合”“维数灾难”等问题4，故 k 的取值不能太大，而特征维数不足可能会丢失序列中的重要信息。此外，K-mers 方法忽略了碱基的距离和排列情况5。因此，本文拟提取出基于相同碱基间距离和不同碱基间相关性的特征用于病毒序列分类。该特征提取方法以 DNA 序列中碱基的位置为基础，分别记录各碱基出现的位置，再通过合适的数学方法计算出平均距离和相关系数。实验结果表明，新的特征提取方法在KNN 分类器上能取得较好的分类效果。1 KNN 算法1.1 KNN 简介K 近邻（K-Nearest Neighbor）算法简称 KNN
4、，是Cover 和 Hart 在 1968 年时首先提出的。它是一个在理论上较为成熟的算法，也是最常用、最简单的机器学习算法之一。由于和其他分类算法相比没有显示的学习过程，所依据的“多数决定”的思想很容易理解，在多分类问题上表现的比其他分类算法要好，而且计算过程经过优化后能够大幅降低计算次数，因此在分类领域有着广泛的应用6。算法的原理是将待分类的样本与训练集的样本逐一计算出距离，按距离从小到大进行排序，然后取出最近的 K 个训练样本，这 K 个样本中数量较多那一类即为测试样本的类别。1.2 距离的计算KNN 计算序列样本之间距离的方法主要有曼哈顿距离、欧式距离和闵可夫斯基距离等，本文采用的是欧
5、式距离法。令训练样本为 X，特征的向量表示为(x1,x2,xn)，测试样本为 Y，特征为(y1,y2,yn)，则它们的欧式距离如式（1）所示：d(X,Y)=(xi yi)2ni=1(1)Dn=DnjCn-11Cn 1(5)DA=7+2+2+2+4+26=3.17(6)Sn(x)=ll0 x Ln1Lnix=Lni;i=(1,2,.,Cn)Lni+1+Lni2Lni x Lncn(9)r=(Xi X-)(Yi Y-)ni=1(Xi X-)2ni=1(Yi Y-)2ni=1(12)(1)式中 n 表示 X 和 Y 的特征维数，若 n=2 相当于计算平面上两点之间的距离，n=3 相当于计算三维空间中
6、两点的距离。上式计算的是一个训练样本和一个测试样本之间的距离，实际的分类问题中往往有 m 个训练样本X1,X2,Xm，需分别计算待分类样本与每个训练样本的距离 d(Xi,Y)(i=1,2,m)，从小到大排序后再进行下一步工作。1.3 K 值的选取K 值的选取是 KNN 算法中至关重要的一环，取值太小容易导致过拟合，太大则会使得分类误差增大。不收稿日期：2022-07-14*基金项目：深圳市高等院校稳定支持计划项目（89402060020）作者简介：陈煜元（1998），男，广东汕尾人，硕士研究生，研究方向：非线性序列数据分析。指导老师：周小安（1968），男，湖南益阳人，博士，副教授，研究方向：
7、混沌系统、保密通信、非线性系统理论。2023 年第 1 期7陈煜元周小安：基于位置信息的 DNA 序列特征提取仅如此，K 值有时能直接影响到分类结果。如图 1 所示，假设一个二分类问题，蓝色正方形代表类别 A，绿色三角形代表类别 B，红色圆形为待分类样本 X。若取 K=3，即把距离最近的 3 个样本作为依据，此时类别 B 的个数为 2，类别 A 的个数为 1，此时 KNN 会将待分类样本归为类别 B；而取 K=5 时显然类别 A 的个数比类别 B 的多，则 X 会被归为 A 类。图 1 K 近邻算法Fig.1 K-nearest neighbors为了降低上述情况带来的影响，可以采用距离加权的
8、方式，给每个已知类别的样本赋予权重，其值和训练样本与测试样本之间距离成反比，这样就使得较相似的样本点在分类上具有更高的权重。本文将通过经验法选取合适的 K 值，即对不同的 K 值进行重复实验，得到一个使分类准确率最高的结果。2 序列特征的提取2.1 基于碱基频率的特征提取这是一种比较典型的特征提取方法，即 k-mers 法，以各碱基或碱基组合在 DNA 序列中的频率作为特征。由于碱基的种类有 4 种，故对于 k(k=1,2,3,)个碱基的组合，共有 4k种组合方式。单碱基有 A、T、G、C 4 种，在不同 DNA 序列甚至同一序列的不同片段中，每种碱基出现的频率也是不相同的。设一条含有 m 个
9、碱基的序列，其中碱基 n 的个数为 c，则碱基 n 的频率可记为 Pn=c/m。把 4 种碱基的频率用向量表示如式（2）所示：P=(PA,PT,PG,PC)(2)其中 Pi(iA,T,G,C)表示碱基 i 在序列中出现的频率。双碱基有 AA、AT、AG、AC、TA、TT、TG、TC、GA、GT、GG、GC、CA、CT、CG、CC共 42种，即 16种组合方式。实验采用滑动窗口算法对各双碱基的个数进行计算，这样可以降低碱基缺失对实验结果的影响。一条含有 m 个碱基的序列，用滑动窗口法得到的双碱基共有 m-1 个，故双碱基 n 的频率可记为 Pn=c/(m-1)，c为双碱基 n 出现的次数。可将双
10、碱基在序列中的频率表示为如下 16 维向量：P=(PAA,PAT,PAG,PCC)(3)其中 Pij(i,jA,T,G,C)表示碱基 ij 在序列中出现的频率。基于三碱基的表示方法共有 64 种组合，同样用滑动窗口法计算出各三碱基的频率，将其用如下 64 维向量表示：P=(PAAA,PAAT,PAAG,PCCG,PCCC)(4)其中 Pijk(i,j,kA,T,G,C)表示碱基 ijk 在序列中出现的频率。基于四碱基组合的表示方法共有 44即 256 种，五碱基的共有 1024 种，随着 n 的增大组合方式呈指数型增长。在实际的机器学习算法中，太多的特征会使得计算的时间成本增加，且可能导致过拟
11、合。此外，多个碱基的组合在序列中出现频率较低，故不考虑 3 个碱基以上的频率作为特征输入。上述基于碱基频率的特征提取方法虽然能取得较好的分类效果，但是并不能表达出碱基的位置信息。本文提出一种新的 DNA 序列特征提取方法，与 k-mers 方法不同的是，新方法在考虑了碱基频率的基础上还包含了序列中碱基的距离和相关性信息。2.2 基于碱基位置信息的特征提取2.2.1 基于碱基距离的特征提取仅用碱基的频率还不足以描述一条 DNA 序列，因为两条完全不同的序列可能会出现相同的碱基频率，如以下两条长度为 20 个碱基的序列：序列 a：ATCGC GCAGA GATAT CTATA序列 b：GCACA
12、TCAGA TCAGA TATGT序列 a 和序列 b 的 A、T、G、C 含量完全相同，双碱基含量和三碱基含量如 AT、AG、TC、GCA、TAT等也有相同或相似之处，但这却是截然不同的两条序列。因此，为了使得分类更加准确，可用一种新的基于碱基距离的特征表示方法，即碱基（或碱基组合）之间的平均距离来描述一条序列。设有一条长度为 m 的 DNA 序列 S=s1,s2,.sm，用 Cn表示碱基 n(nA,T,G,C)的个数，Lni来表示碱基 n 在序列中第 i 次(i=1,2,Cn)出现的位置，则相邻碱基 n 之间的距离 Dnj=Lnj+1-Lnj(j=1,2,Cn-1)，序列中碱基 n 的平均
13、距离为：数字技术与应用 第 41 卷8d(X,Y)=(xi yi)2ni=1(1)Dn=DnjCn-11Cn 1(5)DA=7+2+2+2+4+26=3.17(6)Sn(x)=ll0 x Ln1Lnix=Lni;i=(1,2,.,Cn)Lni+1+Lni2Lni x Lncn(9)r=(Xi X-)(Yi Y-)ni=1(Xi X-)2ni=1(Yi Y-)2ni=1(12)(5)以序列a为例，碱基A的个数CA=7，位置分别为LA1=1，LA2=8，LA3=10，LA4=12，LA5=14，LA6=18，LA7=20，相邻两个碱基A之间的距离DA1=7，DA2=2，DA3=2，DA4=2，DA
14、5=4，DA6=2，可算出其平均距离：d(X,Y)=(xi yi)2ni=1(1)Dn=DnjCn-11Cn 1(5)DA=7+2+2+2+4+26=3.17(6)Sn(x)=ll0 x Ln1Lnix=Lni;i=(1,2,.,Cn)Lni+1+Lni2Lni x Lncn(9)r=(Xi X-)(Yi Y-)ni=1(Xi X-)2ni=1(Yi Y-)2ni=1(12)(6)同理碱基 T 分别位于第 2，13，15，17，19处，故碱基 T 的平均距离 DT=3.4；用该方法算出碱基 G和碱基 C的平均距离分别为 DG=2.33，DC=4.33。对于序列 b 也用此法计算得：DA=2.3
15、，DT=3.5，DG=6，DC=3.33，即：Da=(DA,DT,DG,DC)=(3.17,3.40,2.33,4.33)(7)Db=(DA,DT,DG,DC)=(2.30,3.50,6.00,3.33)(8)其中 Da、Db分别表示序列 a 和序列 b 中碱基 A、T、G、C 的平均距离向量。可看出在单碱基含量相同的情况下，碱基之间的平均距离可能会有较大的差异。对双碱基的平均距离和单碱基的计算方法类似，碱基组合的位置以第一个碱基为准。例如要计算序列 a中碱基组合AT 的平均距离，可找出 4 个 AT，其中碱基 A 的位置分别为 1、12、14、18，故 AT 的平均距离 DAT=5.67；同
16、理序列 b 中 AT 的平均距离 DAT=4。碱基 AT 在序列 a 和序列 b 中含量相同（都是 4 个），平均距离却有所差异，这正说明了我们不能只关注序列中碱基的含量而忽略了碱基的距离信息。2.2.2 基于碱基相关性的特征提取序列中不同碱基之间的相关关系也是区分不同种类生物的重要特征之一，将碱基 n 的位置分布记作 Sn(x)(x=1,2,m)，其定义为：d(X,Y)=(xi yi)2ni=1(1)Dn=DnjCn-11Cn 1(5)DA=7+2+2+2+4+26=3.17(6)Sn(x)=ll0 x Ln1Lnix=Lni;i=(1,2,.,Cn)Lni+1+Lni2Lni x Lncn(9)r=(Xi X-)(Yi Y-)ni=1(Xi X-)2ni=1(Yi Y-)2ni=1(12)(9)式中 Lni表示碱基 n 在 DNA 序列中第 i 次出现的位置，Cn表示碱基 n 的个数。在碱基 n 第一次出现之前，位置记为 0；两个碱基 n 之间的位置记为它们的平均值；最后一个碱基 n 之后的位置都记为最后一个碱基 n 出现的位置。以序列a为例，CT=5，LT1=2，LT2=13，L
