A Novel Similarity Measure for Sequence Data
2
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
A variety of different metrics has been introduced to measure the similarity of two given sequences. These widely used metrics are ranging from spell correctors and categorizers to new sequence mining applications. Different metrics consider different aspects of sequences, but the essence of any sequence is extracted from the ordering of its elements. In this paper, we propose a novel sequence similarity measure that is based on all ordered pairs of one sequence and where a Hasse diagram is built in the other sequence. In contrast with existing approaches, the idea behind the proposed sequence similarity metric is to extract all ordering features to capture sequence properties. We designed a clustering problem to evaluate our sequence similarity metric. Experimental results showed the superiority of our proposed sequence similarity metric in maximizing the purity of clustering compared to metrics such as d2, Smith-Waterman, Levenshtein, and Needleman-Wunsch. The limitation of those methods originates from some neglected sequence features, which are considered in our proposed sequence similarity metric.
Abstract
A variety of different metrics has been introduced to measure the similarity of two given sequences. These widely used metrics are ranging from spell correctors and categorizers to new sequence mining applications. Different metrics consider different aspects of sequences, but the essence of any sequence is extracted from the ordering of its elements. In this paper, we propose a novel sequence similarity measure that is based on all ordered pairs of one sequence and where a Hasse diagram is built in the other sequence. In contrast with existing approaches, the idea behind the proposed sequence similarity metric is to extract all ordering features to capture sequence properties. We designed a clustering problem to evaluate our sequence similarity metric. Experimental results showed the superiority of our proposed sequence similarity metric in maximizing the purity of clustering compared to metrics such as d2, Smith-Waterman, Levenshtein, and Needleman-Wunsch. The limitation of those methods originates from some neglected sequence features, which are considered in our proposed sequence similarity metric.
참고문헌 (34)
- G. Dong, "Sequence Data Mining: Springer; 1 edition" (2007), Springer
- Y. Jiong, "CLUSEQ: Efficient and Effective Sequence Clustering", 19th International Conference on Data Engineering, Bangalore, India, pp.101~112 (2003)
- W. Cohen, "A Comparison of String Metrics for Matching Names and Records", ACM International Conference on Knowledge Discovery and Data Mining (KDD) 09, Workshop on Data Cleaning, Record Linkage, and Object Consolidation (2003)
- T. F. Smith, "Identification of Common Molecular Subsequences", Journal of Molecular Biology, 147, pp.195~197 (1981)
- D. C. Torney, "Computation of d2:A Measure of Sequence Dissimilarity", Computers and DNA, pp.109~125 (1990)
- Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady, 10, pp.707~710 (1966)
- S. B. Needleman, "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins", Journal of Molecular Biology, 48, pp.443~453 (1970)
- K. Min, "Typographical and Orthographical Spelling Error Correction", ~ (2008)
- Hodge, "An Evaluation of Phonetic Spell Checkers", Mechanisms of Radiation Eflects in Electronic Materials, ~ (2001)
- B. Bansal, "Isolated-word Error Correction for Partially Phonemic Languages using Phonetic Cues", International Conference on Knowledge based Computer Systems (KBCS 2004), Hyderabad, India, pp.509~519 (2004)
- R. Mitton, "Ordering the suggestions of a spellchecker without using context", Nat. Lang. Eng, 15, pp.173~192 (2009)
- L. Yujian, "A Normalized Levenshtein Distance Metric", IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (2007)
- M. Bilenko, "Adaptive Duplicate Detection Using Learnable String Similarity Measures", ninth ACM SIGKDD international conference on Knowledge discovery and data mining, Washington, D.C (2003)
- E. S. Ristad, "Learning String Edit Distance", IEEE Transactions on Pattern Recognition and Machine Intelligence, 20, pp.522~532 (1998)
- P. Jaccard, "Étude comparative de la distribution florale dans une portion des Alpes et des Jura", Bulletin de la Société Vaudoise des Sciences Naturelles, 37, pp.547~579 (1901)
- V. J. Hodge, "A Novel Binary Spell Checker", International Conference on Artificial Neural Networks (ICANN'2001), Vienna, Austria (2001)
- R. W. Hamming, "Error detecting and error correcting codes", Bell System Technical Journal, 29, pp.147~160 (1950)
- J. Zobel, "Finding approximate matches in large lexicons", Softw. Pract. Exper, 25, pp.331~345 (1995)
- A. Elmagarmid, "Duplicate Record Detection: A Survey", IEEE Transactions on Knowledge and Data Engineering, 19, pp.1~16 (2007)
- A. E. Monge, "The field matching problem: Algorithms and applications", Second International Conference on Knowledge Discovery and Data Mining, (KDD) (1996)
- M. A. Jaro, "Advances in record linkage methodology as applied to the 1985 census of Tampa Florida", Journal of the American Statistical Society, 84, pp.414~420 (1989)
- M. A. Jaro, "Probabilistic linkage of large public health data file", Statistics in Medicine, 14, pp.491~498 (1995)
- String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage', in Section on Survey Research Methods, "W. E. Winkler", American Statistical Association, 472~477 (1990)
- J. Zobel, "Phonetic String Matching: Lessons from Information Retrieval", 19th annual international ACM SIGIR conference on Research and development in information retrieval (1996)
- J. M. Ponte, "A language modeling approach to information retrieval", 21st annual international ACM SIGIR conference on Research and development in information retrieval (SIGIR '98), ACM, New York, NY, USA, pp.275~281 (1998)
- C. D. Manning, "An Introduction to Information Retrieval 1 edition" (2008), Cambridge University Press
- Altschul, "Basic local alignment search tool", J Mol Biol, 215, pp.403~410 (1990)
- W. Pearson, "Rapid and sensitive sequence comparisonwith fastp and fasta", Methods Enzymol, 183, pp.63~98 (1990)
- L. Noe, "YASS: enhancing the sensitivity of DNA similarity search", Nucleic Acids Research, 33(2), pp.540~543 (2005)
- W. G. Liu, "Bio-Sequence Database Scanning on a GPU", ~ (2006)
- K. H. Rosen, "The Growth of Functions,” in Discrete Mathematics and its Applications, 4th edition", pp.80~90 (1998), McGraw-Hill
- D. J. Hartfiel, "Markov Set-Chains" (1998), Springer-Verlag
- T. Hastie, "Hierarchical clustering, in The Elements of Statistical Learning", pp.520~528 (2009), Springer
- E. Amigó, "A comparison of extrinsic clustering evaluation metrics based on formal constraints", Information Retrieval, 12, pp.461~486 (2008)