International Journal of Data Mining and Bioinformatics · 2010 · 16 citations · 26 references
ComputingBioinformaticsBiomedical InformaticsBiomedical Text MiningComputational BiologyGenomicsDuplicate DetectionNamed Entity RecognitionText Similarity AnalysisEdit DistanceGraph-based Duplicate DetectionSimilarity Detection
Duplicate entity detection in biological data is an important research task. In this paper, we propose a novel and context-sensitive Shortest Path Edit Distance (SPED) extending and supplementing our previous work on Markov Random Field-based Edit Distance (MRFED). SPED transforms the edit distance computational problem to the calculation of the shortest path among two selected vertices of a graph. We produce several modifications of SPED by applying Levenshtein, arithmetic mean, histogram difference and TFIDF techniques to solve subtasks. We compare SPED performance to other well-known distance algorithms for biological entity matching. The experimental results show that SPED produces competitive outcomes.
26
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Binary codes capable of correcting deletions, insertions and reversals
V.I. Levenshtein · Soviet physics. Doklady · 1965 · 10.4K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text