一种面向大规模序列数据的交互特征并行挖掘算法
|
摘要
序列是一种重要的数据类型,在诸多应用领域广泛存在.基于序列的特征选择具有广阔的现实应用场景.交互特征是指一组整体具有显著强于单独个体与目标相关性的特征集合.从大规模序列中挖掘交互特征面临着位点的"组合爆炸"问题,计算挑战性极大.针对该问题,以生物领域高通量测序数据为背景,提出了一种新的基于并行处理和演化计算的高阶交互特征挖掘算法.位点数是制约交互作用挖掘效率的根本因素.摈弃了现有方法基于序列分块的并行策略,采用基于位点分块的并行思想,具有天然的效率优势.进一步,提出了极大等位公共子序列(maximal allelic common subsequence, MACS)的概念并设计了基于MACS的特征区域划分策略.该策略能将交互特征的查找范围缩小至许多"碎片"空间,并保证不同"碎片"间不存在交互特征,避免计算耦合引起的高额通信代价.利用基于置换搜索的并行蚁群算法,执行交互特征选择.大量真实数据集和合成数据集上的实验结果,证实提出的PACOIFS算法在有效性和效率上优于同类其他算法.
Sequence is an important type of data which is widely existing in various domains, and thus feature selection from sequence data is of practical significance in extensive applications. Interactive features refer to a set of features, each of which is weakly correlated with the target, but the whole of which is strongly correlated with the target. It is of great challenge to mine interactive features from large scale sequence data for the combinatorial explosion problem of loci. To address the problem, against the background of high-throughput sequencing in biology, a parallel evolutionary algorithm for high-order interactive features mining is proposed in this paper. Instead of sequence-block based parallel strategy, the work is inspired by loci-based idea since the number of loci is the fundamental factor that restricts the efficiency. Further, we propose the conception of maximal allelic common subsequence(MACS) and MACS based strategy for feature region partition. According to the strategy, the search range of interactive features is narrowed to many fragged spaces and interactions are guaranteed not to exist among different fragments. Finally, a parallel ant algorithm based on substitution search is developed to conduct interactive feature selection. Extensive experiments on real and synthetic datasets show that the efficiency and effectiveness of the proposed PACOIFS algorithm is superior to that of competitive algorithms.
Sequence is an important type of data which is widely existing in various domains, and thus feature selection from sequence data is of practical significance in extensive applications. Interactive features refer to a set of features, each of which is weakly correlated with the target, but the whole of which is strongly correlated with the target. It is of great challenge to mine interactive features from large scale sequence data for the combinatorial explosion problem of loci. To address the problem, against the background of high-throughput sequencing in biology, a parallel evolutionary algorithm for high-order interactive features mining is proposed in this paper. Instead of sequence-block based parallel strategy, the work is inspired by loci-based idea since the number of loci is the fundamental factor that restricts the efficiency. Further, we propose the conception of maximal allelic common subsequence(MACS) and MACS based strategy for feature region partition. According to the strategy, the search range of interactive features is narrowed to many fragged spaces and interactions are guaranteed not to exist among different fragments. Finally, a parallel ant algorithm based on substitution search is developed to conduct interactive feature selection. Extensive experiments on real and synthetic datasets show that the efficiency and effectiveness of the proposed PACOIFS algorithm is superior to that of competitive algorithms.
引文
[1]Beedkar K,Gemulla R.LASH:Large-scale sequence mining with hierarchies[C]Proc of ACM SIGMOD 2015.New York:ACM,2015:491-503
[2]Zhang Peng,Duan Lei,Qin Pan,et al.Mining top-k distinguishing sequential patterns using spark[J].Journal of Computer Research and Development,2017,54(7):1452-1464(in Chinese)(张鹏,段磊,秦攀,等.基于Spark的Top-k对比序列模式挖掘[J].计算机研究与发展,2017,54(7):1452-1464)
[3]Li Pei,Guo Maozu,Wang Chunyu,et al.An overview of SNP interactions in genome-wide association studies[J].Briefings in Functional Genomics,2015,14(2):143-155
[4]Huang Qingyang.Genetic study of complex diseases in the post-GWAS era[J].Journal of Genetics and Genomics,2015,42(3):87-98
[5]Lin Huiyi,Chen Dungtra,Huang Poyu,et al.SNPinteraction pattern identifier(SIPI):An intensive search for SNP-SNP interaction patterns[J].Bioinformatics,2017,33(6):822-833
[6]Pers H,Karjalainen J.Biological interpretation of genomewide association studies using predicted gene functions[J].Nature Communications,2015,6(25):5890-5898
[7]Kotler M,Barak P.Homicidal behavior in schizophrenia associated with a genetic polymorphism determining low catechol O-methyltransferase(COMT)activity[J].American Journal of Medical Genetics,2000,88(6):628-33
[8]Wonodi L,Stine O,Mitchell B,et al.Association between Val108?158 met polymorphism of the COMT gene and schizophrema[J].American Journal of Medical Genetics,2003,120B(1):47-50
[9]Terada A,Yamada R,Tsuda K,et al.LAMPLINK:Detection of statistically significant SNP combinations from GWAS data[J].Bioinformatics,2016,32(22):3513-3515
[10]Ding Xiaojun,Wang Jianxin,Zelikovsky A,et al.Searching high-order SNP combinations for complex diseases based on energy distribution difference[J].IEEE?ACM Transactions on Computational Biology&Bioinformatics,2015,12(3):695-704
[11]Taylor M,Ehrenreich I.Higher-order genetic interactions and their contribution to complex traits[J].Trends in Genetics Tig,2015,31(1):34-40
[12]Zhang Yu,Liu Jun.Bayesian inference of epistatic interactions in case-control studies[J].Nature Genetics,2007,39(9):1167-1173
[13]Marchini J,Donnelly P.Genome-wide strategies for detecting multiple loci that influence complex diseases[J].Nature Genetics,2005,37(4):413-417
[14]Wang Yupeng,Liu Xinyu,Robbins K,et al.Ant epiSeeker:Detecting epistatic interactions for case-control studies using a two-stage ant colony optimization algorithm[J].BMCResearch Notes,2010,3(1):117-124
[15]Llinares-López F,Sugiyama M,Papaxanthos L,et al.Fast and memory-efficient significant pattern mining via permutation testing[C]Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining(KDD’15).New York:ACM,2015:725-734
[16]Janssens A,Duijn M.Genome-based prediction of common diseases:Advances and prospects[J].Human Molecular Genetics,2008,17(R2):166-173
[17]Goldberg A.Finding a maximum density subgraph,UCB?CSD-84-171[R].Berkeley:University of California at Berkeley,1984
[18]Charikar M.Greedy approximation algorithms for finding dense components in a graph[G]LNCS 1913:Proc of Approximation Algorithms for Combinatorial Optimization.Berlin:Springer,2000:139-152
[19]Marchini J,Donnelly P.Genome-wide strategies for detecting multiple loci that influence complex diseases[J].Nature Genetics,2005,37(4):413-417
[20]Urbanowicz R,Jeff K,Sinnott-Armstrong N,et al.GAMETES:A fast,direct algorithm for generating pure,epistatic models with random architectures[J].Biodata Mining,2012,5(1):16
[2]Zhang Peng,Duan Lei,Qin Pan,et al.Mining top-k distinguishing sequential patterns using spark[J].Journal of Computer Research and Development,2017,54(7):1452-1464(in Chinese)(张鹏,段磊,秦攀,等.基于Spark的Top-k对比序列模式挖掘[J].计算机研究与发展,2017,54(7):1452-1464)
[3]Li Pei,Guo Maozu,Wang Chunyu,et al.An overview of SNP interactions in genome-wide association studies[J].Briefings in Functional Genomics,2015,14(2):143-155
[4]Huang Qingyang.Genetic study of complex diseases in the post-GWAS era[J].Journal of Genetics and Genomics,2015,42(3):87-98
[5]Lin Huiyi,Chen Dungtra,Huang Poyu,et al.SNPinteraction pattern identifier(SIPI):An intensive search for SNP-SNP interaction patterns[J].Bioinformatics,2017,33(6):822-833
[6]Pers H,Karjalainen J.Biological interpretation of genomewide association studies using predicted gene functions[J].Nature Communications,2015,6(25):5890-5898
[7]Kotler M,Barak P.Homicidal behavior in schizophrenia associated with a genetic polymorphism determining low catechol O-methyltransferase(COMT)activity[J].American Journal of Medical Genetics,2000,88(6):628-33
[8]Wonodi L,Stine O,Mitchell B,et al.Association between Val108?158 met polymorphism of the COMT gene and schizophrema[J].American Journal of Medical Genetics,2003,120B(1):47-50
[9]Terada A,Yamada R,Tsuda K,et al.LAMPLINK:Detection of statistically significant SNP combinations from GWAS data[J].Bioinformatics,2016,32(22):3513-3515
[10]Ding Xiaojun,Wang Jianxin,Zelikovsky A,et al.Searching high-order SNP combinations for complex diseases based on energy distribution difference[J].IEEE?ACM Transactions on Computational Biology&Bioinformatics,2015,12(3):695-704
[11]Taylor M,Ehrenreich I.Higher-order genetic interactions and their contribution to complex traits[J].Trends in Genetics Tig,2015,31(1):34-40
[12]Zhang Yu,Liu Jun.Bayesian inference of epistatic interactions in case-control studies[J].Nature Genetics,2007,39(9):1167-1173
[13]Marchini J,Donnelly P.Genome-wide strategies for detecting multiple loci that influence complex diseases[J].Nature Genetics,2005,37(4):413-417
[14]Wang Yupeng,Liu Xinyu,Robbins K,et al.Ant epiSeeker:Detecting epistatic interactions for case-control studies using a two-stage ant colony optimization algorithm[J].BMCResearch Notes,2010,3(1):117-124
[15]Llinares-López F,Sugiyama M,Papaxanthos L,et al.Fast and memory-efficient significant pattern mining via permutation testing[C]Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining(KDD’15).New York:ACM,2015:725-734
[16]Janssens A,Duijn M.Genome-based prediction of common diseases:Advances and prospects[J].Human Molecular Genetics,2008,17(R2):166-173
[17]Goldberg A.Finding a maximum density subgraph,UCB?CSD-84-171[R].Berkeley:University of California at Berkeley,1984
[18]Charikar M.Greedy approximation algorithms for finding dense components in a graph[G]LNCS 1913:Proc of Approximation Algorithms for Combinatorial Optimization.Berlin:Springer,2000:139-152
[19]Marchini J,Donnelly P.Genome-wide strategies for detecting multiple loci that influence complex diseases[J].Nature Genetics,2005,37(4):413-417
[20]Urbanowicz R,Jeff K,Sinnott-Armstrong N,et al.GAMETES:A fast,direct algorithm for generating pure,epistatic models with random architectures[J].Biodata Mining,2012,5(1):16