期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Pattern Matching with Flexible Wildcards 被引量：1

Pattern Matching with Flexible Wildcards
原文传递
导出
摘要 Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications. Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.
作者 吴信东 强继朋 谢飞
机构地区 Department of Computer Science Department of Computer Science Department of Computer Science and Technology
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 2014年第5期740-750,共11页 计算机科学技术学报（英文版）
基金 supported in part by the National Natural Science Foundation of China under Grant Nos.61229301 and 60828005 the Program for Changjiang Scholars and Innovative Research Team in University(PCSIRT)of the Ministry of Education,China,under Grant No.IRT13059 the National Science Foundation(NSF)of USA under Grant No.0514819
关键词 pattern matching WILDCARDS BIOINFORMATICS pattern mining pattern matching wildcards bioinformatics pattern mining
分类号 TP391.3 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献49

  • 1Cole J R, Chai B, Farris R J el al. The Ribosomal Database Project (RDP-II): Sequences and tools for high-throughput rRNA analysis. Nucleic Acids Research, 2005, 33(Database Issue): 294-296.
  • 2Mendivelso J, Pinzon Y, Lee I. Finding overlaps within regular expressions with variable-length gaps. In Proc. the 2013 Research in Adaptive and Convergent Systems, Oct. 2013, pp.16-21.
  • 3Patnaik D, Laxman S, Chandramouli B, Ramakrishnan N. A general streaming algorithm for pattern discovery. Knowledge and Information Systems, 2013, 37(3): 585-610.
  • 4Xie F, Wu X, Hu X et al. Sequential pattern mining with wildcards. In Proc. the 22nd IEEE International Conference on Tools with Artificial Intelligence, Oct. 2010, pp.241-247.
  • 5Ding B, Lo D, Han J, Khoo S. Efficient mining of closed repetitive gapped subsequences from a sequence database. In Proc. the 25th IEEE International Conference on Data Engineering, Mar. 29-April 2, 2009, pp.1024-1035.
  • 6El-Ramly M, Stroulia E, Sorenson P. Prom run-time behavior to usage scenarios: An interaction-pattern mining approach. In Proc. the 8th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, July 2002, pp.315-324.
  • 7Manber U, Baeza^ Yates R. An algorithm for string matching with a sequence of don’t cares. Information Processing Letters, 1991, 37(3): 133-136.
  • 8de Pablo-Sanchez C, Segura-Bedmar I, Martinez P, Iglesias-Maqueda A. Lightly supervised acquisition of named entities and linguistic patterns for multilingual text mining. Knowledge and Information Systems, 2013, 35(1): 87-109.
  • 9Barbieri N, Bonchi F, Manco G. Topic-aware social influence propagation models. Knowledge and Information Systems, 2013, 37(3): 555-584.
  • 10Wei Y, Dominique F, Jean-Paul B. An automatic keyphrase extraction system for scientific documents. Knowledge and Information Systems, 2013, 34(3): 691-724.

同被引文献18

  • 1Fischer M J,Paterson M S.String matching and other products[R].Cambridge,MA:Massachusetts Institute of Technology ,1974.
  • 2Manber U,Baeza-Yates R.An Algorithm for String Matching with a Sequence of Don’t cares[J].Information Processing Letters,1991,37(3):133-136.
  • 3Califf M E,Mooney R J.Bottom-up Relational Learning of Pattern Matching Rules for Information Extraction[J].Journal of Machine Learning Research,2003,4(6):177-210.
  • 4Guo Dan,Hu Xue-gang,Xie Fei,et al.Pattern Matching withWildcards and Gap-length Constraints Based on a Centrality-degree Graph[J].Applied Intelligence,2013,39:57-74.
  • 5Dahiya A,Garg D.Maximal pattern matching with flexible wildcard gaps and one-off constraint[C]∥International Conference on Advances in Computing,Communications and Informatics.Arras,France,2014:1107-1112.
  • 6Chen Gong,Wu Xin-dong,Zhu Xing-quan,et al.Efficient string matching with wildcards and length constraints[J].Knowledge and Information Systems,2006,10(4):399-419.
  • 7Min Fan,Wu Xin-dong,Lu Zhen-yu.Pattern matching with independent wildcard gaps[C]∥Proceedings of the 8th IEEE International Conference on Dependable,Autonomic and Secure Computing.2009:194-199.
  • 8Brailsford S C,Potts C N,Smith B M.Constraint satisfaction problems:Algorithms and applications[J].European Journal of Operational Research,1999,119:557-581.
  • 9Bala S.Regular language matching and other decidable cases ofthe satisfiability problem for constraints between regular open terms[J].Theory of Computing Systems,2004,39:596-607.
  • 10Kucherov G,Rusinowitch M.Matching a set of strings with va-riable length don’t cares[C]∥ Proceedings of the 6th sympo-sium on Combinatorial Pattern Matching.1995:230-247.

引证文献1

二级引证文献1

Journal of Computer Science & Technology
2014年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部