11.3 Longest common subsequence and edit distance

Dynamic programming shines in solving sequence comparison problems like the Longest Common Subsequence (LCS) and Edit Distance. These algorithms find patterns and measure similarities between strings, crucial in fields like bioinformatics, text analysis, and version control.

Both LCS and Edit Distance use clever table-filling techniques to break down complex problems into manageable subproblems. By storing and reusing intermediate results, they achieve efficient solutions, showcasing the power of dynamic programming in tackling real-world challenges.

Longest Common Subsequence Problem

Definition and Applications

Top images from around the web for Definition and Applications

• 

  Frontiers | Immune2vec: Embedding B/T Cell Receptor Sequences in ℝN Using Natural Language ... View original

  Is this image relevant?

• 

  NGS sequence analysis — Bioinformatics at COMAV 0.1 documentation View original

  Is this image relevant?

• 

  Natural Language Processing View original

  Is this image relevant?

• 

  Frontiers | Immune2vec: Embedding B/T Cell Receptor Sequences in ℝN Using Natural Language ... View original

  Is this image relevant?

• 

  NGS sequence analysis — Bioinformatics at COMAV 0.1 documentation View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Applications

• 

  Frontiers | Immune2vec: Embedding B/T Cell Receptor Sequences in ℝN Using Natural Language ... View original

  Is this image relevant?

• 

  NGS sequence analysis — Bioinformatics at COMAV 0.1 documentation View original

  Is this image relevant?

• 

  Natural Language Processing View original

  Is this image relevant?

• 

  Frontiers | Immune2vec: Embedding B/T Cell Receptor Sequences in ℝN Using Natural Language ... View original

  Is this image relevant?

• 

  NGS sequence analysis — Bioinformatics at COMAV 0.1 documentation View original

  Is this image relevant?

1 of 3

• Longest common subsequence (LCS) finds the longest subsequence common to two or more sequences
• Subsequence appears in the same relative order but not necessarily contiguous
• Applications in bioinformatics compare genetic sequences and identify similarities between DNA or protein sequences
• Version control systems use LCS to determine differences between file versions and generate efficient diff outputs
• Natural language processing employs LCS for plagiarism detection and text similarity analysis
• Multiple sequence alignment problem extends LCS to multiple sequences crucial in evolutionary biology and comparative genomics
• LCS serves as foundation for related problems (shortest common supersequence, longest increasing subsequence)

Problem Characteristics

• Exhibits optimal substructure allows problem to be broken down into smaller subproblems
• Contains overlapping subproblems solutions to subproblems can be reused
• Suitable for dynamic programming approach due to these characteristics
• Can be solved recursively but inefficient for large inputs due to redundant computations
• Efficient solution requires storing and reusing intermediate results

Dynamic Programming for LCS

Table Construction and Filling

• Construct 2D table to store LCS lengths for all prefixes of two input sequences
• Table dimensions (m+1) x (n+1) where m and n are lengths of sequences
• Fill table using recurrence relation based on character comparison:
  • If characters match add 1 to LCS length of prefixes without these characters
  • If characters don't match take maximum of LCS lengths excluding one character from either sequence
• Recurrence relation: 0 & \text{if } i = 0 \text{ or } j = 0 \\ LCS[i-1][j-1] + 1 & \text{if } X[i] = Y[j] \\ \max(LCS[i-1][j], LCS[i][j-1]) & \text{if } X[i] \neq Y[j] \end{cases}$$
• Example: For sequences "ABCDGH" and "AEDFHR" LCS is "ADH" with length 3

Algorithm Complexity and Optimization

• Time complexity O(mn) where m and n are lengths of input sequences
• Space complexity O(mn) can be optimized to O(min(m,n)) by using only two rows of table at a time
• Backtracking through filled table reconstructs actual LCS sequence not just its length
• Optimization techniques:
  • Using bit vectors for binary alphabet
  • Hirschberg's algorithm combines divide-and-conquer with dynamic programming to achieve O(min(m,n)) space complexity

Edit Distance Problem

Problem Definition and Significance

• Edit distance (Levenshtein distance) measures minimum number of single-character edits to transform one string into another
• Single-character edits include insertions deletions and substitutions
• Fundamental in computational linguistics DNA sequence alignment and spell-checking algorithms
• Provides quantitative measure of string similarity crucial in fuzzy string matching and approximate string matching
• Natural language processing uses edit distance for automatic spelling error correction and speech recognition
• Bioinformatics applies edit distance to analyze mutations and evolutionary relationships between genetic sequences
• Generalizes to weighted edit distance where different edit operations have varying costs allowing nuanced comparisons

Applications and Variations

• Spell checkers suggest corrections based on words with low edit distance from misspelled word
• DNA sequence alignment uses edit distance to measure similarity between genetic sequences
• Plagiarism detection compares document similarity using edit distance on word or sentence level
• Fuzzy string search finds strings that approximately match a pattern within a specified edit distance
• Weighted edit distance assigns different costs to various edit operations (transposition might cost less than substitution)
• Example: Edit distance between "kitten" and "sitting" is 3 (substitute 'k' for 's' substitute 'e' for 'i' insert 'g' at the end)

Dynamic Programming for Edit Distance

Table Construction and Filling

• Construct (m+1) x (n+1) table where m and n are lengths of input strings
• Base cases represent edit distances between empty strings and prefixes of input strings
• Fill table using recurrence relation considering three operations at each step:
  • Insertion
  • Deletion
  • Substitution (or match if characters are the same)
• Recurrence relation: D[i-1][j] + 1 & \text{(deletion)} \\ D[i][j-1] + 1 & \text{(insertion)} \\ D[i-1][j-1] + \text{cost} & \text{(substitution or match)} \end{cases}$$ Where cost = 0 if characters match 1 otherwise
• Example: Edit distance between "cat" and "cut" is 1 (substitute 'a' with 'u')

Algorithm Implementation and Extensions

• Time complexity O(mn) where m and n are lengths of input strings
• Space complexity O(mn) optimizable to O(min(m,n)) using only two rows of table
• Backtracking through filled table reconstructs actual sequence of edit operations
• Algorithm extensions:
  • Handle more complex edit operations (transpositions swapping adjacent characters)
  • Custom costs for different types of edits (making vowel substitutions cheaper than consonant substitutions)
  • Damerau-Levenshtein distance includes transposition as a single edit operation
• Practical implementations often use optimizations:
  • Early termination when edit distance exceeds a threshold
  • Bit-parallel algorithms for faster computation on modern processors