Algo Tabulation

Tabulation (Bottom-Up Dynamic Programming)

When to Use

• Comparing two strings/sequences and need an edit distance, alignment score, or LCS without pulling in a full aligner library
• Recursive/memoized DP hits RecursionError on long sequences and needs converting to an iterative table
• Need to quickly pre-screen candidate sequences by similarity before running expensive Needleman-Wunsch/Smith-Waterman alignment
• Finding the longest increasing trend in a numeric series (e.g., expression values over a time course)
• Need O(1) or O(min(m,n)) space instead of O(mn), because the sequences are long and only the final score (not full traceback) is needed

Version Compatibility

Pure Python stdlib — no external dependencies. Works on Python ≥3.8 (uses only list comprehensions and tuple unpacking).

Prerequisites

• Understand recursion + memoization first (see algo-intro-memoization)
• Comfortable with 2D list indexing and nested loops
• For biological alignment scoring (gap penalties, substitution matrices), see algo-sequence-alignment — tabulation here is the unweighted/uniform-cost special case

Memoization vs Tabulation

Goal: Warm up with the classic O(1)-space rolling-variable pattern before applying it to sequences. Approach: Keep only the last two values instead of a full table.

def fib_optimized(n):
    """Bottom-up Fibonacci using O(1) space (two rolling variables)."""
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Edit Distance (Levenshtein) with Traceback

Goal: Compute the minimum insert/delete/substitute operations to transform one DNA/protein string into another, and recover the actual operations (not just the count). Approach: Fill dp[i][j] = edit distance between s1[:i] and s2[:j], then walk backward from dp[m][n] re-deriving which transition produced each cell.

def edit_distance_with_ops(s1, s2):
    """
    Compute Levenshtein distance and the traceback of edit operations.

    dp[i][j] = min edits to transform s1[:i] into s2[:j].
    Returns (distance, ops) where ops is a list of tuples:
      ('Match', c), ('Substitute', c1, c2), ('Delete', c), ('Insert', c)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # delete all of s1[:i]
    for j in range(n + 1):
        dp[0][j] = j  # insert all of s2[:j]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete from s1
                    dp[i][j - 1],      # insert into s1
                    dp[i - 1][j - 1],  # substitute
                )

    # Traceback: re-derive which transition produced each cell
    ops = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i - 1] == s2[j - 1]:
            ops.append(('Match', s1[i - 1])); i -= 1; j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(('Substitute', s1[i - 1], s2[j - 1])); i -= 1; j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(('Delete', s1[i - 1])); i -= 1
        else:
            ops.append(('Insert', s2[j - 1])); j -= 1

    ops.reverse()
    return dp[m][n], ops


distance, ops = edit_distance_with_ops("ATCG", "TACG")
assert distance == 2  # ops holds the Insert/Match/Delete trace that produced it

Longest Common Subsequence (LCS)

Goal: Find the longest subsequence common to two sequences and use its length as a fast conservation/similarity score. Approach: Same table shape as edit distance but maximizing matches instead of minimizing edits; traceback follows the larger neighbor.

def lcs_with_traceback(s1, s2):
    """Return the longest common subsequence string of s1 and s2."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))


def lcs_similarity(s1, s2):
    """Quick conservation score in [0, 1]: LCS length / longer sequence length.

    ~1.0: highly conserved (e.g. orthologs in closely related species)
    ~0.5: moderate conservation (e.g. diverged paralogs)
    ~0.0: little shared structure
    Cheaper than a full Needleman-Wunsch/Smith-Waterman pass — good for
    pre-screening candidates before running an expensive aligner.
    """
    lcs_len = len(lcs_with_traceback(s1, s2))
    return lcs_len / max(len(s1), len(s2))

Space-Optimized LCS Length — O(min(m,n)) space

Goal: Get the LCS length for long sequences without paying O(mn) memory. Approach: Only the previous row is needed, so keep two 1D arrays instead of a full 2D table (loses traceback ability).

def lcs_length_space_optimized(s1, s2):
    """LCS length using only two rows of size min(m,n)+1."""
    if len(s2) > len(s1):
        s1, s2 = s2, s1
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]

Bonus: Longest Increasing Subsequence (LIS)

Goal: Find the longest increasing run in a numeric series, e.g. an increasing trend across gene-expression time points. Approach: dp[i] = length of the LIS ending at index i; O(n²) tabulation (use bisect for O(n log n) if the series is long).

def lis_length(arr):
    """Length of the longest strictly increasing subsequence, O(n^2)."""
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


expression = [2.1, 3.5, 1.2, 4.8, 3.9, 5.2, 6.1, 4.5, 7.0]
assert lis_length(expression) == 6  # e.g. 2.1, 3.5, 4.8, 5.2, 6.1, 7.0

Pitfalls

• Space-optimized DP (lcs_length_space_optimized) only recovers the optimal value — you cannot traceback the actual alignment/subsequence from it; use the full O(mn) table when you need the traceback
• edit_distance_with_ops checks dp[i][j] == dp[i-1][j-1] + 1 for substitution before checking delete/insert — order matters when multiple operations tie, or the recovered path (though same cost) may differ from what you expect
• LCS and edit distance are related but not interchangeable: edit_distance >= len(s1) + len(s2) - 2 * lcs_length
• lis_length here is strictly increasing (arr[j] < arr[i]); switch to <= for non-decreasing subsequences
• O(n²) LIS is fine for a handful of time points; for genome-scale series use the O(n log n) patience-sorting variant with bisect.bisect_left

See Also

• algo-intro-memoization — top-down recursive DP with caching, the counterpart to this bottom-up approach
• algo-sequence-alignment — weighted alignment with gap penalties and substitution matrices (BLOSUM/PAM), of which edit distance is the uniform-cost special case
• algo-knapsack — another classic tabulation problem (0/1 and unbounded knapsack)
• bio-alignment-pairwise-alignment — production pairwise alignment via Biopython/parasail instead of hand-rolled DP