COMPSCI320 Chap.9 Sequence Alignment, Edit Distance and Linear Space
Sequence Alignment, Edit Distance and Linear Space
Edit distance measures how similar two strings are by the cheapest alignment under a gap penalty and a mismatch penalty.
This chapter defines alignments, derives the three-case recurrence, fills and traces back a full table, explains how Hirschberg's method recovers an optimal alignment in linear space, and reduces the longest common subsequence to alignment.
The worked table uses short words so every entry can be checked, and the practice cards change the penalties to show how the optimal alignment shifts.
The chapter also explains why linear space is easy for the value but needs divide and conquer for the alignment itself.
What this chapter covers
- 01
Alignments without crossing pairs
- 02
Gap and mismatch penalties
- 03
The three-case recurrence
- 04
Filling and tracing back the table
- 05
Hirschberg's linear-space method
- 06
Longest common subsequence
Worked example · free
Align two words with gap and mismatch penalties
- 1Fill the first row and column with multiples of 2.
- 1Fill each cell as the minimum of the diagonal, upper and left candidates.
- 1The bottom-right cell gives an optimal cost of 7.
- 1Trace back: S–S, N–N, W–N and Y–Y with O and U unmatched, costing 3 + 2 + 2.
Key terms
- Edit Distance
- The minimum total penalty of an alignment that lines up two strings using gaps and mismatches.
- Gap Penalty
- The cost charged for each character left unmatched in an alignment.
- Sequence Alignment
- A set of non-crossing pairs of characters from two strings, each character used at most once.
- Longest Common Subsequence
- The longest string obtainable from both strings by deleting characters without reordering.
- Hirschberg's Method
- A divide and conquer refinement that recovers an optimal alignment in linear space.
- Mismatch Penalty
- The cost charged for pairing two different characters in an alignment.
Sequence Alignment, Edit Distance and Linear Space FAQ
Why are the first row and column of the table not zero?
They align a prefix of one string with the empty string, so every character of that prefix is left unmatched and pays the gap penalty. The entry for a prefix of length i is therefore i times the gap penalty. Writing zeros there is the most common slip on these tables and shifts every later entry.
How can an alignment be found in linear space?
Hirschberg's method finds a point on an optimal path through the middle column by adding forward distances from the start to backward distances from the end. Both columns can be computed with two rows of memory. Recording that point and recursing on the two halves recovers the whole alignment, still in O(mn) time but O(m + n) space.
How is the longest common subsequence related to edit distance?
Set the gap penalty to 1 and make every mismatch infinitely expensive, so an alignment uses only matches and gaps. The matched characters form a common subsequence and every other character is a gap. The length of the longest common subsequence is then the total length of both strings minus the edit distance, all divided by two.
How do the penalties change the best alignment?
The best alignment balances mismatches against gaps. When a mismatch is cheap compared with two gaps, the alignment pairs characters even if they differ; when a mismatch is expensive, it leaves characters unmatched instead. Recompute the whole table when a penalty changes, because the change can alter decisions well before the final cell.
Exam move
Fill two full tables by hand, one with cheap and one with expensive mismatches, and compare the alignments they produce. Practise the traceback by labelling each step as a pair, a gap in the first string or a gap in the second. Then explain the Hirschberg split in three sentences without notes.
As a last drill, align two short words of your own under two different penalty settings and explain in one sentence why the optimal alignment changed. Close by writing the longest common subsequence recurrence beside the alignment recurrence and marking where they differ.
Working through Sequence Alignment, Edit Distance and Linear Space in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Sequence Alignment, Edit Distance and Linear Space question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
