（计算机软件与理论专业论文）基于机器学习方法的生物序列分类研究.pdf

19 i+“，心蛐斌礓l目1 i i r e s e a r c ho nb i o l o g i c a ls e q u e n c ec l a s s i f i c a t i o nb a s e do nm a c h i n e l e a r n i n gm e t h o d s t h e s i ss u b m i t t e dt o s h a n g h a ij i a ot o n gu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e m f o rt h ed e g r e eo f d o c t o ro fp h i l o s o p h y b y y a n g y a n g ( c o m p u t e r s o f t w a r ea n dt h e o r y ) t h e s i ss u p e r v i s o r ：p r o f l ub a o l i a n g j u n e ，2 0 0 9 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名：场哟 e l 期：趟年正月彤e l r 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密阢 ( 请在以上方框内打“4 ) 学位论文作者签名：韧吻 日期：加4 年月日 指导教师签名： 易玄陟 隅矽疑j 踞 上海交通大学博士学位论文答辩决议书 所在 姓名杨肠 学号0 c 1 5 ( b 3 拙计算机软件与理论 学科 答辩答辩 上海交通大学徐汇校区新建楼2 0 琏指导教师口j 王假 册吁1 6 日期地点 论文题目 基于机器学习方法的生物序列分类研究 ， 投票表决结果：与5 5( 同意票数实到委员数应到委员数)答辩结论：q 值过 口未通过 评语和决议： 生物序列分类是当前生物信息学的重要研究领域，它的深入研究有助于提高人们对生物分子的序 列、结构和功能的认识。该论文基于机器学习方法，围绕特征提取和模式分类两个关键技术，针对生彩 序列分类中的蛋白质亚细胞定位、同源蛋白查找、分泌蛋白预测以及非编码r n a 预测等问题进行研究 选题具有重要的科学意义和实用价值。 论文的主要贡献有以下几点： 在蛋白质序列特征提取方面，借鉴中文分词技术的思想，提出一种新的特征提取方法，与传统的复 基酸多联体频率法相比，该方法所生成的特征向量具有维数低、准确性高的优点；将其应用到蛋白质m 细胞定位和同源蛋白查找，比较其他方法，取得了较好效果。 采用最小最大模块化支持向量机解决蛋白质定位问题中的样本不平衡和多点定1 1 f 7 ：问题，比传统的支 持向量机大大缩短了训练时间，且在总体准确率和类平均准确率指标上均有提高。同时，针对最小最人 模块化支持向量机中随机划分问题带来的不稳定性，提出一种基于生物领域知识的问题划分方法，比随 机划分的性能更稳定、准确率更高。 针对细菌i i i 型分泌系统分泌的效应蛋白序列相似度低、空间结构不稳定的特性，利州二级结构雨 溶剂可接触性等特征预测细菌i i i 型分泌系统的效应蛋白，取得了较高准确率；并将该方法应用到根瘤 函的基i 因组上，得到一批新的效应蛋白。 基于比较基因组方法，通过设计详细的筛选步骤，结合现有成熟计算方法b l a s t n 、c l u s t e r w 、r n a 2 等，对多种植物全基因组序列的摹因间隔区进行了预测，得到共计1 6 个家族、2 1 个新的非编码r n a ， 且均通过生物实验验证了其表达性。 论文结构合理、内容充实，图表规范，达到了博士学位论文的要求，体现出作者掌握了本学科坚实 的基础理论以及系统的专门知识、具备较强的科研能力和分析解决实际问题的能力。 答辩过程中讲述清晰，回答问题正确。答辩委员会经无记名投票，一致通过杨呖同学的博十学位论 文答辩，并建议授予工学博士学位。 沙7 年易月，占日 职务姓名职称单位 签名 主席李亦学研究员中科院上海生命科学研究院 ，粥 答 黝 辩 委员王晓峰教授上海海事大学 委 委员 赵立平教授上海交通大学 一 少j 张_ ；! 钍 a 委员卢宏涛 教授上海交通大学 酉 成 触 口 委员骆源教授上海交通大学 一 ，) ， 贝 签 名 委员 委员 秘书 任庆生副教授上海交通大学彳磁嘭一 厂。、 、 基于机器学习方法的生物序列分类研究 摘要 在过去的几十年间，机器学习方法在生物信息领域获得了强劲的发 展动力，成为解决许多生物学问题的重要方法。在生物信息学中，无论 是基因识别，还是d n a 序列上的功能位点和特征信号的识别，或者是蛋 白质序列特征分析，都需要用到机器学习和模式识别技术。本文的工作 围绕模式识别的两个关键问题，特征提取和模式分类，对生物序列( 包 括蛋白质序列和核酸序列) 进行深入的分析和分类，以解决蛋白质的亚 细胞定位，同源蛋白查找，细菌i i i 型分泌系统的分泌蛋白预测以及新的 非编码r n a 预测等问题。 本文的主要贡献在以下几个方面。 1 ) 借鉴中文自然语言处理中的分词技术，提出了一种新的蛋白质序 列特征提取方法。我们从蛋白质的氨基酸序列中挑选具有统计意义的子 序列构成词典，并将氨基酸序列切分为互不重叠的词，通过统计各个词 的出现频率获取蛋白质的特征。相比于传统的氨基酸多联体频率法，所 提方法所生成的特征向量具有维数低、准确性高的优点。我们将其应用 到蛋白质亚细胞定位和同源蛋白查找中，取得了良好的效果。 2 ) 针对细菌i i i 型分泌系统分泌的效应蛋白序列相似度低和空间结构 不稳定的特性，我们首次利用二级结构和溶剂可接触性信息以及氨基酸 组份信息预测未知的效应蛋白，在假单胞菌基因组上进行交叉验证，取 得了较高准确率，并对根瘤茵的四个不同菌株的基因组进行了预测，得 到一批新的效应蛋白。 3 ) 针对蛋白质定位问题的样本不平衡和多点定位问题，采用最小最 大模块化支持向量机解决这一多标号不平衡问题。该方法相比于传统的 支持向量机，在总体准确率和类平均准确率指标上均有提高；同时，该 方法也大大缩短了训练时间，可用于大规模的数据集。 4 ) 为最小最大模块化支持向量机提出一种新的基于生物领域知识 ( 物种分类和基因本体注释信息) 的任务分解方法，该方法与随机划分 和其他划分方法相比具有性能稳定，准确率高的优点。 5 ) 基于比较基因组学方法，抽取多种植物全基因组序列的基因间隔 区，并通过序列比对得到在多个植物基因间隔区中保守的序列片段，对 上海交通大学博士学位论文 这些片段进行预测，并经过一系列的筛选步骤，得到共计2 1 个新的非编 码r n a ，分为1 6 个家族。这些新家族均通过生物实验验证其表达性。 关键词：生物信息学，生物序列，特征提取，模式分类，最小最大模块 化网络，支持向量机，问题分解，蛋白质亚细胞定位，非编码r n a 一一 r e s e a r c ho nb i o l o g i c a ls e q u e n c ec l a s s i f i c a t i o nb a s e do n m a c h i n el e a r n i n gm e t h o d s a b s t r a c t o v e rt h ep a s tf e wd e c a d e s ，t h em a c h i n el e a r n i n gm e t h o d sh a v eo b t a i n e dg r e a tm o i l v a t i o no fd e v e l o p m e n ti nt h er e a l mo fb i o i n f o r m a t i c s ，a n db e c o m ea ni m p o r t a n tm e a n st o s o l v eb i o l o g i c a lp r o b l e m s i nb i o i n f o r m a t i c s ，g e n er e c o g n i t i o n ，f u n c t i o nc i t e s i g n a lr e c o g n i t i o no nd n a s e q u e n c e s ，a n dp r o t e i ns e q u e n c ef e a t u r ea n a l y s i s ，a l ln e e dm a c h i n el e a r n i n g a n dp a t t e mr e c o g n i t i o nt e c h n i q u e s i nt h i st h e s i s ，w ef o c u so nt w ok e yp r o b l e m si np a t t e r n r e c o g n i t i o n ，n a m e l yf e a t u r ee x t r a c t i o na n dp a t t e mc l a s s i f i c a t i o n , t oa n a l y z ea n dc l a s s i f yb i o l o g i c a ls e q u e n c e si n c l u d i n gp r o t e i na n dd n as e q u e n c e s ，f o rd e a l i n gw i t has e r i e so f b i o l o g i c a lp r o b l e m s ，i e ，p r o t e i ns u b c e l l u l a rl o c a l i z a t i o n ，p r o t e i nh o m o l o g ys e a r c h i n g ，p r e d i c t i o no f t h e p r o t e i n ss e c r e t e db yt y p ei i is e c r e t i o ns y s t e ma n dp r e d i c t i o no fn o v e ln o n - c o d i n gr n a s t h em a j o rc o n t r i b u t i o n so ft h et h e s i sa r e ： 1 ) i n s p i r e db yt h ew o r ds e g m e n t a t i o nt e c h n i q u e si nc h i n e s en a t u r a ll a n g u a g ep r o c e s s i n g ，w ep r o p o s e dan e wp r o t e i ns e q u e n c ef e a t u r ee x t r a c t i o nm e t h o d w es e l e c t e ds u b s e - q u e n c e sw i t hs t a t i s t i c a ls i g n i f i c a n c ef r o mt h ep r o t e i ns e q u e n c e s ，s e g m e n t e dt h ea m i n oa c i d s e q u e n c e si n t on o n - o v e r l a p p e dw o r d s ，a n de x t r a c t e dt h ef e a t u r e so fp r o t e i ns e q u e n c e sb y c o u n t i n gt h ef r e q u e n c yo fe a c hw o r d 。c o m p a r e dw i t ht r a d i t i o n a la m i n oa c i dk - m e rf r e - q u e n c ym e t h o d , t h ep r o p o s e dm e t h o dh a st h ea d v a n t a g e so fl o w e rd i m e n s i o n a l i t ya n dh i g h e r a c c u r a c y w ea p p l i e di tt op r o t e i ns u b c e l l u l a rl o c a l i z a t i o na n dp r o t e i nf a m i l yc l a s s i f i c a t i o n ， a n do b t a i n e dg o o dr e s u l t s 2 ) c o n s i d e r i n gt h el o ws e q u e n c es i m i l a r i t ya n du n s t a b l es t r u c t u r e so ft h ep r o t e i n ss e e r e t e df r o mt h et y p ei l ls e c r e t i o n s y s t e m s ，i e ，e f f e c t o r s ，w ef o r t h ef i r s tt i m eu t i l i z e dp r o t e i n s e c o n d a r ys t r u c t u r e ，s o l v e n ta c c e s s i b i l i t ya n da m i n oa c i dc o m p o s i t i o ni n f o r m a t i o nt op r e d i c t u n k n o w ne f f e c t o r s w ep e r f o r m e dc r o s sv a l i d a t i o no np s e u d o m o n a sg e n o m ea n do b t a i n e d h i 曲a c c u r a c y m o r e o v e r , w ep r e d i c t e da l lt h ee f f e c t o r so ff o u rs t r a i n so fr h i z o b i u m c o m b i n i n gw i t hp r o m o t e rp a t t e mm a t c h i n g ，w eo b t a i n e dan u m b e ro fn e wt y p eh is e c r e t i o n e f f e c t o r s 3 ) f o rt h ec l a s si m b a l a n c ea n dm u l t i l o c a l i z a t i o np r o b l e m si np r o t e i ns u b c e l l u l a rl o c a l i z a t i o n , w eu s e dm i n - m a xm o d u l a rs u p p o r tv e c t o rm a c h i n e st os o l v et h em u l t i - l a b e li m b a l a l i c ep r o b l e m c o m p a r e dw i t ht r a d i t i o n a ls u p p o r tv e c t o rm a c h i n e s ，t h em o d u l a rc l a s s i f i e r h i 上海交通大学博士学位论文 i m p r o v e db o t ht o t a la c c u r a c ya n dc l a s sa v e r a g ea c c u r a c y a tt h es a m et i m e ，t h i sm e t h o d s p e e d e du pt h et r a i n i n gt i m eg r e a t l y , w h i c hi ss u i t e df o rl a r g e s c a l ed a t as e t s 4 ) w ep r o p o s e dan e wt a s kd e c o m p o s i t i o nm e t h o db a s e do nb i o l o g i c a ld o m a i nk n o w l e d g e ，n a m e l yt a x o n o m ya n dg e n eo n t o l o g yi n f o r m a t i o n ，f o rt h em i n m a xm o d u l a rs u p p o r t v e c t o rm a c h i n e s t h en e w d e c o m p o s i t i o nm e t h o dh a sm o r es t a b l ep e r f o r m a n c ea n dh i g h e r a c c u r a c yt h a nr a n d o md e c o m p o s i t i o na n do t h e rd e c o m p o s i t i o nm e t h o d s 5 ) b a s e do nt h ec o m p a r a t i v eg e n o m i cm e t h o d , w ee x t r a c t e di n t e r g e n i cr e g i o n sf r o m m u l t i p l ep l a n tg e n o m es e q u e n c e s ，a n do b t a i n e dc o n s e r v e ds e q u e n c es e g m e n t st h r o u g hs e q u e n c ea l i g n m e n t s w ec o n d u c t e dp r e d i c t i o no nt h e s es e g m e n t s ，a n dc a r d e do u tas e r i e so f s c r e e n i n gs t e p s ，a n df i n a l l yo b t a i n e d2 1n e wn o n c o d i n gr n a s ，w h i c hc a nb eg r o u p e di n t o 16f a m i l i e s t h e s en e wn c r n a sh a v eb e e nv e r i f i e dt h r o u g hw e t - b e n c he x p e r i m e n t sf o rt h e i r a b i l i t yt oe x p r e s s k e yw o r d s ： b i o i n f o r m a t i c s ，b i o l o g i c a ls e q u e n c e ，f e a t u r ee x t r a c t i o n ，p a a e mc l a s s i - f i c a t i o n ，m i n - m a xm o d u l a rn e t w o r k ，s u p p o r tv e c t o rm a c h i n e s ，t a s kd e c o m p o s i t i o n ，p r o - t e i ns u b c e l l u l a rl o c a l i z a t i o n ，n o n c o d i n gr n a 一一 目录 摘要i a b s t r a c t ( 英文摘要) i 主要符号对照表v i i i 第一章绪论1 1 1 课题背景及意义1 1 2 机器学习算法3 1 2 1 神经网络3 1 2 2 支持向量机4 1 2 3 决策树7 1 2 4k 近邻法8 1 3 蛋白质序列特征提取和分类8 1 4 核酸序列分类1 3 1 5 论文安排1 4 第二章蛋白质序列特征提取1 5 2 1 基于序列的传统特征提取方法1 5 2 1 1 氨基酸组份方法1 5 2 1 2j i ：联体方法1 6 2 2 基于注释的特征提取方法1 9 2 2 1 基因本体( g e n e o n t o l o g y ) 1 9 2 2 2g o 特征提取方法2 0 2 2 3 模体特征提取方法2 0 2 3 基于中文分词技术的特征提取2 0 2 3 1 建立词汇表2 2 2 3 2 分词2 4 2 4 基于其他信息的特征提取2 5 2 5 蛋白质亚细胞定位预测实验2 8 2 5 1 基于分词特征的预测结果2 9 2 5 1 1 每种长度的词个数2 9 2 5 1 2 最大词长度2 9 2 5 2 与其他方法的比较3 3 2 6 蛋白质同源家族分类实验3 4 2 6 1s c o p 家族分类实验：3 5 2 6 2g p c r 蛋白质亚家族分类3 8 一v 一 上海交通大学博士学位论文 2 7 细菌i l l 型分泌系统效应蛋白预测 2 7 1 数据集 2 7 2 实验结果 2 8 本章小结 第三章基于m 3 s v m 的蛋白质亚细胞定位 3 1 研究现状 3 2 最小最大模块化网络 3 2 1 将多类问题分解为二类问题 3 2 2 进一步分解二类闯题 3 2 3 合并子问题 3 2 4 将二类问题还原为多类问题 3 2 5 多标号问题的分类 3 2 6 任务分解 3 3 实验结果与讨论 3 3 1 实验一 3 3 2 实验二 3 3 3 响应时间比较 3 4 本章小结 第四章基于领域知识的问题分解 4 1 问题分解的重要性 4 2 随机分解。 4 3 超平面分解 4 4p c a 超平面分解 4 5 基于均等聚类的问题分解 4 6 根据领域知识的问题分解 4 6 1 基于生物种属关系的分解策略 4 6 2 基于基因本体的样本划分 4 7 实验结果 4 7 1 基于物种信息分解的实验结果 4 7 2 几种分解策略的比较 4 7 3 基于g o 分解的实验结果 4 7 4 与其他方法的比较 4 8 本章小结 第五章非编码r n a 预测 5 1 非编码r n a 简介 5 2 实验数据来源 5 3 计算预测流程 5 3 1 生成保守区段 5 3 2r n a 预测工具 一一 矗 9 0 1 3 5 5 7 7 9 9 l l 3 4 4 8 l 3 4 4 6 7 8 9 l l 2 3 3 6 7 0 2 3 3 4 5 6 7 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 目录 5 4 性能评估8 8 5 4 1 查全率8 8 5 4 2 查准率8 8 5 5 实验结果8 9 5 5 1 预测拟南芥n c r n a 8 9 5 5 2 根据已知基因和n c r n a 筛选9 1 5 5 2 1 预测结果与t a i r 8 注释匹配9 l 5 5 2 2 预测结果与已知n c r n a 数据库匹配9 l 5 5 2 3 使用r f a m 分类可能的n c r n a 9 2 5 5 3 湿实验验证。9 2 5 5 4 与a p p 三元组结果的比较9 2 5 5 5 进一步的结果分析9 3 5 5 5 1 蛋白质编码能力检查9 4 5 5 。5 2 检查包含d 、r n a 的情况9 6 5 5 5 3 识别重复序列和转座予9 6 5 6 本章小结9 6 第六章总结与展望9 8 结束语9 8 参考文献1 0 1 致谢1 1 2 个人简历、在学期间的研究成栗及发表的论文1 1 3 一i 一 囊 m 3 s v m m 3 s v m k n n r b f p c a g o d n a r n a 主要符号对照表 最小最大模块化( m i n m a xm o d u l a r ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 最小最大模块化支持向量机( m i n m a xm o d u l a rs u p p o r tv e c t o rm a c h i n e ) k 最近邻f 算法) ( k n e a r e s tn e i g h b o r ) 径向基函数( r a d i a lb a s i sf u n c t i o n ) 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 基因本体( g e n eo n t o l o g y ) 脱氧核糖核酸( d e o x y r i b o n u c l e i ca c i d ) 核糖核酸( r i b o n u c l e i ca c i d ) 一i i 一 一 第一章绪论 生物信息学是生物学与计算机科学、数学、统计学等学科相互交叉而形成的一 门新兴学科，它采用数学和信息科学的理论、方法和技术去研究生物大分子，包括 它们的序列、结构和功能。近几十年来生物信息学发展十分迅猛，公共数据库中 的生物分子数据量以指数级增长，尤其是核酸序列数据库、蛋白质序列数据库、基 因组信息数据库等。生物序列( 包括核酸和蛋白质序列) 的数字化特性使得计算机 科学家可以用计算的方法来分析处理，生物序列分类就是将生物分子的不同性质看 做不同类别，根据其序列信息进行分类，是解决生物分子功能、结构等方面信息预 测的主要途径。而机器学习方法以其数据驱动的特性，对噪声的应对能力，以及在 大规模数据上的良好性能，成为解决生物信息学问题的重要手段和技术，尤其在生 物序列分类上有着广泛而深入的应用。 在本章中，我们总结了生物序列分类的研究现状，简单介绍了几种常用的机器 学习方法，以及全文涉及的几个生物学问题，包括蛋白质的亚细胞定位，同源蛋白 查找，致病细菌的分泌蛋白预测以及新的非编码r n a 预测。 1 1 课题背景及意义 2 0 世纪后半叶以来生命科学各领域所取得的巨大进展使生命科学在自然科学 中的位置起了革命性的变化。勿庸置疑，在2 l 世纪生命科学将继续蓬勃发展，而信 息科学则是推动其迅速发展的重要力量。由于人类基因组等计划的顺利实施，生物 分子数据量呈现爆炸性增长，现有生物信息数据库中的数据量迅速膨胀，数据库的 复杂程度也在不断增加，如核酸序列数据库、蛋白质序列数据库、大分子结构数据 库、基因组信息数据库等。生物信息学以计算机、网络为工具，采用数学和信息科 学的理论、方法和技术去研究生物大分子，其研究重点主要落实在核酸和蛋白质两 个方面，包括它们的序列、结构和功能。生物信息学的诞生是由生物学对大量数据 处理和分析的需求而引发的，其发展依赖于计算机科学技术和生物技术的发展，而 生物信息学的研究成果又促进了生物学特别是分子生物学的发展。 生命最重要的物质基础是核酸( d n a 与r n a ) 和蛋白质。d n a 分子中的核苷 酸碱基分别是腺嘌呤( a ) 、鸟嘌呤( g ) 、胸腺嘧啶( t ) 、胞嘧啶( c ) ，因此，我们可以 将d n a 分子看成是由字母表q 一 a ，g ，c ，t 】中的元素组成的字母序列。而一切物种 的蛋白质都是由2 0 种氨基酸构成的，所以蛋白质的一级结构可看成是由2 0 个字母组 成的字母序列。本文所涉及的生物序列即包括这两种序列，无论是核酸序列还是蛋 白质序列，都可看做是特殊的字符串。随着各种基因组测序项目的不断进展，生物 信息学研究的重点正逐步从积累数据转移到如何解释这些数据。 上海交通大学博士学位论文 在分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核酸或氨基酸序 列的相似，可能是结构的相似，也可能是功能的相似。一个普遍的规律是序列决定 结构，结构决定功能。人们常常通过相似的序列得到相似的结构或相似的功能，然 而也存在序列完全不同，但分子却具有相同空间结构的情况。 生物序列分析 1 是生物信息学的主要研究领域，其主要工作是从浩瀚的原始生 物序列数据中发掘和提取信息从而探索和揭示生命的奥秘。计算机科学应用于生 物领域的第一个高潮便出现在序列分析中。生物序列分析包罗万象，可以用于序列同 源性搜寻、多序列比对和构建进化树、蛋白质结构和功能预测、基因组序列分析和 基因发现、启动予( p r o m o t e r ) 识别、预测基因表达水平、进行序列聚类及观察类的 拓扑结构、预；溪 j r n a - - 级结构、识别d n a 和r n a 的其他功能位点和类别、蛋白质家 族分类等等方面。这对于理解生物信息的传递与调控机制有着举足轻重的影响。其 中涉及到如何建模、模型参数选择、信息提取和表达等等一系列困难而又复杂的问 题。 为了分析生物序列信息，特别是预测蛋白质和r n a 的功能与结构，人们已经创 造了多种行之有效的方法。序列比对是常用的序列分析方法，即通过在序列中搜索 一系列单个性状或性状模式来比较两条( 两两比对) 或更多序列( 多重比对) ，可 分为两种类型：全局比对和局部比对。前者贯穿整个序列长度，尽可能多地匹配氨 基酸，代表算法是n e e d l e m a n 和w u n s c h 的动态规划算法 2 】；后者则优先寻找最相似 的局部区域，以发现保守的序列模式，代表算法是s m i t h - w a t e r m a n 算法 3 。通过序 列比对我们可以鉴定出高度保守的区域。还有些算法不通过序列比对，直接寻找 序列的共有模式。对于蛋白质序列，这些模式可以定义为一个保守结构或者功能 域；对于d n a 序列，这些模式则可能定义为一个在启动子区域的调控蛋白结合位 点或者是r n a 分子中的处理信号。有许多机器学习和统计学方法应用于寻找共有模 式，如神经网络、隐马尔科夫模型以及期望值极大化、吉布斯采样等 4 _ 7 。 庞大的生物信息数据库对数据分析处理技术提出了许多颇具挑战性的问题，也 提供了广阔的机遇，这些都需要研究人员提出新的思想和方法。在这方面，传统的 计算机科学算法曾有用武之地，但面对许多最具重要意义的序列分析问题，它们越 来越显示出不足。一方面是由于生物体不断进化，导致生物系统内在的复杂性；另 一方面则由于对于很多生物现象，我们并没有一套完整理论去解释。而机器学习方 法正适合于数据量大、含有噪声模式并且缺乏统一理论的领域。机器学习方法的基 本思想是通过推理、模型匹配或样本学习，从数据中自动学习理论。因此，机器学 习方法是传统方法的重要发展。机器学习方法已经开始在生物信息学领域产生显著 的影响。随着“人类基因组计划”的顺利完成、多种模式动植物基因序列的测定以及 蛋白质工程技术的不断发展，核酸与蛋白质一级结构数据库包含了海量的生物信 一2 一 第一章绪论 息，而且许多具有相似特性的序列之间相似程度很低( 长度差异很大，公共部分不 多，序列存在很多变异) ，在这种情况下，模式识别方法往往更加有效。因此，本 文主要探讨基于机器学习的生物序列分类问题。 在1 3 和1 。4 两节中，我们将分别阐述本文涉及到的蛋白质序列和核酸序列分类的 若干应用。 1 2 机器学习算法 机器学习从本质上讲是一个多学科的领域，涵盖了人工智能、概率统计、计 算复杂性理论、控制论、信息论、神经生物学等学科中的概念，其目的是通过建 立适当的统计模型，从一个数据集中找出有用的信息或建立一定的规则。机器学 习的一大优点是由机器自动处理数据，使信息提取过程尽可能自动化地完成。在 这一节中，我们将介绍在机器学习方法应用中涉及到的几个主要算法，包括神经 网络( n e u r a ln e t w o r k , n n ) 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 、k 近邻 ( k n e a r e s tn e i g h b o r ，h 2 q n ) 和决策树( d e c i s i o nt r e e d t ) 。 1 2 - 1 神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) ，也称神经网络( n n ) ，它的提出 源于模拟大脑的信息处理和学习过程，是由一些相互连接的神经元组成的网络。 神经网络可以表示成为带权重的有向图或结构，含有有向环的网络称为反馈式 ( r e c u r r e n t ) 网络，不含有向环的称为前馈式( f e e d - f o r w a r d ) 网络。如果神经元被 分为几层，而且各层之间存在连接，该类网络为分层网络。 神经元节点通常可分为可见节点和隐藏节点。可见节点指直接与外界作用的神 经元节点，如输入、输出神经元节点，其他节点称为隐藏节点。含有可见节点和隐 节点的层分别称为可见层和隐藏层。可见层的设计取决于用于序列数据编码的输入 方式，以及通常代表结构与功能特征的输出方式。 通常一个神经元有不只一个输入，图1 1 显示了一个具有多个输入的神经元 8 ， 其输入矶( 1 i r ) 对应权值矩阵w 的元素w l ) 。该神经元有一个偏置, i ( 1 ir 值b ，它与所有输入的加权和累加，从而形成总输入佗，用矩阵形式可表示为： 佗= w p + b 其中单个神经元的权值矩阵w 只有一列元素。神经元的输出可以写成： a = f ( w p + b ) 其中，为传输函数( t r a n s f e rf u n c t i o n ) 。 一3 一 ( 1 2 ) 上海交通大学博士学位论文 输入多输入神经元 n 厂、 p l p 2 p 3 p r ! 一， a = a w p + b ) 图1 1多输入神经元节点 f i g 1 1m u l t i p l ei n p u tn e u r o n 一般同一层的所有节点具有相同的传输函数，总的输入量为前一层节点总输出 量的加权和。在分层前馈神经网络中，同一层中所有的神经元节点同时进行更新， 而各层逐次顺序更新。 有很多形式的传输函数被广泛使用，如硬极限函数、线性函数、对数一s 型函数 和径向基函数等等。使用者可根据待解决问题的需要设计选择网络层数和节点数， ，i 以及传输函数。 神经网络的最重要的特性是可以通过样本进行学习，并可证明，它能够以 任意精度逼近任意给定函数 9 ，1 0 】。它的学习算法通常采用反向传播算法( b a c k p r o p a g a t i o n ) ，它是最速下降算法的近似，其中性能指数是均方误差。由输出层回 馈到输入层，误差信号依照神经网络链接反向传播，依次更新权重。 1 2 2 支持向量机嘲 1 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m s ) 是v a p n i k 等人提出的一种机器学 习方法 1 1 】。其基本思想是在样本输入空间或特征空间，构造出一个最优超平面，使 得超平面到两类样本集之间的距离达到最大，从而取得最好的泛化能力。不同于神 经网络，支持向量机的解是全局最优的，而且不需要人工设计网络结构。 设给定问题的训练样本集为( z l ，可1 ) ，( z 2 ，耽) ，( 觑，饥) ，其中虢r n ，阢 - 1 - + - 1 ，i = 1 ，2 。假设该训练集的正反两类样本可以被一个超平面划分，即存 在一个超平面w x + b = 0 ，使得w x t + b 0 时输出为正类，否则为负类。对于一个问一 题，可能存在很多个满足条件的超平面，但有一个称为最优超平面。所谓最优超平 面是指距离超平面最近的点跟超平面的距离达到最大。如图1 2 所示，h + 就是最优超 一4 一 第一章绪论 + + + + 图1 2正确无误地划分两类问题的超平面及其最优超平面h + 平面。支持向量机就是要寻找这个最优超平面，而那些跟最优超平面距离最近的点 就是支持向量。 容易得到支持向量与最优超平面的距离为：丽1 ，而训练集两类样本的间隔距离 则为丽2 。因此，构造最优超平面的问题就等价于在公式1 3 约束下最小化式1 4 ， y i ( “g x i + b ) 1 对i = 1 ，1 ，、 1 t 妒( u ) 2 互u u 这是一个二次规划问题，我们构造其拉格朗日函数： ( 1 3 ) ( 1 4 ) m ，6 垆互1 u 一妻州坎( o ) t x i _ | - b ) - 1 】 ( 1 5 ) 其中啦是拉格朗日乘数。二次规划的最优解就在这个拉格朗日函数的鞍点。在 鞍点处，