结构关系挖掘及其在生物信息中的应用.pdf
《结构关系挖掘及其在生物信息中的应用.pdf》由会员分享,可在线阅读,更多相关《结构关系挖掘及其在生物信息中的应用.pdf(6页珍藏版)》请在咨信网上搜索。
1、2023年/第12期 物联网技术智能处理与应用Intelligent Processing and Application1150 引 言结构关系挖掘是数据挖掘领域一个全新的分支,是基于序列模式挖掘提出的一种寻找序列模式之间内在结构关系的挖掘方法。该方法将序列模式之间的关系进一步细分,整合成一种由并发、互斥、重复及串行关系组成的复合关系1-3。随着人类基因组计划的启动和高通量测序技术的快速发展,生物医学数据呈现指数增长趋势,面对海量的生物数据,生物信息学的重要性日益凸显4。生物信息学的研究内容主要包括发展新的数理信息技术以用于开发生物数据的算法和运用数据挖掘等计算机技术以用于分析解释生物基因信
2、息。如今,应用和开发数据挖掘技术来探索生物系统规律是生物信息学领域最受关注的方向之一,其中包括基因序列分析、蛋白质功能预测、生物进化分析、表达图谱分析等5-6。在生物信息领域,结构关系挖掘方法也有重要应用。王翠青等人提出使用支持向量作为提取蛋白质序列中新模式的算法ConSP7并进行了并发挖掘。Jing Lu 等人使用真实蛋白质数据集的实验突显了 ConSP 方法在蛋白质这种数据中的适用性8。现有的结构关系挖掘方法关注的是序列模式间的结构关系,忽略了那些并不是很频繁但却可能有意义的序列,而且在挖掘过程中,主要分析的是序列模式之间而非序列内部的关系,这在面向生物信息挖掘时可能会导致分析得到的结果过
3、于冗余,实际意义不大。因此,本文对现有的结构关系挖掘知识体系做了进一步改进,在原有结构关系挖掘的基础上,改进了并发度、互斥度以及并发关系和互斥关系的概念,基于此提出了面向生物基因信息的结构关系挖掘算法框架。改进后的结构关系挖掘方法将序列之间的结构关系进一步细化到项集之间,并且关注了那些并不频繁但可能存在意义的序列。这样的改动使得在面向生物基因信息挖掘时能够得到更加科学客观的结果,从而确保在研究生物结构、分析生物进化变异等问题时能够快速准确地挖掘到有效的知识。1 相关问题描述1.1 有关序列模式和结构关系模式的知识I=i1,i2,.,im 是项目的集合,项集是 I 的非空子集,记为(x1,x2,
4、.,xk),其中 xj I,(1 j k m)。序列 S 是项集的有序集合,记为 s1,s2,.,sn,其中每个元素 si是一个项集。在事务数据库中,包含 S 的序列数与事务数据库中的序列总数之比称为序列 S 的支持度,记为 sup(S)。用户指定的最小支持度记为 minsup。当序列 S 的支持度大于等于用户指定的最小支持度,即 sup(S)minsup 时,则称序列 S 为频繁序列或序列模式9。事务数据库中所有的序列模式构成该数据库的序列模式集,记为 SPDB。对于序列S=I1I2.In 和序列 S=I1I2.In,mn,如果存在 m 个正整数 1 j1 j2.jm n,使得 Ij1Ij1
5、,Ij2Ij2,.,IjmIjm,则称序列 S 包含于序列 S,记为 SS,也称 S 为 S的子序列或 S为 S 的超序列10。结构关系模式挖掘是一种基于序列模式挖掘所提出的挖掘任务,旨在寻找隐藏在序列模式间的结构关系,如并发关结构关系挖掘及其在生物信息中的应用陈章昭1,2,陈未如1,2,张 雪1,2,高胜召1,2,韩 静1,2(1.沈阳化工大学 计算机科学与技术学院,辽宁 沈阳 110142;2.辽宁省化工过程工业智能化技术重点实验室,辽宁 沈阳 110142)摘 要:针对现有结构关系挖掘方法在挖掘时主要关注的是序列之间而没有分析序列内部的关系且忽略了那些非频繁但可能有意义的序列等问题,对现
6、有结构关系挖掘体系做了进一步改进,并基于改进后的并发、互斥、关联等关系提出了面向生物基因信息的并发关系挖掘算法 conApriori 和 conPrefix,以及互斥关系挖掘算法 excApriori。实验选取新冠病毒序列作为数据集,运用结构关系挖掘算法进行挖掘。实验结果表明,在不同的并发度和互斥度下,病毒序列间均存在并发、互斥等结构关系,结合现有的新冠病毒相关文献进行分析,病毒的部分并发突变可能会影响 SARS-CoV-2 的复制、感染性和抗原性,通过并发关系构建新冠病毒序列的系统发育关系可适用于新冠病毒的进化传播等研究,也进一步验证了挖掘结果的意义。关键词:结构关系;生物信息结构关系;新冠
7、病毒;基因序列;conApriori;conPrefix中图分类号:TP301 文献标识码:A 文章编号:2095-1302(2023)12-0115-06DOI:10.16667/j.issn.2095-1302.2023.12.031收稿日期:2023-01-13 修回日期:2023-03-01物联网技术 2023年/第12期 智能处理与应用Intelligent Processing and Application116系模式、互斥关系模式以及重复关系模式等1-3。现有结构关系模式挖掘的研究给出了并发度、互斥度、并发序列模式以及互斥序列模式等定义,并在此基础上提出了几种结构关系模式挖掘算
8、法。1.2 结构关系的相关概念基因项:基因项 ij=由两部分组成,其中 base为生物碱基 A,G,C,T 或蛋白质 G,A,V,L,I,F,W,Y,D,N,E,K,Q,M,S,T,C,P,H,R,loc 为该碱基或蛋白质在所对应序列的绝对位置。基因序列:由若干个基因项构成的集合称为基因序列,记为 i1,i2,.,in,其中每个元素 ij为一个基因项。如序列 S:,.,.,是由 29 562 个基因项构成的新冠病毒基因序列。并发度:对于序列 A=1,2,.,n,序列数据库 SDB中包含 A 的序列个数与包含 A 中任意项集的序列个数之比,称为序列 A 的并发度,记作 con(1,2,.,n),
9、或 con(A)。conSDBSDB(,)|,|(),121 2=niiS AS SSS Si,|n(1)并发关系:对于序列 A=1,2,.,n,给定客户指定的最小并发度 mincon,当 con(A)mincon 时,称 A 存在并发关系,表示为 A=1+2+.+n。1,2,.,n构成一组并发集。特别的,若 A 为基因序列且并发集中包含 n 个基因项,则称该并发集为 n-基因并发集。表 1 为包含了 4 条新冠序列的基因序列数据库 GSDB。表 1 基因序列数据库 GSDB编 号新冠病毒基因序列1,.,.,2,.,.,3,.,.,4,.,.,若给定最小并发度 mincon=70%,根据并发度
10、的定义可以得出序列 S=,的并发度 con(,)=3/4 mincon,则称序列 S 存在并发关系。表示为 S=+。,构成一组 3-基因并发集。并发关系具有反单调性:对于给定的序列数据库 GSDB,如果序列 A=1,2,.,n 存在并发关系 1+2+.+n,则 A的任意一个子序列也存在并发关系。证 明:假 设 序 列 A=1,2,.,n 且 存 在 并 发 关 系1+2+.+n,即 con(1,2,.,n)mincon,A 为序列 A 的一个 n-1 子序列。在序列库 SDB 中,包含 A 的序列肯定也包含 A,即 con(A)的分子要大于等于 con(A)的分子;由于序列 A 较 A 相比少
11、了一个元素,因此,con(A)的分母要小于等于 con(A)的分母。综上可得,con(A)con(A)mincon,即序列 A 的任意一个 n-1 序列也存在并发关系。以此类推,序列 A 的任意一个子序列都存在并发关系。完 全 并 发 集:对 于 并 发 关 系 C1=1+2+.+m 和C2=1+2+.+n,mn。若对 i(1 I m)都存在 ij(1 j n),则称并发关系 C2 包含并发关系 C1。若基因序列 S 存在并发关系且不被任意一个并发关系所包含,则称并发关系 S 为完全并发关系,该并发关系的所有基因项构成一组完全并发集。互斥度:对于序列 A=1,2,.,n,序列数据库 SDB中包
12、含且仅包含 A 中一个项集的序列个数与包含 A 中任意项集的序列个数之比称为序列 A 的互斥度,记作 xcl(1,2,.,n)或 xcl(A)。xcl(,)|(!),SDB,|()121 2=niiiSS SinS iS Sin=,SDB,|1 2(2)互斥关系:对于序列 A=1,2,.,n,给定客户指定的最小并发度 minxcl,当 xcl(A)minxcl 时,称 A 存在互斥关系,表示为A=12.n。1,2,.,n构成一组互斥集。特别的,若 A 为基因序列且互斥集中包含 n 个基因项,则称该互斥集为 n-基因互斥集。对于给出的 GSDB,若给定最小互斥度 minxcl=60%,根 据 互
13、 斥 度 的 定 义 可 以 得 出 基 因 序 列 S=,的 互 斥 度 为:xcl(,)=2/3 minxcl,称序列 S 存在互斥关系,表示为 S=。根据互斥度与并发度关系,以及并发关系的反单调性质可知,任何一个存在互斥关系的序列 A 的超序列(包含该 A的序列)很容易满足互斥关系,满足这一条件的互斥关系称为平凡互斥关系,这样的互斥关系不是我们关心的,只有那些任意子序列间都存在互斥关系的序列才有意义。非凡互斥关系:序列A=1,2,.,n存在非凡互斥关系,当且仅当 A 及其所有子序列都满足互斥关系。显然,非凡互斥关系满足反单调性。关联度:同时包含序列 A 和 B 的序列占包含序列 A 的序
14、列的比例,称为序列A关联B的关联度,记作association(A,B)。association(,)=A BS AS BS SS AS S|,GSDB|,GSDB|(3)关联关系:对于序列 A 与 B,当 A 在某一序列中出现时2023年/第12期 物联网技术智能处理与应用Intelligent Processing and Application117B 也有很大概率出现,即 A 与 B 的关联度 ass(A,B)minass(minass 为客户指定的最小关联度),则称序列 A 与 B 存在关联关系,表示为 A B。对于给出的 GSDB,若给定最小关联度 minass=90%,根据关联度
15、的定义可以得出基因序列 A=,与 B=,的关联度为:association(A,B)=1.0 minass,称 存 在 关 联 关 系,。2 结构关系挖掘具体过程描述获取数据集:数据集一般是通过访问资料库、网页抓取和问卷调查手动收集等方式获得。特别的,对于生物基因数据而言,可以从生物基因数据库下载进行研究,如 NCBI(https:/www.ncbi.nlm.nih.gov/)为美国国家生物技术信息中心,该数据库包含人类基因组、病毒、微生物和新冠病毒等生物基因信息;GISAID(https:/gb.org/gisaid/)是全球最大的流感及新型冠状病毒数据平台,该数据库不仅具有最完整的新冠病毒
16、基因组序列数据以及相关临床和流行病学数据,更汇聚了全球诸多科研团队对 COVID-19 的研究成果。预处理:数据预处理是为了提高数据的质量,保证数据的准确性、完整性和一致性。对于生物基因序列而言,从基因数据库下载的基因序列可能存在基因缺失或未知碱基数过多的情况,所以需要将下载的序列进行预处理,去除重复和低质量的序列。其次,虽然同类生物基因序列相似度很高,但序列长度会存在略微偏差,在预处理阶段还需要进行序列对齐操作。获取变异基因序列组:生物进化的实质是遗传物质的变异。在面向生物信息的研究过程中,由于生物序列和事务序列的特征存在很大差异,如生物序列是由有限个体(碱基或蛋白质)组成的超长序列,且同类
17、生物基因序列的相似性很高11,因此可以对基因序列的变异点进行针对性研究,这不仅可以很大程度提高挖掘效率,更使得分析生物变异进化过程更加科学、客观。已有研究表明,病毒基因组间的共突变是研究病毒进化的重要标志。例如,Deng Lizong 等人利用氨基酸序列的共突变网络来预测埃博拉病毒的致命性12。Olabode E.Omotoso 等人分析发现,新冠病毒序列 S蛋白 D614G 与其他复发性蛋白共突变对病毒 ACE-2 宿主进入产生了影响13。Qin Luyao 等人根据 SARS-CoV-2 基因组发现了一些共突变模块来推测病毒的进化传播过程14。经过预处理后的基因序列长度一致,我们首先选取一
18、条序列作为参考序列,然后将基因组中的序列和选取的参考序列进行序列比对,去除序列中具有一致核苷酸的保守位点,剩余部分则构成了变异基因序列。所有变异基因序列构成变异序列组vGSDB。挖掘序列间的结构关系:通过结构关系挖掘算法挖掘序列间的结构关系。本文给出了面向生物基因信息的结构关系挖掘算法。结果可视化表达:由挖掘序列间的结构关系步骤可以得到 SDB 结构关系,根据这些结构关系通过相关可视化方法可进一步分析序列库中的信息。如本文根据挖掘得到的新冠序列结构关系生成了 GSDB 系统发育框架,从而更好捕获生物基因的进化变异情况。3 结构关系挖掘算法由于实验对象选取的是新冠病毒 Sars-Cov-2 序列
19、,因此本文在 Apriori、Prefixspan 等序列模式挖掘算法的基础上,结合结构关系定义给出了适用于生物信息领域的挖掘算法。3.1 基于 Apriori 的并发关系挖掘算法 conApriori输入:基因序列数据库 GSDB,最小并发度 mincon输出:所有的并发集 allConcurrentItemSets算法:(1)获取 GSDB 中所有的基因项 T,生成初始候选并发集 Lk=TT(k 为 2);(2)令 Ck=null;allConcurrentItemSets=null;(3)dofor each s of Lkif(con(s)mincon)将 s 存入 k-并发集 Ck
20、中;将 Ck 存入 allConcurrentItemSets;Lk+1=CkCk;for each c of Lk+1if(c 存在 k-子序列不被 Ck 所包含)将 c 从 Lk+1 中删除;while(Lk+1 is not null);3.2 基于 PrefixSpan 的并发关系挖掘算法 conPrefix输入:基因序列数据库 GSDB,最小并发度 mincon输出:所有的并发集 allConcurrentItemSets算法:(1)获取 GSDB 中所有的基因项 T;(2)令 pre=null,preDB=null,prefDBItem=null;(3)for each s of
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 结构 关系 挖掘 及其 生物 信息 中的 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。