【摘要】 该发明公开了一种基于关联分析与关联分类的蛋白质二级结构预测技术，以双库协同机制为基础，将KDD*过程模型引入蛋白质二级结构预测问题中，KAAPRO方法以数据挖掘(知识发现)为主体，采用基于KDD*过程模型Maradbcm算法以及关联规则分类D-CBA方法。KAAPRO方法所取得关联规则在一定程度上揭示了氨基酸物化属性对蛋白质二级结构的影响关系，从而提高了预测的精度。其中Maradbcm算法挖掘意外规则的特性对纯度较高的α蛋白质库与β蛋白质库进行关联规则的挖掘，由此获得的挖掘结果是精化的规则。D-CBA关联分类方法使用可信度与支持度的测度作为一个复合型度量来进行蛋白质关联分类。在保证预测精度的同时，为生物学家对二级结构进一步分析提供了依据。 【专利类型】发明授权 【申请人】北京科技大学 【申请人类型】学校 【申请人地址】100083 北京市海淀区学院路30号 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810116675.7 【申请日】2008-07-15 【申请年份】2008 【公开公告号】CN101344902B 【公开公告日】2010-07-28 【公开公告年份】2010 【授权公告号】CN101344902B 【授权公告日】2010-07-28 【授权公告年份】2010.0 【IPC分类号】G06F19/00; G06F17/30; G06F19/24 【发明人】杨炳儒 【主权项内容】1.一种基于关联分析与关联分类的蛋白质二级结构预测方法，包括：基于KDD*过程模型关联分析方法、基于复杂度量的D-CBA关联分类方法； 基于KDD*过程模型的关联分析方法，具体方式为对RS126数据集分割窗口化，收集中间残基结构为C的记录组合而成，在此基础上，在KDD*过程模型的作用下，获得精化的关联规则库； 基于复杂度量的D-CBA关联分类方法主要特征包括两方面：其一使用可信度与支持度的测度作为一个复合型度量；其二根据蛋白质生物数据的特性，使用内容分别相对偏向α、β的蛋白质库；此两个数据库是以CATH分类为基础，以同源性小于30％为条件，选择α型、β型的蛋白质而构成；利用基于KDD*模型的Maradbcm算法对纯度较高的α蛋白质库与β蛋白质库进行关联规则的挖掘； 复杂度量的D-CBA关联分类方法与通过基于KDD*过程模型的关联分析方法得到精化的关联规则库：在合成金字塔复合结构中，包括综合分析层、核心判定层、辅助判定层和结果优化层，底层的综合分析层包括同源性分析与SVM多分类，核心判定层起着精化判定的重要作用，为结果优化层算法判断辅助判定层D-CBA算法无法判断的情况与为综合分析层同源分析与SVM的投票提供依据；在偏α、β型蛋白质二级结构预测中，核心判定层主要的作用是对同源分析与SVM多分类的结果的不同的部分进行分类，主要的工具是KDD*模型与基于支持度与可信度的复杂度量的D-CBA算法，通过KDD*系统生成的α、β的规则，进行约简后得到精炼的α、β关联规则库，使用D-CBA算法，经过对相对偏向α、β的蛋白质库的反复实验得到适用于α、β关联规则库的支持度与可信度的比例的系数； 在D-CBA算法的使用过程中，按照可信度的累加来作为α、β的判定标准，使用可信度与支持度的距离来作为一个复合型度量； 上述的基于KDD*过程模型关联分析方法主要包括KDD*过程模型、维护型协调器、启发型协调器、中断型协调器、基于KDD*过程模型的Maradbcm算法； KDD*过程模型包括：数据预处理、聚焦、定向挖掘、求取假设规则、实时维护、评价； 1)数据预处理：对真实数据库中的数据进行再加工，形成挖掘数据库，并与所述的真实数据库在基于属性建库的构造下建立对应关系； 2)聚焦：由通过人机交互输入的内容来指导数据挖掘的方向； 3)定向挖掘：启发型协调器知识库中“知识结点”的不关联态，计算有向超图的可达矩阵来实现发现“知识短缺”，产生“创见意象”，从而启发与激活真实数据库中相应的“数据子类”，以产生“定向挖掘进程”，进而用规则强度阈值进行剪枝并由计算机自动完成聚焦； 4)求取假设规则：通过选定的知识挖掘法，从挖掘数据库中提取用户所需要的知识，并用特定的模式表达所提取的知识，主要通过可信度阈值来实现； 5)实时维护：当从真实数据库的大量数据中经聚焦而生成规则后，中断型协调器则用SQL语言或计算有向超图的可达矩阵，去知识库中对应位置有无此生成规则的重复、冗余、矛盾、从属、循环；若有，则取消该生成规则或相应处理后返回KDD的“始端”；若无，则继续知识评价的KDD进程； 6)评价：对步骤5)处理后并被选取的规则进行价值评定，将被接受的规则存入衍生知识库； 维护型协调器是当从真实数据库的大量数据中经聚焦而生成感兴趣的与具有一定可信度的规则后，使KDD进程产生中断，而去定向知识库中对应位置有无此生成规则的重复、冗余与矛盾，若有重复与冗余，则取消该生成规则或冗余规则而返回KDD的始端；若无，则继续KDD进程；对于矛盾的处理，采用约束规则的条件与根据约束规则的可信度或关联强度来裁决的方法；其主要功能有：1)重复的处理：重复是指两条知识表达方式、内容完全一致，为此对重复的知识进行处理，当新知识的可信度大于旧知识的可信度时，则以新知识的可信度代替旧知识的可信度，其它的不变；否则扔掉新知识；2)矛盾的处理：矛盾是指由相同的前提推出相反的结论，或由相反的前提推出相同的结论；3)冗余的处理：冗余是指有些新产生的知识可以由知识库中固有的知识表达出来； 启发型协调器是在以属性为基础的知识库建库原则下，通过知识库中“知识结点”的不关联态，以发现“知识短缺”，产生“创见意象”，从而启发与激活真实数据库中相应的“数据子类”，以产生“定向挖掘进程”，为了防止“无序定向挖掘”现象产生，必须规定优先级，以定向挖掘较可信与关联性强的待定规则； 上述的维护型协调器算法实现步骤为： 步骤1、对挖掘出的知识逐一判断知识的可信度是否大于给定的阈值；若是，则进入步骤2；否则进入下一条知识的判断； 步骤2、对由步骤1得到的知识判断知识是否重复；若是，则转入步骤1；否则转入步骤3； 步骤3、对由步骤2得到的知识判断知识是否冗余；若是，则转入步骤1；否则转入步骤4； 步骤4、对由步骤3得到的知识判断知识是否矛盾；若是，则转入步骤1；否则将知识存入知识库；若所有的知识处理完，则算法终止；否则转入步骤1； 上述的启发型协调算法实现步骤为： 步骤1、自关联强度大于某一阈值的语言变量值，形成结点集S； 步骤2、对结点集S中的结点进行组合，形成元组集合； 步骤3、现有知识库，从元组中除去已在知识库中存在的元组； 步骤4、对剩余元组按关联强度排序，给出定向的优先序； 步骤5、按优先级排序，并逐一扫描各元组，聚集到数据库相应入口，进行定向挖掘；并进行KDD进程； 上述的基于KDD*过程模型的Maradbcm算法的实现步骤为： 设规则强度阈值为Min_Intensity，支持度阈值为Min_Sup，可信度阈值为Min_Con； 步骤1、数据预处理：这里主要是用户选择真实数据库，对于多值属性进行离散化； 步骤2、划分数据子库，依据数据子库建立数据子类结构，形成挖掘数据库；划分知识子库，依据知识子库建立知识结点，调用calculate_reach_matrix过程产生可达矩阵，从而形成挖掘知识库； 步骤3、调用Heuristic_Coordinator(K2)过程生成K2，其中Heuristic_Coordinator(K2)表示产生所有长度为2的短缺知识，K2为长度为2的短缺知识； 步骤4、将值m赋值2； 步骤5、对Km产生假设规则：对Km中的短缺知识ri：e1∧e2∧...∧ep→eq进行定向挖 掘，其中ri∈Km，ri：e1∧e2∧...∧ep→eq表示短缺知识，对数据表table1，table2，...，tablep，tableq进行挖掘，计算Con(ri)和Intensity(ri)，其中Intensity(ri)表示第i条短缺知识的规则强度，Con(ri)表示第i条短缺知识的规则可信度；如果Con(ri)大于Min_Con并且Intensity(ri)大于Min_Intensity(ri)，则转步骤6；否则，将Km-ri赋值给Km，转步骤8； 步骤6、对规则ri应用维护型协调器进行处理；若维护型协调器返回的结果为0，则取消该生成规则或相应处理，转步骤8；若不为0，则转步骤7； 步骤7、对规则ri进行评价；若评价通过则入库；若m等于2，调用过程Calculate_matrix1(s，t)(ri：(s→t))来调整超图的可达矩阵；否则调用过程Calculate_matrix2((f1，f2，...，fs)，t)(ri：(f1∧f2∧...∧fs→t))来调整超图的可达矩阵；若评价没有通过，则删除该规则； 步骤8、Km是否结束；若结束，当m等于2时调用X1(P)，否则调用X2(P)；调用过程Heuristic_Coordinator(Km，Km+1)来产生Km+1，其中Heuristic_Coordinator(Km，Km+1)表示由长度为m的短缺知识产生所有长度为m+1的短缺知识，其中m＞2，转步骤9；若没结束，则转步骤5进行下一条规则的处理； 步骤9、将m值加1，若Km为空集或者m大于M，M为预先给定的最大长度，转步骤10；否则，转步骤5； 步骤10、显示新产生的规则； 步骤11、结束； 过程calculate_reach_matrix的运行步骤如下： 步骤1、知识库中所有的知识素结点的ID号，1，2，...n，组成一个矩阵Pn×n，用一个二维数组来表示Pn×n，其元素均为0，P(i，j)＝0，其中i，j＝1，2，...，n； 步骤2、e的值设定为1； 步骤3、读取知识库中第e条长度为2的规则re：pi→pj； 步骤4、矩阵P(H)的元素P(i，i)＝1； 步骤5、调用过程Calculate_matrix1(s，t)； 步骤6、知识库中长度为2的规则是否读完？若没读完，则e的值加1，转步骤3；否则转步骤7； 步骤7、将e的值赋为1； 步骤8、读取知识库中的第e条长度大于2的规则re：pf1∧pf2∧...pfj→pi； 步骤9、调用过程Calculate_matrix2((f1，f2，...，fs)，t)； 步骤10、知识库中长度大于2的规则是否读完？若没读完，则e的值加1，转步骤8；否则结束； n为可达矩阵的列数， 过程X1(P)如下： 步骤1、外循环：i从0读到n； 步骤2、内循环：j从0读到n， 如果P(i，j)等于1，那么Km＝Km∪{i→j}； 过程X2(P)，形成带有结点的规则如下： 步骤1、外循环：i从n+1读到T，T为可达矩阵的行数； 步骤2、内循环：j从0读到n， 如果P(i，j)等于1，那么Km＝Km∪{i→j}； 过程Calculate_matrix1(j，i)的运行步骤如下所示： 步骤1、循环：k从1读到n， 执行P(j，k)：＝P(j，k)∨P(i，k)； 步骤2、循环：m从1读到n，， 如果P(m，j)等于1，那么做下面循环 循环：k从1读到n；执行P(m，k)：＝P(m，k)∨P(j，k)； 过程Calculate_matrix2((f1，f2，...，fj)，i)，此处j＞1，其过程的运行步骤如下： 步骤1、若虚结点pf1∧pf2∧...pfj不存在，则可达矩阵的后面加一行表示该结点； 步骤2、P(pf1∧pf2∧...pfj，i)＝1； 步骤3、循环：s从1读到n； 执行P(pf1∧pf2∧...pfj，s)：＝P(pf1∧pf2∧...pfj，s)∨P(i，s)； 过程Procedure Heuristic_Coordinator(K2)，该程序模块用以产生所有长度为2的短缺知识，其运行步骤如下所示： 步骤1、把可达矩阵从数据表ReachMatrix中读出，把support(pi)大于min_sup的知识素结点与全部知识合结点存入数组P中；support(pi)为pi的支持度，min_sup表示最小支持度； 步骤2、K2＝φ； 步骤3、 外循环：i从0读到n， 内循环：j从0读到n， 如果P(i，j)＝0且attr(pi)不等于attr(pj)且support(pipj)大于min_sup，则执行K2＝K2∪{i→j})；其中attr(pi)为知识素结点pi所对应的属性，相同属性的不同程度词不能出现在同一规则中，对i，j对应的数据表tablei，tablej进行挖掘计算support(ri)，support(ri)为ri的支持度； 过程Procedure Heuristic_Coordinator(Kx-1，Kx)，该程序模块用以由长度为x-1的短缺知识产生所有长度为x的短缺知识，其中x＞2，其运行步骤如下所示： 步骤1、Kx＝Φ，Kx为长度为x的短缺知识； 步骤2、对于Kx-1中任意两规则fi1∧fi2∧...∧fix-1→j和gi1∧gi2∧...∧gix-1→i，若fi1＝gi1，...，fix-1＝gix-1且j≠i，则Kx＝Kx∪{fi1∧fi2∧...∧fix-1∧i→j，fi1∧fi2∧...∧fix-1∧j→i}； 步骤3、对所有ri∈Kx， 步骤4、若support(ri)小于等于min_sup，则对ri对应的数据表table1，table2，...，tablep，tableq进行挖掘，计算support(ri)； 步骤5、Kx＝Kx-ri； 上述的基于复杂度量的D-CBA关联分类实现步骤为： 步骤1、基于Maradbcm算法的挖掘结果，形成α、β的精化关联规则库；其中每条规则 均带有可信度和支持度两个属性； 步骤2、对于关联规则库中每条规则进行复杂度量； 步骤3、计算每条规则的评价函数，并由此得出规则的SCORE；其中评价函数为： 其中wconf与wsup分别是可信度与支持度的系数，ScoreD-CBAα/β为每条规则的评价函数，confidencei为第i条规则的可信度，sup porti为第i条规则的支持度； 步骤4、按照复杂度量SCORE对关联规则库中的规则进行从大到小排序； 步骤5、按照排序后的关联规则库进行α、β分类； 步骤6、在待分类的蛋白质数据库中，找到符合优先级最高的规则的数据集，也就是符合关联规则库中复杂度量最高的规则的条件； 步骤7、用优先级最高规则的类别结果来标记步骤6中所有满足规则条件的数据集； 步骤8、将步骤7中满足规则条件的数据库从待分类蛋白质数据库中移除； 步骤9、重复步骤6；直到关联规则库为空或者待分类蛋白质数据库为空； 步骤10、结束。。微信 【当前权利人】北京科技大学 【当前专利权人地址】北京市海淀区学院路30号 【统一社会信用代码】121000004000022245 【家族被引证次数】9
