The Combinatorics of String Alignments: Reconsidering the Problem*

Abstract

In recent work, Covington discusses the number of alignments of two strings. Thereby, Covington defines an alignment as “a way of pairing up elements of two strings, optionally skipping some but preserving the order”. This definition has drawbacks as it excludes many relevant situations. In this work, we specify the notion of an alignment so that many linguistically interesting situations are covered. To this end, we define an alignment in an abstract manner as a set of pairs and then define three properties on such sets. Secondly, we specify the numbers of possibilities of aligning two strings in each case.

Notes

¹We take the term “string” in a general sense, see below. This is an innocuous assumption.

²Obtaining a goodness score is often simple. For example, in sequence alignment algorithms the goodness of an alignment is usually measured in terms of the number of exact matchings, mismatches, etc. In unsupervised alignment algorithms goodness is usually measured with reference to other observed string pairs, relying on simple count statistics.

³The inclined reader may note that a string alignment (in our sense) corresponds to the edge relation of a bipartite graph whose vertex set is a union of two disjoint sets of sizes m and n, respectively, so that the present analysis can also be interpreted in “graph theoretic” terms.

⁴Our analysis suggests another interpretation, besides the given one. The number denotes the number of complete matchings in a bipartite graph.

⁵Another possible derivation would be as follows. For each of the k possible matches there are possibilities how these can occur, in the given order. Moreover, there are k! permutations of the set [k], which account for all possible orders.

⁶For those numbers involving factors solely, this is not surprising as takes on its maximal value when n =  and is decreasing for both smaller and larger values.

⁷For example, Covington (2004) considers the case of monotonicity and one-to-one-ness – he calls this situation “a different middle set” – for which the formula can be derived in a similar manner as shown in Theorem 6.