翻译Class imbalance s for translation initiation site recognition in DNA sequences.docx

对于在序列中翻译初始地点识别的分类不平衡方法摘要翻译初始地点（）识别是基因结构预测的第一步骤之一，也是任何基因识别系统的普遍构成之一。许多转录序列在辨别TIS的方法已经在文献中被形容，比如MRNA，EST和cDNA序列。但是TIS和DNA序列的识别仍是一个挑战，而且目前为止，在DNA 序列中转录而描述的方法还没什么结果。大多数方法可以在生物特征上解释问题。本文中，我们尝试一个不同的角度，把这个分类问题完全看做一个单纯的机器学习。从机器学习的角度来看，TIS识别是分类不平衡问题。因此，本文中我们从这个角度接近TIS识别，并应用不同的已经被发展用来解决不平衡数据的方法。提出的方法有两个优点。第一，它提高了用标准分类方法的水平。第二，它拓宽了分类算法可用的集合，如一些分类不平衡方法（比如采样不足）也被用作放大数据挖掘算法，如它们减少数据的大小。在种方法，分类器不能应用于全体数据（因为长训练时间或者大量的记忆要），可以被用在要使用采样不足方法时。结果显示一个分类不平衡方法的优势，【同时同样的但没有考虑分类不平衡的自然问题的方法应用】。应用方法也可以在文献中提到的最好的方法下提高结果的获得，这基于寻找下一个来自于推定一定被预测的框架内的终止密码子。. 介绍识别组成以识别起始密码子，ATG（在大多数基因中标志转录的开始）。大多数之前的方法已经致力于在转录中识别TIS。但是，在基因组序列中识别TIS是不同的，而且更困难的工作。全长或部分转录经常包括1或0，而且没有基因内区。另一方面，在一个一般的基因组序列中，我们可以找到密码子，然后一个可能在任何地方的推定的。在本文中，我们考虑分析基因序列最为不同的问题，它包括废弃DNA，外显子，基因内区和非翻译区终止区（URTs）。后者还包括转录。识别TIS在转录和基因组序列中不同的特点被在每一个问题不同的预测表现中阐明。TISMiner1是最好的TIS在转录中的识别的项目，在灵敏度为80%时可以明确的实现98%。但是，当测试放在基因组序列中时，在同样灵敏度水平下结果的实现降到50%。从生物的观点，在基因序列中的TIS识别有一些特殊性，这将使得问题比在RNA序列中更为困难2：扫描模型不能被应用在基因序列中除非转录起始点已知，这不是我们要解决的问题；转录特别的包括0或1TIS，它会明显的促进识别；基因组数据包括基因内区，它破坏编码结构TIS下游而且真核基因组包括百万计的候选TIS，这要求TIS预测系统可以被有效的计算实现。在基因组序列TIS预测中最重要的特征之一是消极的实例远多于积极的实例。在机器学习理论中，这被称作分类不平衡问题3,4。大多数的学习算法期望一个无论怎样在不同的分类间平衡的分布。已经显示经历歪斜分布的学习算法与分类不平衡相联系。大多数TIS识别没有考虑从分类不平衡方法中解决这个问题。但是，问题是可以高度不平衡的。在我们的检测数据中，我们积极/消极的比例是1：25，1:93和1:123.在低水平的编纂的序列中，比如人类21号染色体。可以达到1:4912的比例。本文中，我们把TIS识别当做一个分类不平衡问题。我们检测分类不平衡问题是否能对于那些针对为从生物角度进行TIS识别而设计的方法实现同样的表现。该工作还检测一些最广泛使用的分类不平衡方法在一个困难的现实问题中的使用情况。因此，这给予这些方法在困难问题的应用上一个有趣的评价。本文的组织如下：第二部分概述了分类不平衡问题最重要的方向和我们将使用到的方法；第三部分展示实验步骤；第四部分展示所得结果；最后第五部分说明我们工作的结果和未来的研究路线。. 分类不平衡问题在类的训练实例中大多数分类法是不平衡分布这一点已经被反复显示5。【大多数学习算法期待一个在不同程度上不同类的大概的甚至分配的实例】。解决分类不平衡问题是很困难的，而且一个非常相关的问题，如许多大多数有着非常不平衡分布的有趣且有挑战性的的像是问题，比如基因识别，指令发觉，网络挖掘等。大多数这类问题表现为两类数据。一类【interesting】，积极的类，在数据中没有被高度表现，另一类是有许多实例的消极类。在高度不平衡问题中，正负 比例可以达到1:1000或1:10000。许多算法和方法已经打算改善分类不平衡对学习算法表现的影响。主要有三种不同的方法：1（1） 内部作用于算法。这个方法修改学习算法来解决不平衡问题。它们可以改编结果临界值来创造对少数类的偏向或者引入学习过程中的损失来补偿少数类。（2） 外部作用于数据。这个算法作用与数据而不是学习方法。 它的优点在于独立于分类器的使用。这里用两个基本的途径，过多对少数类采样或过少对多数类采样。（3） 结合基于推进8考虑训练集合不平衡的方法。这个方法修改基本推进方法来解决少数类在数据集中的不被表现。 【sampling against cost sensitive methods】有两个主要的优势。第一，采样法更加普通因为它不会有改编一个有着分类损耗的已有算法的可能性。第二，学习算法不被修改（修改会造成许多困难而且要添加额外的参数来调整）。数据调动算法可以被广泛的分类两组。多数类采样过少和少数类采样过多。也有一些算法结合两种处理方法。采样过少和采样过多都被随机做到，或者一个更复杂的的处理搜索最少/最多的游泳有用数据。早期的工作已经显示多数类采样过少经常导向一个比少数类采样过多更好的结果，至少在过量采样代替少数类时结果是这样的。然后少数类过多采样和多数类过少采样结合使用没有多数类过少采样结果好。少数类采样过多表现更差的一个可能的原因是没有新的信息在训练集里被引入，因为采样过量必须依赖于增加已经在数据集里的新的少数类实例的复制品。2.1过少采样和探究过少采样对于平衡数据集的第一种方法是过少采样多数类指导两类有相同的实例数量。我们没有用过多采样少数量因为大多数前期的功过认为过少采样比过多采样表现更好。但是，有些工作呈现了相反的发现11。此外，当我们解决非常大的数据集时过多采样会让数据集是原来的两倍。防止一些最有趣的分类器的使用，比如支持向量机器。随机的过少采样随机由来自多数类的随机移除实例组成（移除直到达到一个确定的标准）。在大多数工作中，实例被移除直到两类有相同的实例数。一些研究比较复杂的过少采样和随机的过少采样，没有成功找到前者的明显优势。因此，在这个问题上我们考虑先随机过少采样。但是随机过少采样会让许多可能有用的样本被忽略。这样，在多数/少数的比例很大时，随机过少采样的表现会被削弱。而且，当少数类的数量非常少时，我们还要解决训练数据少的问题。Liu.et al.13提出两个结合过少采样和助推的全体方法来避免这个问题。这个方法被叫叫做过少采样探究过少采样。两个提及的方法被叫做EasyEnsemble（EE）和BalanceCascade（BC）。我们在实验两者后对这两种方法有更细节的描述。EE由被反复应用的对于多数类的不同样本的标准全体方法ADABOOST14组成。算法1显示了EE法。EE法背后的想法是从多数类产生T平衡子问题采样。EE一个探索消极实例集的无监督策略，N，没有应用到前期的全体中成员分类表现的信息的一种采样。另一方面，BC法在监督下探索N，从多数类中移除的实例已经在之前加在总体中的分类器真确的分类过了。BC法如算法2所示：2.2 SMOTE-N过多采样的一个问题是它仅仅做了少数类样本的拷贝而没有加入新的数据集，而且学习方法不能明显的提高分类的少数类。为了解决这个问题，Chawla et al.5提出了一个方法叫做SMOT，它可以结合多数类过少取样和少数类过多取样。但是，代替了少数类过多取样只是拷贝了少数类的样本，SMOT从少数类里已有的实例里形成了综合实例。综合样本生成如下：考虑特征向量（样本）间的不同和它的邻近者。将这些不同随机乘上0和1，并把这些考虑的特征向量加起来。这会造成在沿着线两个特征分割随机点的选择。我们可以形成新的样本，这些样本分享了更多稠密数据集的现实实例的主要特点。原始的算法提及了数值属性。但是，一个叫做SMOTE-N的算法也我们问题中的所谓的属性。形成这个综合样本子集SMOTE-N的程序如算法3所示。SMOTE-N与标准的SMOTE的不同在于使用了VDM的改进版本（由Cost和Salzherg15形成），而不是Euclidean距离，如我们的实例，DNA苏冽，只用名义上的属性。2.3 评估措施精度对于不平衡数据来说不是一个有用的量度，特别是当实例中的少数类与多数类相比非常小的时候。如果比例为1：100，那么分给所有多数类实例的分类器的精度为99%。一些方法6已经被发展用来问题的不平衡属性。给出true positive(TP), false positive(FPP), true negative(TN), 和false negative(FN)的比例，我们可以给出一些方法。大概最常用的方法是true positive（） 率，recall(R)或者sinsitivity(Sn)：如果我们只对积极类的表现感兴趣的话它将有很大的作用；true negative 率（）和specificity（SP）：除了这些基本的方法中，其他方法也被提及，比如F法，或者如果我们同时考虑献计和积极类在G平均17上的表现：许多有着一些理解值的分类器可以多变的来实现以上方法的不同值。对于这种分类器接收者操作特征（ROC）曲线可以被构造。一个ROC曲线，是一种反对（1-或者）对二元分类器系统的图线，它的区分临界值是多变的。完美的模型可以实现TP率为1而FP率为0。一个随机的猜想将被用一个包括（0,0）和（1,1）的线表示。ROC曲线是一个评价分类器表现的好方法。进而，从这个曲线中，一个新数据，曲线下的面积（AUC），可以被获得。AUC可以建立一个分类器之间的主导关系。如果ROC曲线是交叉的，全部的AUC是一个模型18间的平均比较.在我们的实验中，我们将使用ROC曲线作为只要的比较工具。数值方法我们可以选择从梯形数值计算法获得的AUC值。Saeys et al.2发展了现行的最好的模型并且比较在使用其他方法得到灵敏性为80%的特异性时它们的建议。为了可以很好的比较这些方法，我们也将使用灵敏度为80%并且展示一定的特异性的数据。 . 验步骤 在解决分类不平衡的不同方法中，我们已经在文中选择了一些成功率最高的方法，如我们在之前的部分所提到的。我们用随机过少采样，SMOTE-N，BC和EE。其他的方法尝试下来会有较差的结果。我们必须考虑前两个是单独的分类器方法，而后两个是全体方法。由于它们增加的复杂性，BC和EE必定会得到一个与过少采样和SMOTE-N向比明显更好的结果。我们用C4.5决策树19，一个支撑向量机制（SVM）20和一个k-nearst邻居（k-NN）分类器作为基本学习者。一些非常有理的学习算法将可以被得到。尽管还有许多其他方法可用，这三个通常来说在大多数关于分类的论文中最好的。当然也有其它原因。我们使用决策树因为它可以在数值上很快的得到结果，而且是全体的很好的学习者。SVMs被包括，因为它们通常来说是在分类问题中最好的方法，特别对于分为两类的问题，而且对于有许多输出的问题也很有效。最后k-NN法被用到因为它简洁有效，而且在其他现实实例中得到了很好的结果，比如计算机图形学21和其他生物信息学领域22。我们做实验用k-重叠-交叉-确认法来设置参数值，k=10。对于每一个用到的分类器，我们得到一组不同的最好参数。对于SVMs，我们尝试一个的线性核心，和一个的Gaussian核心，检验所有的21种可能性。对于C4.5我们检验1和10个实验并且减轻它们的临界值一尝试所有的4个可能组合。对于k-NN，k的值用间距为10的重叠-交叉-确认法得到。重叠-交叉-确认法还被用来设置如下参数：每次一个被训练的分类器，训练组被分为k部分。然后每一组的参数被这k部分标准k-重叠-交叉-确认法评估。这样，为了评估每一个子集的参数，每一个k部分被用来检测参数表现然后剩下的k-1部分用来训练数据。当所有的参数集被评估后，选出最好的一组然后训练数据在所有训练集和参数集下训练。G平均被用做评估每一组参数的方法。所有的评估都被用来检验错误然后得到最好的参数集如图1所示（k=10）。原始资料编码，在C而且在下可同行，为所有的方法和数据组所用，在作者的要求下都是可得的。补充使用的图书馆。.数据组我们用了三组数据组来检验所述方法的结果。数据组被从一致数据库中编译。工程是一个被精确的注释的对于编译和辨别人类基因核的相关的成就。注释是手动和自动的结合注释。包括个消极样本和个积极样本，积极/消极是1:25。Ustilago数据集是一组编码和未编码的来自真菌Ustilago maydis（U）排序的基因序列标识符。序列首先在Broad Institution得到，然后通过给蛋白质序列的Munich 信息中心（MIPS）完善。Ustilago数据组包括607696个消极样本和6515个积极样本，其比为1:93。Arabidopsis （A）数据集包含植物Arabidopsis thaliana编码和未编码的标识符从“Arabidopsis信息资源”（TAIR）获得。这个数据集包括27342个积极实例和3369875个消极实例，不平衡比例为1:123。 为了估计实验的错误，我们使用k-重叠-交叉-确认法。在这个方法中，可得的数据被分为k个大致相等的子集。然后，方法被学习k次，k子集中的数据轮流使用作为检验组，剩下的k-1个子集作为训练组。估计的错误是k个子集的平均检验错误。我们是一个标准值k，k=10。 我们的目标是在不同的数据集下检验提出的方法来研究问题更困难是不是取决于生物体。因此，我们用三种完全不同物种的数据集。CCDS数据集包括人类DNA，因此它有很长的基因，有许多外显子和潜在的基因内区。另一方面，U的数据集包括更短的基因，有很少的外显子，通常只有1-2个，或者少而且短的基因内区。A的复杂性来在两者之间。在这样的数据集下，我们可以学习在不同环境下提出的方法的行为。 对所有的数据集，我们考虑一个有着每个ATG密码子上下游都有500bps的序列。分类器可以解决所谓的属性，C4.5和k-NN，我们使用原始的序列。对于那些需要数值属性的分类器，SVMs，我们用1/4编纂，序列上每一个元素总共有4012输出。对于k-NN分类器，我们用海明距离，然后为每一个相邻值的选票已经赋有权重。这样，对于一个已给的疑问实例x，第i个邻近值的选票，得到权重，根据：. 实验结果在第一步，我们想要建立过少采样的实用性。图2-4分别展示了C4.5，k-NN和SVM分类器对于所有数据集的ROC曲线。这些曲线展示出一个在使用所有数据集的分类方法和相同分类器使用随机过少采样之间的比较。ROC曲线展示了标准分类器方法在面对分类不平衡数据时的问题。对于U的数据集，C4.5不能在两类里面分类所有的实例得到有用的数值依赖于使用的临界值。对于CCDS，C4.5得到了更好的结果，尽管和我们将要展示的其他方法相比没有竞争力。对于A，结果比U的更好，但是反对采样过少的话可以得到一个很大的提高。采样过少在U和A上对于提高结果又很大的帮助。CDDS的也更好，但是区别分有那么明显，但比没有过少采样的C4.5有更好的表现。k-NN的ROC的曲线展示更明显的区别。过少采用坚实的提高了k-NN的表现。对于CDDS，不同是很明显的，得到了更高的灵敏性。对于U，表现就更好了。过少采样让k-NN从一个很一般的水平变成对这些数据集来说表现最好的算法之一。对于A的观察也是这样，有一个很显著的提高。对于SVM，对所有实例SVM下的表更好，但是过少采样仍对它有一个显著的提高，特别是对于CCDS和A。SVM的表现在U上也很显著，几乎与AUC下的过少采样相一致。我们的第二步是比较过少采样和之前描述的更复杂的方法SMOTE-N的表现。我们想要检验增加SMOTE-N的复杂性是否会提高表现。 图5-7比较了用过少采样和SMOTE-N对所有分类器的结果。用C4.5和SVM的表现是一样的。这两个分类器的结果在过少采样和SMOTE-N下没有多大不同，都有更好的表现在每一个依赖于数据集和分类器的方法上。对于k-NN，结果有些不同，SMOTE-N总是比过少采样结果差，尽管差别不大。因此得到一个一般的规律，SMOTE-N不能提高标准过少采样的结果。这并不意味着SMOTE-N没有用，尽管我们可以得出结论数值属性的版本不是很有效。4.1全体方法我们实验的下一步致力于全体法。在之前的实验中我们已经展示了过少采样和SMOTE-N在提高分类器表现的效果。在这一部分，我们展示两个如上应用全体方法的结果。参数的选取跟从作者13的建议。为了简化和平衡落下的全体，我们构造4ADABOOST全体，T=4，十个分类器。这两个方法应用C4.5和SVM作为基本学习者。K-NN没有什么用，如显示的那样这个分类器不想一个全体成员那样有效。图8展示了简化和平衡下落的全体的ROC曲线。我们包括了C4.5和SVM在最好分类不平衡方法，过少采样或SMOTE-N，对每一个数据集的表现图线作为比较。对于C4.5，两个方法的表现对于这三个数据集来说非常相近。我们可以看到，这些全体方法的表现明显的比C4.5在过少采样或SMOTE-N下像的平衡数据一样使用时的结果要好。但是，也必须考虑到它们的复杂性更高，因为这些全体是由40个分类器组成的。我们试着扩大全体，但是增加分类器不能明显的提高表现。事实上25，全体的表现在一开始的几个分类器被训练之后就不会改变了即使我们增加了更多的分类器。对于SVM，结果是的EE比BC好好。但是两个全体法都比过少采样或SMOTE-N明显的要差。已经显示SVMs作为全体的成员并不像决策树表现的那么好26。我们的结果证实了这个事实。4.2 与state-of-the-art方法的比较一旦我们建立了过少采样和SMOTE-N的功能，我们还想比较这些方法是否能提高目前为止表现最好的终止密码子法2的结果。这个方法考虑终止密码子频率TIS的下游。这个方法的基本原理如下：TIS被它们表现起始外显子描绘，所以我们知道起始外显子的读取框架。总的来说起始外显子有最小的长度，而且这将是在TIS下游最小的序列，不包含一个框架内的终止密码子。另一方面假冒的TIS不会有这个，因此，一个框架内的终止密码子可以被用来区分真假TIS。一个简单的预测可以被构造，考虑跟着一个有着框架内终止密码子假定TIS的区域。框架内终止密码子越早在这个区域出现，这个推定的TIS越不可能是真正的TIS。为了得到一个简单的在的构造观察外的分类器的得分方程，Saeys et al.计算（积累）了对于训练集积极例子观察到一个框架内终止密码子的可能性。结果显示，在两个数据集框架内终止密码子积累区分由很大的不同。然后，对于每一个实验例子，方法扫描了序列的下游部直到找到一个框架内的终止密码子。对这个首先出现的一个框架内的终止密码子，方位x被记录，然后模型检查来找到在x处有一个第一框架内终止密码子跟随者一个真的TIS的可能性。这个最后的比较现实提出的方法和基于将终止密码子频率作为底线的方法的结果的比较。我们还想检验终止密码子方法的原理是否适用于和人类基因组不同的U和A。图9-11展示了底线终止密码子法和表现最好的方法在每个分类器上的比较。我们用拉领个数值进行比较。首先，我们考虑检验错误。为了比较这两个不同的方法，我们设置灵敏性为80%并且测量在这个灵敏性水平下的特征。我们选择合个灵敏性水平因为这也是saeys et al2使用的。图12展示了对于所有方法特征的一组图线和数值。作为第二种方法，我们使用ROC曲线的AUC展示如上。如之前描述的，AUC是一个比较不同算法全部行为的不错的数值。AUC的数值和一组图线结果如图13所示。第一个有趣的结果是终止密码子方法对于U和A数据集表现很好，这种方法也的到CCDS的很好的结果。两个值都有相同的表现。我们看到终止密码子法是在这些结果中如果我们考虑它是一个很简单的方法的话最成功的一个。这些值也证明在没有不平衡分类法下的分类器应用表现不好。另一方面，使用即使是最简单的采样过少也能很显著的提高表现。事实上，采样过少的SVM或者SMOTE-N可以在三个数据集的AUC数值上打败终止密码子法。K-NN在采样过少或者SMOTE-N下在U数据集上打败终止密码子法。尽管采样过少也对C4.5分类器有用，在没有采样过少下C4.5糟糕的结果令C4.5和采样过少或SMOTE-N不那么有用（即使有所提高）。当我们使用决策树作为基本学习者时，全体法对提高基本分类器的表现可别有用。简单和平衡的额叠层全体，于CCDS和U数据集的终止密码子相联系，都能得到很好的表现，而且很明显的比他们的基本分类器C4.5的表现要好。为了比较AUC的使用，我们还表现了一个统计学的检测来确定是否观察到的不同在统计学上有意义。由于我们对比在同样的问题上使用10-重叠-交叉-确认法的不同结果，我们选择修正的重新取样t