一种面向大规模序列数据的交互特征并行挖掘算法
发布时间：2021-09-04 02:54
序列是一种重要的数据类型,在诸多应用领域广泛存在.基于序列的特征选择具有广阔的现实应用场景.交互特征是指一组整体具有显著强于单独个体与目标相关性的特征集合.从大规模序列中挖掘交互特征面临着位点的"组合爆炸"问题,计算挑战性极大.针对该问题,以生物领域高通量测序数据为背景,提出了一种新的基于并行处理和演化计算的高阶交互特征挖掘算法.位点数是制约交互作用挖掘效率的根本因素.摈弃了现有方法基于序列分块的并行策略,采用基于位点分块的并行思想,具有天然的效率优势.进一步,提出了极大等位公共子序列（maximal allelic common subsequence, MACS）的概念并设计了基于MACS的特征区域划分策略.该策略能将交互特征的查找范围缩小至许多"碎片"空间,并保证不同"碎片"间不存在交互特征,避免计算耦合引起的高额通信代价.利用基于置换搜索的并行蚁群算法,执行交互特征选择.大量真实数据集和合成数据集上的实验结果,证实提出的PACOIFS算法在有效性和效率上优于同类其他算法.
【文章来源】：计算机研究与发展. 2019,56(05)北大核心EICSCD
【文章页数】：15 页
【部分图文】：
图１极大等位公共子序列的示例图Ｆｉｇ．１Ａｎｅｘａｍｐｌｅｏｆｍａｘｉｍａｌａｌｌｅｌｉｃｃｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅ
ｍ，１≤ｊ≤ｔ，发现：所有满足定义３，与特定类标签ｃｒ∈Ｃ存在显著统计关联的ｋ阶交互特征并且满足ＦＷＥＲ≤α．３ＰＡＣＯＩＦＳ框架第２．１节所述，大规模生物序列中的高阶交互特征挖掘面临着密集计算问题．本节将提出一种新的基于并行处理和演化计算的解决框架（ＰＡＣＯＩＦＳ），并对构成框架的各主要步骤加以详细介绍．３．１整体思想图２给出了ＰＡＣＯＩＦＳ框架的总体示意图：Ｆｉｇ．２ＡｎｉｌｌｕｓｔｒａｔｉｏｎｏｆＰＡＣＯＩＦＳ图２ＰＡＣＯＩＦＳ框架示意图框架由４个主要步骤构成：１）数据预处理．对原始数据进行编码后，执行特征维度削减，提前过滤一些无关特征，提高整个框架的执行效率．２）数据划分．基于极大等位公共子序列ＭＡＣＳ，将原始高维特征数据划分成一系列低维特征区域，并保证其“低耦合高内聚”性（即特征交互在区域内的可能性高，在区域间的可能性低）．３）特征区域筛选．许多划分后的特征区域具有较高的相似度．如果在所有特征区域上都执行交互赵宇海等：一种面向大规模序列数据的交互特征并行挖掘算法５９９
可能的“热区”．其问题在于，单位点过滤大多只保留具有强边际效应的候选位点，许多具有弱边际效应但具有强交互作用的位点组合被遗漏了．在对原始数据编码后，本节中将提出一种结合块过滤和位点过滤的２阶段过滤方法ＢＬＦｉｌｔｅｒ．先通过基于图论的块过滤，粗粒度地保留与疾病具有较高关联可能性的区域；再通过细粒度的位点过滤进一步提炼保留区域内的位点，以最大限度地保留边际效应弱但交互作用强的位点．Ｆｉｇ．３Ｔｈｅｇｒａｐｈｍｏｄｅｌｏｆｂｌｏｃｋｓ图３分块的图模型３．２．１块过滤块过滤阶段，输入序列被划分为??－Ｎ??ｋ?－块．其中，前??－Ｎ??ｋ?－－１块每块包含ｋ个位点，最后一块包含Ｎ－ｋ×??－Ｎ??ｋ??（－１）个位点．根据划分后块内和块间存在的显著交互位点对的数量，可构建如图３所示的无向权重图Ｇ＝（Ｖ，Ｅ）．其中，第ｉ个序列块对应顶点ｖｉ∈Ｖ．如果第ｉ个序列块和第ｊ个序列块之间存在显著交互的位点对，则存在边ｅｉｊ∈Ｅ．顶点ｖｉ的权重ｗｉ为块ｉ内显著交互的位点对数，边ｅｉｊ的权重ｗｉｊ为块ｉ和块ｊ之间的显著交互位点对数．对给定的顶点集合Ｖ′?Ｖ，若记其在Ｇ中对应的导出子图为Ｇ′，则可定义Ｇ′的密度为ｄ（Ｇ′）＝∑ｉ，ｊ∈Ｇ′∧ｉ＜ｊｗｉｊ＋∑ｋ∈Ｇ′ｖｋＳＧ′，（１）其中，ＳＧ′＝｜ＶＧ′｜＋｜ＶＧ′｜（｜ＶＧ′｜－１）２?
本文编号：3382412
【文章来源】：计算机研究与发展. 2019,56(05)北大核心EICSCD
【文章页数】：15 页
【部分图文】：
图１极大等位公共子序列的示例图Ｆｉｇ．１Ａｎｅｘａｍｐｌｅｏｆｍａｘｉｍａｌａｌｌｅｌｉｃｃｏｍｍｏｎｓｕｂｓｅｑｕｅｎｃｅ
ｍ，１≤ｊ≤ｔ，发现：所有满足定义３，与特定类标签ｃｒ∈Ｃ存在显著统计关联的ｋ阶交互特征并且满足ＦＷＥＲ≤α．３ＰＡＣＯＩＦＳ框架第２．１节所述，大规模生物序列中的高阶交互特征挖掘面临着密集计算问题．本节将提出一种新的基于并行处理和演化计算的解决框架（ＰＡＣＯＩＦＳ），并对构成框架的各主要步骤加以详细介绍．３．１整体思想图２给出了ＰＡＣＯＩＦＳ框架的总体示意图：Ｆｉｇ．２ＡｎｉｌｌｕｓｔｒａｔｉｏｎｏｆＰＡＣＯＩＦＳ图２ＰＡＣＯＩＦＳ框架示意图框架由４个主要步骤构成：１）数据预处理．对原始数据进行编码后，执行特征维度削减，提前过滤一些无关特征，提高整个框架的执行效率．２）数据划分．基于极大等位公共子序列ＭＡＣＳ，将原始高维特征数据划分成一系列低维特征区域，并保证其“低耦合高内聚”性（即特征交互在区域内的可能性高，在区域间的可能性低）．３）特征区域筛选．许多划分后的特征区域具有较高的相似度．如果在所有特征区域上都执行交互赵宇海等：一种面向大规模序列数据的交互特征并行挖掘算法５９９
可能的“热区”．其问题在于，单位点过滤大多只保留具有强边际效应的候选位点，许多具有弱边际效应但具有强交互作用的位点组合被遗漏了．在对原始数据编码后，本节中将提出一种结合块过滤和位点过滤的２阶段过滤方法ＢＬＦｉｌｔｅｒ．先通过基于图论的块过滤，粗粒度地保留与疾病具有较高关联可能性的区域；再通过细粒度的位点过滤进一步提炼保留区域内的位点，以最大限度地保留边际效应弱但交互作用强的位点．Ｆｉｇ．３Ｔｈｅｇｒａｐｈｍｏｄｅｌｏｆｂｌｏｃｋｓ图３分块的图模型３．２．１块过滤块过滤阶段，输入序列被划分为??－Ｎ??ｋ?－块．其中，前??－Ｎ??ｋ?－－１块每块包含ｋ个位点，最后一块包含Ｎ－ｋ×??－Ｎ??ｋ??（－１）个位点．根据划分后块内和块间存在的显著交互位点对的数量，可构建如图３所示的无向权重图Ｇ＝（Ｖ，Ｅ）．其中，第ｉ个序列块对应顶点ｖｉ∈Ｖ．如果第ｉ个序列块和第ｊ个序列块之间存在显著交互的位点对，则存在边ｅｉｊ∈Ｅ．顶点ｖｉ的权重ｗｉ为块ｉ内显著交互的位点对数，边ｅｉｊ的权重ｗｉｊ为块ｉ和块ｊ之间的显著交互位点对数．对给定的顶点集合Ｖ′?Ｖ，若记其在Ｇ中对应的导出子图为Ｇ′，则可定义Ｇ′的密度为ｄ（Ｇ′）＝∑ｉ，ｊ∈Ｇ′∧ｉ＜ｊｗｉｊ＋∑ｋ∈Ｇ′ｖｋＳＧ′，（１）其中，ＳＧ′＝｜ＶＧ′｜＋｜ＶＧ′｜（｜ＶＧ′｜－１）２?
本文编号：3382412
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3382412.html
