Multiple Sequence Alignment as a Facility Location Problem^{1}

Winfried Just and Gianluca Della Vedova

Department of Mathematics, Ohio University, Athens, Ohio 45701, U.S.A. Dipartimento di Informatica, Sistemistica e Comunicazione, Universitá degli Studi di Milano - Bicocca, 20126 Milano, Italy

        e-mail: just@math.ohiou.edu, dellavedova@disco.unimib.it

Abstract. A connection is made between certain multiple sequence alignment problems and facility location problems, and the existence of a PTAS (polynomial time approximation scheme) for these problems is shown. Moreover, it is shown that multiple sequence alignment with SP-score and fixed gap penalties is MAX SNP-hard.

Key words: multiple sequence alignment, SP-score, Space-L Alignment problem, Switchboard Location problem, PTAS, smooth polynomial programming

1 Introduction

Recent advances in the availability of biological data (i.e. DNA, RNA or protein) has led to tremendous improvements in Molecular Biology. This huge amount of data has also given a tremendous boost to a new field of Computer Science called Bioinformatics. Pattern matching is a basic tool in Molecular Biology, as sequence similarity usually implies homology and functional similarity of the proteins or genes encoded by such sequences. Another crucial application of sequence comparison are searches of biological databases. All known biological sequences are stored in huge databases (e.g. EMBL, Swiss-Prot), and all recent papers in Molecular Biology that report the discovery of a new sequence include a detailed comparison of the novel sequences with those stored in the publicly available databases.

Paper Submitted for PSCW

These facts reveal the importance of developing efficient algorithms for aligning a set of sequences. It is standard practice to represent biological sequences as sequences over a fixed alphabet (4 symbols for DNA and RNA sequences, 20 symbols for proteins). An alignment of a set S of sequences is basically a matrix where the rows correspond to the sequences in the set, possibly with some spaces inserted, and the cost of an alignment is the sum of the costs of all columns. The goal is to compute the alignment of S of minimum cost (or, in an equivalent formulation preferred by many biologists, maximum score). This general definition allows different specifications of the problem, according to the definition of cost of a column in the alignment we choose. In practice at least two definitions make sense, the first (called Tree Alignment) requires a tree whose node set is exactly S and where the cost of a column is the sum of the costs of the pairs of symbols of the two sequences that are adjacent in the tree. A particular case of this problem is called Star Alignment, which is the restriction to trees with exactly one internal node. The other definition (called SP-Alignment) will be the one studied in this paper and defines the cost of a column as the sum of all pairs of symbols in the column. Equivalently, the SP-score can be defined as the sum over the pairwise alignment scores of all induced alignments of pairs of the sequences. The pairwise alignment scores are defined as follows. Let Σ be a fixed alphabet and let Δ ∉ Σ denote the space symbol, then a scoring scheme is a symmetric scoring function d_{M} : (Σ ∪ Δ) × (Σ ∪ Δ) ↦ N together with specifications on how to handle gaps. A scoring function d_{M} can be conveniently represented by a scoring matrix M. The cost of a pair of symbols s_{1}, s_{2} under the scoring matrix M is d_{M}(s_{1}, s_{2}). A gap is a string of the form Δ^{i}. Most scoring schemes used in practice are affine, i.e., they specify a fixed gap opening penalty g (possibly 0) that is added to the score calculated according to d_{M} for each newly created gap in the alignment. In this context, the numbers d_{M}(s, Δ) for s ∈ Σ are called gap extension penalties. Note that if all gap extension penalties are zero, then we have a scoring scheme with fixed gap penalties. If d_{M}(s, Δ) > 0 for all s ∈ Σ, then we will say that the scoring scheme specifies strictly positive gap extension penalties.

1The second author was supported by MURST grant ”Bioinformatica e ricerca genomica.”

Both Tree Alignment and SP-Alignment problems have been proved to be NP-hard by Wang and Jiang [WJ94]. Hence reasearch has focused on heuristic algorithms or approximation algorithms for such problems and on finding restrictions that are efficiently solvable. A restriction which has a natural interpretation is the one where the scoring function is a metric. For this restriction some approximation algorithms with guaranteed 2−o(1) error ratio have been described [G93, P92, BLP97]. Moreover, optimal alignments in actual biological sequences tend to have relatively few gaps [W93, F93, BCG93, PA92], but unfortunately even in such restricted cases the SP-Alignment problem is still NP-hard [BD00, J99]. In [J99], several such modifications of the SP-Alignment problem were studied. In the Gap-0 Alignment problem, spaces may be inserted at the beginning and at the end of sequences, but not between characters from Σ, and the Gap-0-1 Alignment problem is the restriction of Gap-0 Alignment where at most one space can be inserted in each sequence. It turns out that SP-Alignment, Gap-0 Alignment and Gap-0-1 Alignment problems are all NPhard for practically every affine scoring scheme with strictly positive gap extension penalties used by molecular biologists [J99]. This leaves open the case of other ways of calculating the gap penalties that are sometimes used in Molecular Biology. In particular, this leaves open the interesting case of fixed gap penalties, where all gaps are penalized equally, no matter where they occur and how long they are.

Multiple Sequence Alignment as a Facility Location Problem

Moreover, it had been shown in [J99] that for some scoring matrix M the three problems mentioned above are MAX SNP-hard. The scoring matrix M used in the the latter result does not penalize all character mismatches, and thus is not metric. In [JKL99], Jiang et al. ask whether a particular restriction of the SP-Alignment problem (the case of metric scoring matrix) has a polynomial time approximation scheme (PTAS), that is, there exists a polynomial time approximation algorithm for any fixed constant guaranteed error ratio. In [LMW99] a related question has been answered positively by showing that the Star-c-Alignment Problem (where the number of gaps in the pairwise alignment between any given sequence and the median sequence is bounded by a constant c) with Hamming distance admits a PTAS. In our paper we show that a different restriction of the problem admits a PTAS. More precisely, we show that a PTAS exists if the total number of spaces that can be inserted into each sequence is bounded and the ratio of the costs between each pairwise alignment is in a fixed interval. Our results trivially hold also for Gap-0-1 Alignment.

Moreover, we will show that at least for some scoring scheme with fixed gap penalty, the Gap-0 Alignment and the SP-Alignment problems are MAX SNP-hard. Since the optimal alignment in the example that yields the latter result contains only one space in each sequence, the requirement of bounded cost ratio cannot be dropped from the construction of the PTAS we describe in the paper.

2 Preliminaries

Let Σ be a finite alphabet, let Δ ∉ Σ be the space symbol, let d_{M} : (Σ ∪ Δ) × (Σ ∪ Δ) → N be a function called scoring function, and let g be a nonnegative integer constant called gap opening penalty. The symbol α(M) will denote the maximum value d_{M}(a_{1}, a_{2}) between two different symbols a_{1}, a_{2} ∈ Σ ∪ {Δ}. Given a sequence a over Σ ∪ {Δ}, the symbol a[i] will denote the i-th character of a and |a| will denote the length n of a sequence a = a[1], …, a[n]. Then given two sequences s_{1} = s_{1}[1], …, s_{1}[m], s_{2} = s_{2}[1], …, s_{2}[m] of m symbols over (Σ ∪ Δ), the cost of aligning s_{1} and s_{2} is d_{M}(s_{1}, s_{2}) = g(G_{1} + G_{2}) + ∑_{i=1}^{m} d_{M}(s_{1}[i], s_{2}[i]), where G_{j} is the number of gaps (consecutive runs of space symbols) in s_{j}. Given a k-tuple < t_{1}, …, t_{k} > of sequences over the alphabet Σ ∪ {Δ}, a multiple alignment is a ktuple < at_{1}, …, at_{k} > of equal-length sequences (where at_{i} stands for aligned t_{i}) over the alphabet Σ ∪ {Δ} such that each at_{i} can be obtained from t_{i} by inserting some space symbols into the sequences without altering the order of symbols of t_{i}. Given two equal-length sequences at_{1}, at_{2}, their pairwise alignment is the pair of sequences bt_{1}, bt_{2} that is obtained from at_{1}, at_{2} by removing all columns containing only Δs. If L is a nonnegative integer, by d_{M,L}^{opt}(t_{1}, t_{2}) we will denote the minimum cost among all pairwise alignments of < t_{1}, t_{2} > that insert at most L spaces into each of the sequences t_{1}, t_{2}. The SP-Alignment problem for a given scoring scheme (d_{M}, g) is to find the multiple alignment < at_{1}, …, at_{k} > that minimizes SP (< at_{1}, … at_{k} >) = ∑_{1≤i<j≤k} d(bt_{i}, bt_{j}) among all possible multiple alignments of < t_{1}, …, t_{k} >.

Here we will study a restriction of SP-Alignment that captures to some extent the pattern of space insertions observed in real biomolecular sequences and is different from the restrictions studied in [J99]. A space-L alignment A of a k-tuple < t_{1}, …, t_{k} > of sequences is an alignment < at_{1}, …, at_{k} > of < t_{1}, …, t_{k} > such that |at_{i}| ≤ |t_{i}| + L for each sequence t_{i}. Note that space-L-alignments exist only if the length of the shortest of these sequences is at least n − L, where n is the length of the longest among the sequences t_{1}, …, t_{k}. Please also note that there are no restrictions about where the space symbols can be inserted. The Space-L Multiple Alignment problem asks to find, for a k-tuple of sequences < t_{1}, …, t_{k} > and a scoring scheme (d_{M}, g), a space-L multiple alignment that minimizes the SP-score with respect to (d_{M}, g). Given an instance I =<< t_{1}, …, t_{k} >, (d_{M}, g) > of the Space-L Multiple Alignment problem we define the variability of I, denoted by v(I), as

v(I) = max\{\frac{nα(M) + Lg}{d_{M,L}^{opt}(t_{i}, t_{j})} : 1 ≤ i < j ≤ k\},

Please note that the value v(I) of the instance I can be computed in polynomial time. The Space-L Multiple Alignment(σ) problem is the restriction of the Space-L Multiple Alignment problem to instances I with v(I) ≤ σ.

A few comments are in order. The most common multiple alignment problem in Molecular Biology is the alignment of homologous protein sequences from different species. For a pair < t_{i}, t_{j} > of such sequences, < a(i, j)t_{i}, a(i, j)t_{j} > will be small only if the sequences are very similar, which usually happens only if the two species of origin have a relatively recent (in the timescale of evolution) common ancestor, and will be close to the average distance of random sequences if the species diverged a long time ago, or if the optimal alignment requires more than L spaces. For scoring matrices used in practice, the average distance of random sequences is usually a number of about the same order of magnitude as nα(M). The algorithms used in practice for multiple sequence alignment tend to perform well if all sequences are closely related to each other, while our first theorem covers one of the cases that are difficult in practice and quite common, namely the case where none of the sequences are closely related to each other.

3 The PTAS

The main results of this section is the following:

Theorem 1 Let σ be a constant. Then the Space-L Multiple Alignment(σ) problem has a polynomial time approximation scheme.

Note that in the above theorem, the scoring scheme (d_{M}, g) is considered part of the input, thus the theorem works for all affine scoring schemes, no matter whether the scoring function is a metric and the gap penalties are fixed or variable. This does not contradict the results about MAX SNP-hardness from [J99] though, since the variability of the instances used to obtain the latter results was not bounded.

Theorem 1 will be proved by reformulating it as a kind of facility location problem. To see the connection, suppose a communication network is to be set up in a country that consists of k regions. In each region, there should be one switchboard of the network, and each switchboard is to be connected by expensive, high quality cable to every other switchboard. If in each region there are several possible locations for the switchboard that are equally good for the operation of the network within this region, then the locations of switchboards should be chosen in such a way as to minimize overall cost of cable between them. The question of choosing optimal locations for the switchboards can then be formalized as follows. The Switchboard Location problem has as instance some disjoint sets R_{1}, …, R_{k} called regions, as well as a distance function d between all pairs of points x_{i}, x_{j} in R_{1}∪⋯∪R_{k}. The distance function gives strictly positive values whenever the two points are distinct. A feasible solution is a k-tuple < x_{1} …, x_{k} > of points such that x_{i} ∈ R_{i} for 1 ≤ i ≤ k. The problem asks for a feasible solution that minimizes ∑_{1≤i<j≤k} d(x_{i}, x_{j}).

While facility location problems with objective functions similar to those of Switchboard Location have been studied for regions of the real line (see e.g. [AH97], [T94]), we are not aware of any published results concerning the general formulation of Switchboard Location given above.

We will discuss later how instances of Space-L Alignment(σ) can be mapped to suitable instances of Switchboard Location in order to have a (1 + ϵ) approximation algorithm. But first we have to introduce a restriction of Switchboard Location similar to the one introduced for Space-L Alignment. Let I = {R_{1}, …, R_{k}, d} be an instance of the Switchboard Location problem. We define the spread s(I) of I as

s(I) = \frac{max\{d(x_{i}, x_{j}) : 1 ≤ i < j ≤ k, x_{i} ∈ R_{i}, x_{j} ∈ R_{j}\}}{min\{d(x_{i}, x_{j}) : 1 ≤ i < j ≤ k, x_{i} ∈ R_{i}, x_{j} ∈ R_{j}\}}.

It is immediate from the definition that s(i) ≥ 1. For any pair of constants P, σ, the Switchboard Location_{P} (σ) problem is the Switchboard Location problem restricted to instances of spread at most σ and where each region contains at most P points.

Theorem 2 Let P, σ be two constants. Then the Switchboard Location_{P} (σ) problem admits a PTAS.

Proof. The PTAS for Switchboard Location is based on the smooth polynomial programming technique of Arora et. al [AKK99]. We will briefly recall the relevant material from those papers. A c-smooth polynomial integer program (or PIP) is a problem of the form

minimize p_{0}(x_{1}, …, x_{n})
subject to l_{j} ≤ p_{i}(x_{1}, …, x_{n}) ≤ u_{j}
x_{i} ∈ {0, 1} for i = {1, …, n}

(1)

where each p_{j} is an n-variate polynomial of maximum degree d, and each coefficient of each degree ℓ monomial (term) has an absolute value of at most c · n^{d−ℓ}.

The fundamental result that we will use, Theorem 1.10 of [AKK99], asserts that, for each δ > 0, there exists an approximation algorithm running in time O(n^{\frac{1}{δ^{2}}} ) that computes a 0/1 assignment < y_{1}, …, y_{n} > to the variables x_{i} of a c-smooth PIP such that, for n-variate degree-d polynomials, the value of p_{0}(y_{1}, …, y_{n}) is within an additive error is at most δn^{d} of minimum for 0/1 solutions that satisfy all constraints p_{1}, …, p_{m}, and such that < y_{1}, …, y_{n} > satisfies each linear constraint within an additive error of O(δ\sqrt{n log n}).

Now let σ be a fixed constant, and suppose we have an instance I of the Switchboard Location_{P} (σ) problem, where {R_{i} : 1 ≤ i ≤ k} are the regions of I, and R_{i} = {x_{i,j} : 1 ≤ j ≤ P }. (Since one can always add dummy points to the regions, we do not lose generality by assuming the regions to be exactly of cardinality P.) Let D be the value min{d(x_{i,j}, x_{h,ℓ}) : 1 ≤ i < h ≤ k, 1 ≤ j, ℓ ≤ P }. Now we can formulate the Switchboard Location problem as a PIP:

minimize ∑_{1≤h<i≤k, 1≤j,ℓ≤k} \frac{d(x_{i,j},x_{h,ℓ})}{D}y_{i,j}y_{h,ℓ}
subject to ∑_{j} ky_{i,j} = k  i = 1, …, k
y_{i,j} ∈ {0, 1}  i = 1, …, k; j = 1, …, P

(2)

Please note that the total number of variables is at most kP. Since s(I) ≤ σ, all coefficients of the objective functions are between 1 and σ. Thus the PIP is σ-smooth.

Now suppose we want to find a solution to the Switchboard Location problem that is within a factor of (1 + ϵ) of minimum. Setting δ = \frac{ϵ}{2P^{2}} , and running the algorithm of [AKK99] on the PIP defined above, we find a 0/1 solution that satisfies all constraints within an additive error of O(δ\sqrt{kP log kP}). Since for 0/1 solutions the left hand sides of our side constraints are multiples of k; for sufficiently large k we can assume that these side constraints are satisfied exactly. But then for each region R_{i}, exactly one of the numbers y_{i,j} is equal to 1. Thus the corresponding x_{i,j}’s form a feasible solution of instance I of the Switchboard Location problem, and the sum of the distances is within an additive error of Dϵ\binom{k}{2}. By the choice of D, the minimum value for the sum of all distances in any feasible solution of instance I of the Switchboard Location problem cannot be less than D\binom{k}{2}, and thus we have found, in polynomial time, an approximation within a factor of (1 + ϵ). □

Now let us show how Theorem 2 implies Theorem 1. Suppose we are given an instance I =<< t_{1}, …, t_{k} >, (d_{M}, g) > of the Space-L Alignment(σ) problem, and let ϵ > 0. We want to find a space-L multiple alignment of these sequences that scores within (1 + ϵ) of optimum. Let N = ⌈\frac{4Lσ}{ϵ}⌉ and note that N is a constant. Let n be the length of the longest among the sequences t_{1}, …, t_{k}, and let K = ⌈2N + \frac{gN}{α(M)}⌉.

First assume that n ≤ K. In this case we let R_{i} be the set of all sequences x_{i,j} that are obtainable by inserting L spaces into t_{i} (at the beginning, end, or between symbols). This set contains at most \binom{K+L}{L} elements. Note that \binom{K+L}{L} is a constant that does not depend on the number of sequences k. Thus the family {R_{i} : 1 ≤ i ≤ k} together with the distances d(x_{i,j}, x_{i′,j′}) defined by the scoring scheme is an instance of the Switchboard Location problem where the cardinality of all regions is bounded by the constant \binom{K+L}{L}. Feasible solutions of the Switchboard Location problem are exactly all space-L alignments of our sequences, and the objective function of the Switchboard Location problem is exactly the SP-score of the alignment. Since the variability of the Space-L Alignment problem is bounded by σ, the spread of the corresponding Switchboard Location problem that we just constructed is also bounded by σ. Thus the PTAS for Switchboard Location\binom{K+L}{L}(σ) finds a solution within (1 + ϵ) of optimum.

Now assume that n > K. In this case we partition each sequence t_{i} into consecutive chunks < s_{i,h} : 1 ≤ h ≤ N >, where the length of each chunk differs from \frac{n}{N} by no more than 1. With each function f : {1, …, N +1} → N such that ∑_{1≤i≤N+1} f(i) ≤ L we associate a sequence t_{i,f} by inserting f(h) space symbols to the left of each chunk s_{i,h}. In other words,

t_{i,f} = Δ^{f(1)}s_{i,1}Δ^{f(2)}s_{i,2} … Δ^{f(N)}s_{i,N}Δ^{f(N+1)}

Now we let R_{i} be the set of all t_{i,f} for functions f : {1, …, N + 1} → N that satisfy ∑_{1≤i≤N+1} f(i) ≤ L. We run the approximation algorithm for Switchboard Location_{N+1}(σ) that finds a solution within (1 + \frac{ϵ}{3}) on the instance given by the k + 1-tuple < R_{1}, …, R_{k}, (d_{M}, g) >.

The algorithm returns a space-L multiple alignment < t_{1,f_{1}}, …, t_{k,f_{k}} > of the sequences < t_{1}, …, t_{k} >. It remains to show that the alignment < t_{1,f_{1}}, …, t_{k,f_{k}} > scores within (1 + ϵ) of optimum. Let < at_{1}, …, at_{k} > denote a space-L multiple alignment with optimal SP-score. For each i, let g_{i} : {1, …, N + 1} → N be the function such that for each 1 ≤ i ≤ k and 1 ≤ h ≤ N, g_{i} is equal to the number of spaces in at_{i} inserted immediately to the left of the chunk s_{i,h} or between characters of s_{i,h}. Instead of t_{i,g_{i}} we will write bt_{i}. Since bt_{i} ∈ R_{i} for each i, we have

SP (< t_{1,f_{1}}, …, t_{k,f_{k}} >) ≤ (1 + \frac{ϵ}{3})SP (< bt_{1}, …, bt_{k} >).

Since 1 + ϵ > (1 + ϵ/2)(1 + ϵ/3) whenever ϵ < 1, it now suffices to show that

SP (< bt_{1}, …, bt_{k} >) ≤ (1 + \frac{ϵ}{2})SP (< at_{1}, …, at_{k} >).

Let us split the sequences at_{i}, bt_{i} into N + 1 chunks at_{i,h}, bt_{i,h} for 1 ≤ h ≤ N + 1 where bt_{i,h} = Δ^{g_{i}(h)}s_{i,h}, s_{i,N+1} is the empty string, and |bt_{i,h}| = |at_{i,h}|, so that at_{i} = at_{i,1}at_{i,2} ⋯ at_{i,N+1} and bt_{i} = bt_{i,1}bt_{i,2} ⋯ bt_{i,N+1}. From the definition of g_{i}, whenever g_{i}(h) = g_{j}(h) = 0, the pairwise alignment < at_{i,h}, at_{j,h} > is the same as < bt_{i,h}, bt_{j,h} >. Since at most L spaces are inserted into each sequence t_{i}, and since the maximum penalty on each chunk (excluding the newly inserted spaces) is equal to the length of the chunk (i.e. at most \frac{n}{N} + 1) multiplied by α(M), and there are globally only L extra spaces, we get the inequality

d_{M}(bt_{i}, bt_{j}) ≤ d_{M}(at_{i}, at_{j}) + α(M)L(2 + \frac{n}{N}) + Lg.

Since n > 2N + \frac{gN}{α(M)} and thus α(M)\frac{Ln}{N} ≥ 2Lα(M) + Lg, we get

d_{M}(bt_{i}, bt_{j}) ≤ d_{M}(at_{i}, at_{j}) + α(M)n\frac{2L}{N}.

By the choice of N, the latter yields

d_{M}(bt_{i}, bt_{j}) ≤ d_{M}(at_{i}, at_{j}) + \frac{α(M)nϵ}{2σ}.

Since the variability of our instance was assumed to be at most σ, the inequality d_{M}(at_{i}, at_{j}) ≥ \frac{α(M)n}{σ} holds, and we get

d_{M}(bt_{i}, bt_{j}) ≤ d_{M}(at_{i}, at_{j})(1 + \frac{ϵ}{2}),

as required.

4 MAX SNP-hardness

The following theorem shows that the assumption of bounded variability cannot be simply dropped in Theorem 1.

Theorem 3 There exists a scoring scheme (d_{M}, g) with fixed gap penalties such that:

(a) For the scoring scheme (d_{M}, g) and for every L > 0 the Space-L Multiple Alignment problem is MAX SNP-hard.

(b) For the scoring scheme (d_{M}, g) the Gap-0 Alignment problem is MAX SNP-hard.

(c) For the scoring scheme (d_{M}, g), the SP-Alignment problem is MAX SNP-hard.

Here is the scoring scheme mentioned in the above theorem. The alphabet will be Σ = {A, C, T }, the gap opening penalty will be g = 2, and the scoring matrix M will be:

Δ A C T
Δ 0 0 0 0
A 0 0 0 1
C 0 0 0 0
T 0 1 0 0

Proof. We will prove Theorem 3 by reducing the Max Cut problem on cubic graphs (denoted by 3-Max Cut) to the respective multiple alignment problems. Recall that an instance of size k of the 3-Max Cut problem is a simple graph G =< V, E > such that |V | = k and each vertex of G has degree exactly 3. The problem is to find a partition of the set of vertices V into disjoint sets V_{0} and V_{1} such that the number of edges that connect a vertex in V_{0} with a vertex in V_{1}, i.e., the size of the cut determined by < V_{0}, V_{1} >, is as large as possible. It is well known that the 3-Max Cut problem is MAX SNP-hard [AK97]. For our purposes, it is most important to note that the latter implies that there exists a real ϵ > 0 such that no polynomial-time approximation algorithm can find a cut such that the number of edges that are NOT cut is within an additive constant of ϵk of minimum.

Given a cubic graph G =< V, E > with k vertices, we define a 2k-tuple t̄^{G} =< t_{1}, …, t_{2k} > of sequences as follows: Enumerate V = {v_{1}, …, v_{k}}, E = {e_{0}, …, e_{ℓ−1}}. Each sequence t_{i} will have length 2(k^{4} + ⌈αk⌉ℓ), where α is a constant that will be defined below. Intuitively speaking, for 1 ≤ i ≤ k, the sequence t_{i} will encode the vertex v_{i}. Edge e_{m} = {v_{i}, v_{h}} will be encoded by characters t_{h}[j], t_{i}[j], where j = 2(⌈αk⌉m+1), …, 2⌈αk⌉(m+1). More precisely, we define t_{i}[j], the j-th character in t_{i}, as follows. For 1 ≤ m ≤ ℓ, e_{m} = {v_{h}, v_{i}}, h < i, ⌈αk⌉m < j < ⌈αk⌉(m + 1) we put: t_{h}[2j] = A, t_{i}[2j] = T, and t_{p}[2j] = C for p ∉ {i, h}.

The sequence t_{k+i} will act as a “mirror image” of t_{i}. The purpose of mirror images is to neutralize the effects of unbalanced cuts on the scores of aligments. For 1 ≤ i ≤ k and ⌈αk⌉ℓ + ik^{3} < j < ⌈αk⌉ℓ + (i + 1)k^{3} we put: t_{i}[2j] = A, t_{k+i}[2j] = T, t_{p}[2j] = C for p ∉ {i, k + i}.

For all p, j, we let t_{p}[2j −1] = C. Let us illustrate this construction with a picture. We exhibit a situation where e_{m} = {v_{h}, v_{i}}.

t[2(⌈αk⌉m + 1)]  t[2⌈αk⌉ℓ + 2(h − 1)k^{3}] t[2⌈αk⌉ℓ + 2(i − 1)k^{3}] ↓  ↓  ↓ t_{h}: ... A C A C A ... A C A C A C ... C C C C C ... t_{i}:  ... T C T C T ... C C C C C C ... A C A C A ... t_{k+h}: ... C C C C C ... T C T C T C ... C C C C C ... t_{k+i}: ... C C C C C ... C C C C C C ... T C T C T ...

Let us define a “benchmark alignment” of the above sequences. We will define this alignment by partitioning the sequences into two sets L and R and inserting one space to the left of each sequence in L and one space to the right of each sequence in R. Let < V_{1}, V_{2} > be a cut of G. We will show how to associate a benchmark alignment to such cut. For each 1 ≤ i ≤ k we let t_{i} ∈ L iff t_{k+i} ∈ R. Moreover for each 1 ≤ i ≤ k we let t_{i} ∈ L iff v_{i} ∈ V_{1}.

Note that the score for the benchmark alignment is 4k^{2} + αkU, where U is the number of edges that are not in the cut < V_{1}, V_{2} >. Moreover, the benchmark alignment is a gap-0-1 alignment, and hence both a gap-0 alignment and a space-1 alignment.

We will show that there exists a fixed δ > 0 such that if an alignment a of the above sequences is found that scores within a factor of (1 + δ) of the benchmark alignment, then it will be possible to reconstruct, in polynomial time, from this alignment a partition of the vertex set that induces a cut whose size is within a additive constant of ϵk of maximum. Suppose we have any alignment a that scores within 1 + δ of our benchmark alignment, where δ is sufficiently small and will be determined later. Let us say that a sequence pair < t_{p}, t_{q} > is static in a if there is no space in the induced pairwise alignment < bt_{p}, bt_{q} >. Being static in a is easily seen to be an equivalence relation. Let T_{1} and T_{2} denote the two largest equivalence classes of the “static” relation, and let T_{3} denote the set of sequences that are neither in T_{1} nor in T_{2}. Note that none of the sequence pairs < t_{i}, t_{k+i} > can be static in a, otherwise the cost of the alignment of < t_{i}, t_{k+i} > is too large. Thus the size of T_{1} and T_{2} is at most k. Let |T_{1}| = k − k_{1}, |T_{2}| = k − k_{2}. Then |T_{3}| = k_{1} + k_{2}. Since each pair of sequences from different equivalence classes adds at least 4 to the SP-score of a, we have

SP (< at_{1}, …, at_{2k} >) ≥ 4((k − k_{1})(k − k_{2}) + (k − k_{1})(k_{1} + k_{2}) + (k − k_{2})(k_{1} + k_{2})) =

4(k^{2} + k_{1}k_{2} + k(k_{1} + k_{2}) − (k_{1} + k_{2})^{2}) = 4(k^{2} + k_{1}k_{2} + (k − |T_{3}|)|T_{3}|).

Thus the numbers k_{1} and k_{2} must be such that k_{1}k_{2}+(k−|T_{3}|)|T_{3}| < δk^{2}+δαkU, where U is the number of edges that are not cut by the partition used in the benchmark alignment. Note that U ≤ 3k. We will choose δ < \frac{ϵα}{100}. It follows that as long as α is sufficiently small, we can assume that |T_{3}| < k \frac{ϵ}{6}. Now let α, δ be as above, and let V_{i} be the set of all vertices such that t_{i} ∈ T_{i} for i ∈ {1, 2}. Consider the partition < V_{1}, V \V_{1} >. Let W be the number of edges of G that are not cut by < V_{1}, V \V_{1} >. Note that this number differs from the number Z of edges {v_{i}, v_{j}} such that < t_{i}, t_{j} > is static by at most 3|T_{3}|, since every edge in the difference must have an endpoint in T_{3} and the degree of the graph is 3. If the SP-score of the alignment is within a factor of (1 + δ) of that of the benchmark alignment, then we have:

4k^{2} + αkW ≤ 4k^{2} + αk(Z + k \frac{ϵ}{2}) ≤ (1 + δ)(4k^{2} + αkU) + α\frac{ϵ}{2}k^{2}.

By the choice of δ and since U ≤ 3k, we get

αkW − αkU < 4δk^{2} + δαkU + α\frac{ϵ}{2}k^{2}.

Assuming, as we may, that α ≤ 1, and noting that U ≤ 3k, our choice of δ gives:

W − U < 4\frac{ϵ}{100}k + 3\frac{ϵ}{100}αk + \frac{ϵ}{2}k < ϵk.

□

The following results on hardness of Switchboard Location problems are not covered by Theorem 3.

Theorem 4 For every constant σ > 1, the Switchboard Location_{2}(σ) problem is NPhard.

Proof. Let σ > 1. Since the number of instances of Switchboard Location_{2}(σ) increases with σ, we may without loss of generality assume that σ ≤ 2. We prove the theorem by reducing the Max-Cut problem to Switchboard Location_{2}(σ). Given a graph G =< V, E > with vertices V = {v_{1}, …, v_{k}}, construct a metric space X = {x_{1}, …, x_{k}, y_{1}, …, y_{k}} as follows: For i ≠ j, we let d(x_{i}, x_{j}) = d(y_{i}, y_{j}) = 1. If {v_{i}, v_{j}} ∈ E, then d(x_{i}, y_{j}) = σ; if {v_{i}, v_{j}} ∉ E, then d(x_{i}, y_{j}) = 1. (Note that for our choice of σ, the distance function is actually a metric.) For 1 ≤ i ≤ k, the region R_{i} is defined as {x_{i}, y_{i}}. This gives us an instance I of the Switchboard Location_{2}(σ) problem. Every solution x̄ of I induces a partition < V_{x}, V_{y} >, where V_{x} = {v_{i} : x_{i} ∈ x̄} and V_{y} = {v_{i} : y_{i} ∈ x̄}. If cx̄ denotes the size of the cut induced by the partition < V_{x}, V_{y} >, then the measure of x̄ is equal to \binom{k}{2} + (σ − 1)(|E| − cx̄), and the theorem follows from NP-hardness of the Max-Cut problem (see [GJ79]). □

Theorem 5 The Switchboard Location_{2} problem is MAX SNP-hard.

In view of our observation that Gap-0-1 Alignment is a special case of Switchboard Location, Theorem 5 is a corollary of Theorem 3(c) of [J99].

Acknowledgements

We thank Tao Jiang for helpful discussions about this paper and Arie Tamir for bringing references [AH97] and [T94] to our attention.

References

[AK97] P. Alimonti and V. Kann. Hardness of approximating problems on cubic graphs. CIAC 97, 288-298, volume 1203 of LNCS, 1997.

[AH97] E. M. Arkin and M. Hassin. Minimum diameter covering problems. Technical report, 1997.

[AKK99] S. Arora, D. Karger, and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of N P-Hard Problems. J. Computer and Systems Sci., 58, 193-210, 1999.

[BCG93] S. A. Benner, M. A. Cohen, and G. H. Gonnet. Empirical and Structural Models for Insertions and Deletions in the Divergent Evolution of Proteins. J. Mol. Biol. 229:1065-1082, 1993.

[BLP97] V. Bafna, E.L. Lawler, P.A. Pevzner, Approximation algorithms for multiple sequence alignment, Theoret. Comput. Sci., 182:233-244, 1997.

[BD00] P. Bonizzoni and G. Della Vedova. The complexity of multiple alignment with SP-score that is a metric. To appear in Theoretical Computer Science.

[F93] W. M. Fitch. Letter to the Editor: Commentary on the letter by Ward C. Wheeler. Mol. Biol. Evol. 10(3):713-714, 1993.

[GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman 1979.

[G93] D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds, Bull. Math. Biol. 55:141-154, 1993.

[JKL98] T. Jiang, P. Kearney, and M. Li. Orchestrating Quartets: Approximation and Data Correction. Proc. 39th IEEE Symp. on Found. of Comp. Science, 416-425, 1998.

[JKL99] T. Jiang, P. Kearney, and M. Li. Some Open Problems in Computational Molecular Biology. SIGACT News 30(3):43-49, 1999.

[J99] W. Just. Computational Complexity of Multiple Sequence Alignment with SP-Score. Submitted, 1999.

[LMW99] M. Li, B. Ma, L. Wang, Finding Similar Regions in Many Strings, Proc. 31st Symposium on the Theory of Computing (STOC), 473-482, 1999.

[PA92] S. Pascarella and P. Argos. Analysis of Insertions/Deletions in Protein Structures. J. Mol. Biol. 224:461-471, 1992.

[P92] P.A. Pevzner, Multiple alignment, communication cost, and graph matchings, SIAM J. Appl. Math, 52:1763-1779, 1992.

[T94] A. Tamir. A distance constrained p-facility location problem on the real line. Mathematical Programming, 66:201-204, 1994.

[WJ94] L. Wang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337-348, 1994.

[W93] W. C. Wheeler. Letter to the Editor: The Triangle Inequality and character analysis. Mol. Biol. Evol. 10(3):707-712, 1993.