A bioinformatics-inspired adaptation to Ukkonen's edit distance calculating algorithm

ABSTRACT

Edit distance measures the similarity between two strings (as the minimum number of change, insert or delete operations that transform one string to the other). An edit sequence s is a sequence of such operations and can be used to represent the string resulting from applyings to a reference string. We present a modification to Ukkonen's edit distance calculating algorithm based upon representing strings by edit sequences. We conclude with a demonstration of how using this representation can improve mitochondrial DNA query performance.

REFERENCES

• 1: Vose, M. D. 2004. A Formal Analysis of Edit Distance. UT CS Technical Report ut-cs-04-517, Feb. 2004
• 2: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 3: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 4: Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
• 5: Esko Ukkonen, On Approximate String Matching, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.487-495, August 21-27, 1983
• 6: Campbell, N. and Reese, J. 1997 Biology (6th ed.). Addison Wesley.
• 7: Anderson, S., et al. 1981 Sequence and organization of the human mitochondrial genome. Nature, 290(5806) (April 9, 1981), 457--265.
• 8: K. L. Monson, et al. 2002. The mtDNA population database: an integrated software and database resource for forensic comparison, Forensic Science Communications, 4(2), April 2002. DOI = http://www.fbi.gov/hq/lab/fsc/backissu/april2002/miller1.htm

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Performance

Keywords:
bioinformatics, edit distance