Vectorize pairwise edit distance computation
I do not think vectorisation to buy you anything "in the upper levels".
My guess is the statement little use due to data dependencies is true even more than for 
parallel computing in general.
With SciPy/NumPy I'm out of my depth; drawing on Syncrossus levenshtein.py.
I'd need a better motivation for the distance function - I guess the minimum requirement being triangle inequality
Shot from the hip using set.symmetric_difference() as food for thought:

import numpy as np


def replacement_cost(s1, s2):
    return len(set(s1).symmetric_difference(s2))


def edit_distance(seq1, seq2):
    """ return edit distance between two list-like sequences of sequences
        Args:
            seq1, seq2: subscriptable objects compatible with len()
                containing objects comparable with the `==` operator.
    """
    m = len(seq1)
    n = len(seq2)
    dp = np.zeros(shape=(m, n))
    dp[0, :] = range(0, n)
    dp[:, 0] = range(0, m)

    for i in range(1, m):
        for j in range(1, n):
            cost = 0 if seq1[i] == seq2[j] \
                     else replacement_cost(seq1[i], seq2[j])
            dp[i][j] = min(dp[i][j - 1] + len(seq2[j - 1]),  # Insert
                           dp[i - 1][j] + len(seq1[i - 1]),  # Remove
                           dp[i - 1][j - 1] + cost)          # Replace
    return dp[m-1][n-1]