How algorithms that correct your spelling also help find cures for diseases.

  1. Identify misspelled word
  2. Find candidate strings n edits away
  3. Filter candidates
  4. Calculate word probabilities
  • Evaluate similarity between two strings
  • Find the minimum number of edits between two strings
  • Implement spelling correction, document similarity, machine translation, genome sequencing, and more
  • Insert (add a letter) ‘to’ -> ‘top’, ‘two’ …
  • Delete (remove a letter) ‘hat’ ->‘ha’, ‘at’, ‘ht’
  • Replace (change 1 letter to another) ‘jaw’ -> ‘jar’, ‘paw’, …
  • Distance between nold and mold strings is 1
  • Distance between nold and fnol strings is 2
  • Distance between nold and mold strings is 2
  • Distance between nold and fnol strings is 2

Algorithm

  • Initial state: the word we’re transforming
  • Operators: insert, delete, substitute
  • Goal state: the word we’re trying to get to
  • Path cost: what we want to minimise: the number of edits

Computational complexity:

  • We can’t afford to navigate naïvely
  • Lots of distinct paths wind up at the same state.
  • We don’t have to keep track of all of them
  • Just the shortest path to each of those revisited states.

Dynamic programming for calculating Minimum Edit Distance:

Other distance metrics:

  • Damerau–Levenshtein distance allows the transposition of two adjacent characters alongside insertion, deletion, substitution;
  • longest common subsequence (LCS) distance allows only insertion and deletion, not substitution;
  • Hamming distance allows only substitution, hence, it only applies to strings of the same length.
  • the Jaro distance allows only transposition.

Weighted Edit distance:

  • Spell Correction: some letters are more likely to be mistyped than others
  • Biology: certain kinds of deletions or insertions are more likely than others

NLP in computational biology

  • Compare genes or regions from different species
  • Assemble fragments to sequence DNA
  • Compare individuals to look for mutations

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sid dhuri

sid dhuri

I am data scientist by trade. I love to write about data science, marketing and economics. I am also the founder Orox.ai a marketing ai and automation platform.