# Algorithms for normalized multiple sequence alignments

Eloi Araujo${}^{1,}\qquad$111Corresponding author Diego P. Rubert1
Luiz Rozante${}^{2}\qquad$ Fábio V. Martinez1
1 Faculdade de Computação
Universidade Federal de Mato Grosso do Sul
Brazil
2 Centro de Matemática, Computação e Cognição
Universidade Federal do ABC
Brazil

###### Abstract

Sequence alignment supports numerous tasks in bioinformatics, natural language
processing, pattern recognition, social sciences, and other fields. While the
alignment of two sequences may be performed swiftly in many applications, the
simultaneous alignment of multiple sequences proved to be naturally more
intricate. Although most multiple sequence alignment (MSA) formulations are
NP-hard, several approaches have been developed, as they can outperform
pairwise alignment methods or are necessary for some applications. Taking into
account not only similarities but also the lengths of the compared sequences
(i.e. normalization) can provide better alignment results than both
unnormalized or post-normalized approaches. While some normalized methods have
been developed for pairwise sequence alignment, none have been proposed for
MSA. This work is a first effort towards the development of normalized methods
for MSA. We discuss multiple aspects of normalized multiple sequence alignment
(NMSA). We define three new criteria for computing normalized scores when
aligning multiple sequences, showing the NP-hardness and exact algorithms for
solving the NMSA using those criteria. In addition, we provide approximation
algorithms for MSA and NMSA for some classes of scoring matrices.

Keywords: Multiple sequence alignment ($\mathbf{MSA}$), Normalized multiple
sequence alignment ($\mathbf{NMSA}$), Algorithms and complexity

##  1 Introduction

Sequence alignment lies at the foundation of bioinformatics. Several
procedures rely on alignment methods for a range of distinct purposes, such as
detection of sequence homology, secondary structure prediction, phylogenetic
analysis, identification of conserved motifs or genome assembly. On the other
hand, alignment techniques have also been reshaped and found applications in
other fields, such as natural language processing, pattern recognition, or
social sciences [AT00, AG97, BL02, MV93].

Given its range of applications in bioinformatics, extensive efforts have been
made to improve existing or developing novel methods for sequence alignment.
The simpler ones compare a pair of sequences in polynomial time on their
lengths, usually trying to find editing operations (insertions, deletions, and
substitutions of symbols) that transform one sequence into another while
maximizing or minimizing some objective function called edit distance [HAR09].
This concept can naturally be generalized to align multiple sequences
[WLXZ15], adding another new layer of algorithmic complexity, though. In this
case, most multiple sequence alignment (MSA) formulations lead to NP-hard
problems [Eli06]. Nevertheless, a variety of methods suitable for aligning
multiple sequences have been developed, as they can outperform pairwise
alignment methods on tasks such as phylogenetic inference [OR06], secondary
structure prediction [CB99] or identification of conserved regions [SWD+11].

In order to overcome the cost of exact solutions, a number of MSA heuristics
have been developed in recent years, most of them using the so-called
progressive or iterative methods [HTHI95, SH14, TPP99, WOHN06]. Experimental
data suggest that the robustness and accuracy of heuristics can still be
improved, however [WLXZ15].

Most approaches for pairwise sequence alignment define edit distances as
absolute values, lacking some normalization that would result in edit
distances relative to the lengths of the sequences. However, some applications
may require sequence lengths to be taken into account. For instance, a
difference of one symbol between sequences of length 5 is more significant
than between sequences of length 1000. In addition, experiments suggest that
normalized edit distances can provide better results than both unnormalized or
post-normalized edit distances [MV93]. While normalized edit distances have
been developed for pairwise sequence alignment [AE99, MV93], none have been
proposed for MSA to the best of our knowledge.

In this work, we propose exact and approximation algorithms for normalized MSA
(NMSA). This is a first step towards the development of methods that take into
account the lengths of sequences for computing edit distances when multiple
sequences are compared. The remainder of this paper is organized as follows.
Section 2 introduces concepts related to sequence alignment and presents
normalized scores for NMSA, followed by the complexity analysis of NMSA using
those scores in Section 3. Next, Sections 4 and 5 describe exact and
approximation algorithms, respectively. Section 6 closes the paper with the
conclusion and prospects for future work.

##  2 Preliminaries

An _alphabet_ $\Sigma$ is a finite non-empty set of _symbols_. A finite
sequence $s$ with $n$ symbols in $\Sigma$ is seen as $s(1)\cdots s(n)$. We say
that the _length_ of $s$, denoted by $\left|s\right|$, is $n$. The sequence
$s(p)\cdots s(q)$, with $1\leq p\leq q\leq n$, is denoted by $s(p\\!:\\!q)$.
If $p>q$, $s(p\\!:\\!q)$ is the _empty_ sequence which length is equal to zero
and it is denoted by $\varepsilon$. We denote the sequence resulting from the
concatenation of sequences $s$ and $t$ by $s\cdot t=st$. A sequence of $n$
symbols $\mathtt{a}$ is denoted by $\mathtt{a}^{n}$. A $k$-tuple $S$ over
$\Sigma^{*}$ is called a _$k$ -sequence_ and we write $s_{1},\ldots,s_{k}$ to
refer to $S$, where $s_{i}$ is the $i$-th sequence in $S$. We denote
$S=\emptyset$ if every sequence of $S$ is a empty sequence.

Let $\Sigma_{\texttt{-}}:=\Sigma\cup\\{\texttt{-}\\}$, where
$\texttt{-}\not\in\Sigma$ and the symbol - is called a _space_. Let
$S=s_{1},\ldots,s_{k}$ be a $k$-sequence. An _alignment_ of $S$ is a $k$-tuple
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ over $\Sigma_{\texttt{-}}^{*}$,
where

  1. ($a$)

each sequence $s^{\prime}_{h}$ is obtained by inserting spaces in $s_{h}$;

  2. ($b$)

$\left|s^{\prime}_{h}\right|=\left|s^{\prime}_{i}\right|$ for each pair $h,i$,
with $1\leq h,i\leq k$;

  3. ($c$)

there is no $j$ in $\\{1,\ldots,k\\}$ such that
$s^{\prime}_{1}(j)=\ldots=s^{\prime}_{k}(j)=\texttt{-}$.

Notice that alignments, which are $k$-tuples over $\Sigma_{\texttt{-}}^{*}$,
are written enclosed by square brackets “$[~{}]$”. The sequence
$A(j)=[s^{\prime}_{1}(j),\ldots,s^{\prime}_{k}(j)]\in\Sigma_{\texttt{-}}^{k}$
is the _column $j$_ of the alignment
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ and $A[j_{1}\\!:\\!j_{2}]$ is the
alignment defined by the columns $j_{1},j_{1}+1,\ldots,j_{2}$ of $A$. We say
that the pair $[s^{\prime}_{h}(j),s^{\prime}_{i}(j)]$ _aligns_ in $A$ or,
simply, that $s^{\prime}_{h}(j)$ and $s^{\prime}_{i}(j)$ are _aligned_ in $A$,
and $\left|A\right|=\left|s^{\prime}_{i}\right|$ is the _length_ of the
alignment $A$. It is easy to check that
$\max_{i}\\{\left|s_{i}\right|\\}\leq\left|A\right|\leq\sum_{i}\left|s_{i}\right|$.
We denote by $\mathcal{A}_{S}$ the set of all alignments of $S$.

An alignment can be used to represent _editing operations_ of _insertions_ ,
_deletions_ and _substitutions_ of symbols in sequences, where the symbol -
represents insertions or deletions. An alignment can also be represented in
the matrix format by placing one sequence above another. Thus, the alignments

$\displaystyle[\mathtt{a}\mathtt{a}\mathtt{a}\texttt{-},\mathtt{a}\mathtt{b}\texttt{-}\texttt{-},\texttt{-}\mathtt{c}\mathtt{a}\mathtt{c}]$
and
$\displaystyle[\texttt{-}\mathtt{a}\mathtt{a}\mathtt{a}\texttt{-},\mathtt{a}\mathtt{b}\texttt{-}\texttt{-}\texttt{-},\texttt{-}\mathtt{c}\mathtt{a}\texttt{-}\mathtt{c}]$

of 3-sequence
$\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{b},\mathtt{c}\mathtt{a}\mathtt{c}$
can be represented respectively as

$\displaystyle\left[\begin{array}[]{cccc}\mathtt{a}&\mathtt{a}&\mathtt{a}&\texttt{-}\\\
\mathtt{a}&\mathtt{b}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\mathtt{c}&\mathtt{a}&\mathtt{c}\end{array}\right]$ and
$\displaystyle\left[\begin{array}[]{ccccc}\texttt{-}&\mathtt{a}&\mathtt{a}&\mathtt{a}&\texttt{-}\\\
\mathtt{a}&\mathtt{b}&\texttt{-}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\mathtt{c}&\mathtt{a}&\texttt{-}&\mathtt{c}\end{array}\right].$

Let $I=\\{i_{1},\ldots,i_{m}\\}\subseteq\\{1,\ldots,k\\}$ be a set of indices
such that $i_{1}<\cdots<i_{m}$ and let
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ be an alignment of a $k$-sequence
$S=s_{1},\ldots,s_{k}$. We write $S_{I}$ to denote the $m$-sequence
$s_{i_{1}},\ldots,s_{i_{m}}$. The alignment of $S_{I}$ _induced_ by $A$ is the
alignment $A_{I}$ obtained from the alignment $A$, considering only the
corresponding sequences in $S_{I}$ and, from the resulting structure, removing
columns where all symbols are -. In the previous example, being
$A=[\mathtt{a}\mathtt{a}\mathtt{a}\texttt{-},\mathtt{a}\mathtt{b}\texttt{-}\texttt{-},\texttt{-}\mathtt{c}\mathtt{a}\mathtt{c}]$
an alignment of
$\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{b},\mathtt{c}\mathtt{a}\mathtt{c}$,
we have

$\left[\begin{array}[]{ccc}\mathtt{a}&\mathtt{a}&\mathtt{a}\\\
\mathtt{a}&\mathtt{b}&\texttt{-}\end{array}\right]$

is an alignment of $\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{a}\mathtt{b}$
induced by $A$.

A _$k$ -vector_ $\vec{\jmath}=[j_{1},\ldots,j_{k}]$ is a $k$-tuple, where
$j_{i}\in\mathbb{N}=\\{0,1,2,\ldots\\}$. We say that $j_{i}$ is the $i$-th
element of $\vec{\jmath}$. The $k$-vector $\vec{0}$ is such that all its
elements are zero. If $\vec{\jmath}$ and $\vec{h}$ are $k$-vectors, we write
$\vec{\jmath}\leq\vec{h}$ if $j_{i}\leq h_{i}$ for each $i$; and
$\vec{\jmath}<\vec{h}$ if $\vec{\jmath}\leq\vec{h}$ and
$\vec{\jmath}\not=\vec{h}$. A sequence of $k$-vectors
$\vec{\jmath}_{1},\vec{\jmath}_{2},\ldots$ is in _topological order_ if
$\vec{\jmath}_{i}<\vec{\jmath}_{h}$ implies $i<h$. Given two $k$-vectors, say
$\vec{a}=[a_{1},a_{2}\ldots a_{k}]$ $\vec{b}=[b_{1},b_{2}\ldots b_{k}]$, we
say that $\vec{a}$ _precedes_ $\vec{b}$ when there exists $l\in\mathbb{N}$
such that $a_{i}=b_{i}$ for each $i>l$ and $a_{l}<b_{l}$. A sequence of
$k$-vectors $\vec{\jmath}_{1},\vec{\jmath}_{2},\ldots$ is in _lexicographical
order_ if $\vec{\jmath}_{i}$ precedes $\vec{\jmath}_{h}$ for each $i<h$.
Clearly, a lexicographical order is a special case of topological order.

Consider $S=s_{1},\ldots,s_{k}$ a $k$-sequence with $n_{i}=\left|s_{i}\right|$
for each $i$ and we call $\vec{n}=[n_{1},\ldots,n_{k}]$ the _length of $S$_.
Let $V_{\vec{n}}=\\{\vec{\jmath}:\vec{\jmath}\leq\vec{n}\\}$. Therefore,
$\left|V_{\vec{n}}\right|=\prod_{i}(\left|s_{i}\right|+1)$ which implies that
if $n_{i}=n$ for all $i$, then $\left|V_{\vec{n}}\right|=(n+1)^{k}$. Define
$S(\vec{\jmath})=s_{1}(j_{1}),\ldots,s_{k}(j_{k})$ a _column_ $\vec{\jmath}$
in $S$ and we say that
$S(1\\!:\\!\vec{\jmath})=s_{1}(1\\!:\\!j_{1}),\ldots,s_{k}(1\\!:\\!j_{k})$ is
the _prefix of $S$ ending in $\vec{\jmath}$_. Thus, $S=S(1\\!:\\!\vec{n})$.
Besides that, if $A$ is an alignment and $\vec{j}=[j,j,\ldots,j]$, then
$A[\vec{j}]=A(j)$.

Denote by $\mathcal{B}^{{k}}$ the set of $k$-vectors $[b_{1},\ldots,b_{k}]$,
where $b_{i}\in\\{0,1\\}$ for each $i$. Now, for $\vec{b}\leq\vec{j}$, where
$\vec{j}=[j_{1},\ldots,j_{k}]$, define

$\vec{b}\cdot S(\vec{j})=[x_{1},\ldots,x_{k}]\in\Sigma_{\texttt{-}}^{k}\,,$

such that

$x_{i}=\left\\{\begin{array}[]{ll}s_{i}(j_{i})\,,&\mbox{if $b_{i}=1$}\\\
\texttt{-}\,,&\mbox{otherwise}\,.\end{array}\right.$

Therefore, given an alignment $A$ of $S(1\\!:\\!\vec{n})$, there exists
$\vec{b}\in\mathcal{B}^{{k}}$, with $\vec{b}\leq\vec{n}$, such that
$A(\left|A\right|)=\vec{b}\cdot S(\vec{n})$. In this case, notice that
$b_{i}=1$ if and only if $s_{i}(n_{i})$ is in the $i$-th row of the last
column of $A$ and we say that $\vec{b}$ _defines_ the column $\left|A\right|$
of alignment $A$. For $\vec{b}\leq\vec{\jmath}$, we also define the operation

$\vec{\jmath}-\vec{b}=[\jmath_{1}-b_{1},\ldots,\jmath_{k}-b_{k}]\,.$

Notice that $\left|\mathcal{B}_{k}\right|=2^{k}$. Figure 1 shows an example of
alignment using vectors to define columns and operations.

$\displaystyle
A=\left[\begin{array}[]{ccccc}\mathtt{a}&\mathtt{b}&\mathtt{c}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\mathtt{b}&\mathtt{c}&\mathtt{a}&\texttt{-}\\\
\mathtt{b}&\texttt{-}&\mathtt{b}&\texttt{-}&\mathtt{a}\\\
\mathtt{a}&\mathtt{a}&\mathtt{a}&\mathtt{a}&\mathtt{a}\\\
\mathtt{c}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}\end{array}\right]$
$\displaystyle\Rightarrow$ $\displaystyle\left[\begin{array}[]{c}\\\ \\\
A[1:4]\\\ \\\ \\\ \end{array}\right]\left[\begin{array}[]{c}\\\ \\\
\left[0,0,1,1,0\right]\cdot S(1:[3,3,3,5,1])\\\ \\\ \\\ \end{array}\right]$
Figure 1: The length of alignment $A$ of
$S=\mathtt{a}\mathtt{b}\mathtt{c},\mathtt{b}\mathtt{c}\mathtt{a},\mathtt{b}\mathtt{b}\mathtt{a},\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{c}$
is
$\vec{n}=[\left|\mathtt{a}\mathtt{b}\mathtt{c}\right|,\left|\mathtt{b}\mathtt{c}\mathtt{a}\right|,\left|\mathtt{b}\mathtt{b}\mathtt{a}\right|,\left|\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}\right|,\left|\mathtt{c}\right|]=[3,3,3,5,1]$.
Here, $S(\vec{n})=[\mathtt{c},\mathtt{a},\mathtt{a},\mathtt{a},\mathtt{c}]$
and since $\vec{b_{5}}=[0,0,1,1,0]$ define the last column of $A$, we have
$S(\vec{n}-\vec{b_{5}})=\mathtt{a}\mathtt{b}\mathtt{c},\mathtt{b}\mathtt{c}\mathtt{a},\mathtt{b}\mathtt{b},\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{c}$.
The alignment defined by the first four columns of $A$ is $A[1:4]$ which is an
alignment of $S(1:\vec{n}-\vec{b_{5}})$ and the last column of $A$ is
$\vec{b_{5}}\cdot S(\vec{n})$. It is interesting to note that $A$ can be
completely defined by $5$-vectors
$\vec{b_{1}}=[1,0,1,1,1],\vec{b_{2}}=[1,1,0,1,0],\vec{b_{3}}=[1,1,1,1,0],\vec{b_{4}}=[0,1,0,1,0],\vec{b_{5}}=[0,0,1,1,0]$
where $b_{i}$ represents column $i$of alignment $A$.

For a problem $\mathbf{P}$, we call $\mathbb{I}_{\mathbf{P}}$ the set of
instances of $\mathbf{P}$. If $\mathbf{P}$ is a decision problem, then
$\mathbf{P}(I)\in\\{\texttt{Yes},\texttt{No}\\}$ is the image of an instance
$I$. If $\mathbf{P}$ is an optimization (minimization) problem, there is a set
$\mathrm{Sol}(I)$ for each instance $I$, a function $v$ defining a non-
negative rational number for each $X\in\mathrm{Sol}(I)$, and a function
$\mathrm{opt}_{v}(I)=\min_{X\in\mathrm{Sol}(I)}\\{v(X)\\}$. We use
$\mathrm{opt}$ instead of $\mathrm{opt}_{v}$ if $v$ is obvious. Let
$\mathbf{A}(I)=v(X\in\mathrm{Sol}(I))$ a solution computed by an algorithm
$\mathbf{A}$ with input $I$. We say that $\mathbf{A}$ is an _$\alpha$
-approximation_ for $\mathbf{P}$ if $\mathbf{A}(I)\leq\alpha\,\mathrm{opt}(I)$
for each $I\in\mathbb{I}_{\mathbf{P}}$. We say that $\alpha$ is an
_approximation factor_ for $\mathbf{P}$.

The _alignment problem_ is a collection of decision and optimization problems
whose instances are finite subsets of $\Sigma^{*}$ and
$\mathrm{Sol}(S)=\mathcal{A}_{S}$ for each instance $S$. Function $v$, used
for scoring alignments, is called _criterion_ for $\mathbf{P}$ and we call
$v[A]$ the _cost of the alignment_ $A$. The _$v$ -optimal alignment_ $A$ of
$S$ is such that $v[A]=\mathrm{opt}(S)$. Thus, we state the following general
optimization problems using the criterion $v$ and integer $k$:

######  Problem 1 (Alignment with criterion $v$).

Given a $k$-sequence $S$, find the cost of a $v$-optimal alignment of $S$.

We also need the decision version of the alignment problem with criterion $v$
where we are given a $k$-sequence $S$ and a number $d\in\mathbb{Q}_{\geq}$,
and we want to decide whether there exists an alignment $A$ of $S$ such that
$v[A]\leq d$.

Usually the cost of an alignment $v$ is defined from a scoring matrix. A
_scoring matrix_ $\gamma$ is a matrix whose elements are rational numbers. The
matrix has rows and columns indexed by symbols in $\Sigma_{\texttt{-}}$. For
$\mathtt{a},\mathtt{b}\in\Sigma_{\texttt{-}}$ and a scoring matrix $\gamma$,
we denote by ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}$ the entry of
$\gamma$ in row $\mathtt{a}$ and column $\mathtt{b}$. The value
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}$ defines the score for a
substitution if $\mathtt{a},\mathtt{b}\in\Sigma$, for an insertion if
$\mathtt{a}=\texttt{-}$, and for a deletion if $\mathtt{b}=\texttt{-}$. The
entry ${\gamma}_{{\texttt{-}}\rightarrow{\texttt{-}}}$ is not defined.

###  2.1 $v{\mathrm{A}_{\gamma}}$\- and $v{\mathrm{N}_{\gamma}}$-score for
scoring alignments of 2-sequences

Consider a scoring matrix $\gamma$. Let $S=s,t\in\Sigma^{*}$ be a 2-sequence
whose length is $\vec{n}=[n=\left|s\right|,m=\left|t\right|]$. A simple
criterion for scoring alignments of 2-sequences using the function
$v{\mathrm{A}_{\gamma}}$ follows. For an alignment $[s^{\prime},t^{\prime}]$
of $s,t$ we define

$\textstyle
v{\mathrm{A}_{\gamma}}[s^{\prime},t^{\prime}]=\sum_{j=1}^{|[s^{\prime},t^{\prime}]|}{\gamma}_{{s^{\prime}\\!(j)}\rightarrow{t^{\prime}\\!(j)}}\,.$

We say that $v{\mathrm{A}_{\gamma}}[s^{\prime},t^{\prime}]$ is a
$v{\mathrm{A}_{\gamma}}$-_score_ of $s,t$. The optimal function for this
criterion is called _unweighted edit distance_ and denoted by
$\mathrm{opt}{\mathrm{A}_{\gamma}}$, and an
$\mathrm{opt}{\mathrm{A}_{\gamma}}$-optimal alignment is also called an
A-_optimal alignment_. When ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{a}}}=0$
and ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=1$ for each
$\mathtt{a}\not=\mathtt{b}\in\Sigma_{\texttt{-}}$,
$\mathrm{opt}{\mathrm{A}_{\gamma}}$ is also known as _Levenshtein distance_
[Lev66].

Now, suppose that $n\geq m$. Needleman and Wunch [NW70] proposed an
$O(n^{2})$-time algorithm for computing

$\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)=\mathrm{opt}{\mathrm{A}_{\gamma}}(S)=\min_{A\in\mathcal{A}_{S}}v{\mathrm{A}_{\gamma}}[A]=\left\\{\begin{array}[]{ll}0&\mbox{if
$S=\emptyset$},\\\
\min_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{n}}\Big{\\{}\mathrm{opt}{\mathrm{A}_{\gamma}}(S[1:\vec{n}-\vec{b})+v{\mathrm{A}_{\gamma}}[\vec{b}\cdot
S]\Big{\\}}&\mbox{otherwise}.\end{array}\right.$

If $\mathrm{opt}{\mathrm{A}_{\gamma}}$ is a Levenshtein distance, Masek and
Paterson [MP80] presented an $O(n^{2}/\log n)$-time algorithm using the “
_Four Russian’s Method_ ”. Crochemore, Landau and Ziv-Ukelson [CLZU03]
extended $\mathrm{opt}{\mathrm{A}_{\gamma}}$-score supporting scoring matrices
with real numbers and describing an $O(n^{2}/\log n)$-time algorithm. Indeed,
there is no algorithm to determine $\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)$ in
$O(n^{2-\delta})$-time for any $\delta>0$, unless SETH is false [BI18].
Andoni, Krauthgamer and Onak [AKO10] described a nearly linear time algorithm
approximating the edit distance within an approximation factor
$\textrm{poly}(\log n)$. Later, Chakraborty et al. [CDG+20] presented an
$O(n^{2-2/7})$-time $\alpha$-approximation for edit distance, where $\alpha$
is constant.

Marzal and Vidal [MV93] defined another criterion for scoring alignments of
two sequences called $v{\mathrm{N}_{\gamma}}$-_score_ , which is a
normalization of $v{\mathrm{A}_{\gamma}}$-score, as follows:

$v{\mathrm{N}_{\gamma}}[A]=\left\\{\begin{array}[]{ll}0\,,&\mbox{if
$\left|A\right|=0$}\,,\\\
v{\mathrm{A}_{\gamma}}[A]/\left|A\right|\,,&\mbox{otherwise}\,.\end{array}\right.$

The optimal function for this criterion as known as _normalized edit distance_
and it is denoted by $\mathrm{opt}{\mathrm{N}_{\gamma}}$, and an
$\mathrm{opt}{\mathrm{N}_{\gamma}}$-optimal alignment is also called a
N-_optimal alignment_ of $S=s,t$.

A naive dynamic programming algorithm was proposed by Marzal and Vidal [MV93]
to obtain an N-optimal alignment of two sequences in $O(n^{3})$-time. Using
fractional programming, Vidal, Marzal and Aibar [VMA95] presented an algorithm
with running time $O(n^{3})$, but requiring only $O(n^{2})$-time in practice
which is similarly to the classical (unnormalized) edit distance algorithm.
Further, Arslan and Egecioglu [AE99] described an $O(n^{2}\log n)$-time
algorithm to this problem.

Let $S=s,t$ a 2-sequence whose length is $\vec{n}$. A simple heuristic for
determining a close value for $\mathrm{opt}{\mathrm{N}_{\gamma}}(s,t)$
computes first $\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)$ and then divides it by
the maximum length $L(\vec{n})=L(S)$ of an optimum alignment of $S$. In order
to find $L(S)$, we use the same dynamic programming strategy for computing
$\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)$, i.e.,

$L(S)=L(\vec{n})=\left\\{\begin{array}[]{ll}0&\mbox{if $S=\emptyset$}\\\
\max_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{n},\mathrm{opt}{\mathrm{A}_{\gamma}}(S)=\mathrm{opt}{\mathrm{A}_{\gamma}}(S-\vec{b})+v{\mathrm{A}_{\gamma}}(\vec{b}\cdot
S)}\Big{\\{}L(\vec{n}-\vec{b})\Big{\\}}+1&\mbox{otherwise},\end{array}\right.$

in $O(nm)$-time. The following theorem shows that this heuristic is a simple
approximation algorithm to find a N-optimal alignment.

######  Theorem 2.1.

Let $s,t$ be a 2-sequence of length $[n,m]$ and let $L(s,t)$ be the maximum
length of an A-optimal alignment of $s,t$. Then,

$\frac{\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)}{L(S)}\leq
2\,\mathrm{opt}{\mathrm{N}_{\gamma}}(s,t)\,,$

and it can be computed in $O(n^{2})$-time if $n=m$. Moreover, this ratio is
tight, i.e., for any positive rational $\varepsilon$, there exists a scoring
matrix $\gamma$, sequences $s,t$ and an $A$-optimal alignment of $s,t$ with
maximum length $A$ such that

$\frac{\mathrm{opt}{\mathrm{A}_{\gamma}}(s,t)}{\left|A\right|}=\frac{v{\mathrm{A}_{\gamma}}[A]}{\left|A\right|}=(2-\varepsilon)\,\mathrm{opt}{\mathrm{N}_{\gamma}}(s,t).$

###### Proof.

Let $A$ be an $A$-optimal alignment with maximum length computed by the
heuristic above in $O(nm)$-time. Let $B$ be an N-optimal alignment. Thus,
$v{\mathrm{A}_{\gamma}}[A]\leq v{\mathrm{A}_{\gamma}}[B]$. Moreover, since
$\left|B\right|\leq n+m$, $n+m\leq 2\,\max\\{n,m\\}$ and $\max\\{n,m\\}\leq
2\left|A\right|$, we have that $\left|A\right|\geq\left|B\right|/2$.
Therefore,
$v{\mathrm{N}_{\gamma}}[A]=\frac{v{\mathrm{A}_{\gamma}}[A]}{\left|A\right|}\leq\frac{v{\mathrm{A}_{\gamma}}[B]}{\left|A\right|}\leq\frac{v{\mathrm{A}_{\gamma}}[B]}{\left|B\right|/2}=2\,\mathrm{opt}{\mathrm{N}_{\gamma}}(s,t)\,.$

We present now a 2-sequence $s,t$ and a scoring matrix $\gamma$ such that the
solution given by the heuristic is at least
$(2-\varepsilon)\mathrm{opt}{\mathrm{N}_{\gamma}}(s,t)$ for any $\varepsilon$
in $\mathbb{Q}_{>}$. Let $\Sigma=\\{\mathtt{a},\mathtt{b}\\}$, $\gamma$ be a
scoring matrix such that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}={\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}=1/\varepsilon$
and ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=2/\varepsilon-1$ and
$\mathtt{a}^{n},\mathtt{b}^{n}\in\Sigma^{*}$, where $n$ in a positive integer.
Observe that the $v{\mathrm{A}_{\gamma}}$-score of any alignment of
$(\mathtt{a}^{n},\mathtt{b}^{n})$, where $[\mathtt{a},\mathtt{b}]$ is aligned
in $k$ columns, is equal to $2n/\varepsilon-k$. Thus,
$\mathrm{opt}{\mathrm{A}_{\gamma}}(\mathtt{a}^{n},\mathtt{b}^{n})=\min_{0\leq
k\leq n}\\{2n/\varepsilon-k\\}=2n/\varepsilon-n=(2/\varepsilon-1)\,n$ which
implies $[\mathtt{a}^{n},\mathtt{b}^{n}]$ is the $A$-optimal alignment with
maximum length. Since
$\mathrm{opt}{\mathrm{N}_{\gamma}}(\mathtt{a}^{n},\mathtt{b}^{n})\leq
v{\mathrm{N}_{\gamma}}([\mathtt{a}^{n}\texttt{-}^{n},\texttt{-}^{n}\mathtt{b}^{n}])=1/\varepsilon$,
it follows

$\displaystyle\frac{\mathrm{opt}{\mathrm{A}_{\gamma}}(\mathtt{a}^{n},\mathtt{b}^{n})}{\left|[\mathtt{a}^{n},\mathtt{b}^{n}]\right|}$
$\displaystyle=\frac{v{\mathrm{A}_{\gamma}}[\mathtt{a}^{n},\mathtt{b}^{n}]}{\left|[\mathtt{a}^{n},\mathtt{b}^{n}]\right|}=\frac{(2/\varepsilon-1)\,n}{n}=\frac{2-\varepsilon}{\varepsilon}=(2-\varepsilon)\,v{\mathrm{N}_{\gamma}}([\mathtt{a}^{n}\texttt{-}^{n},\texttt{-}^{n}\mathtt{b}^{n}])\geq(2-\varepsilon)\,\mathrm{opt}{\mathrm{N}_{\gamma}}(\mathtt{a}^{n},\mathtt{b}^{n})\,.$

∎

We define now classes of scoring matrices. The most common class of scoring
matrices $\mathbb{M}^{\mathrm{C}}$ has the following properties: for all
$\mathtt{a},\mathtt{b},\mathtt{c},\in\Sigma_{\texttt{-}}$, we have (a)
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}>0$ if
$\mathtt{a}\not=\mathtt{b}$, and
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=0$ if $\mathtt{a}=\mathtt{b}$;
(b)
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$;
and (c)
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}+{\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{c}}}$.
The class $\mathbb{M}^{\mathrm{W}}$ of scoring matrices is such that, for all
symbols $\mathtt{a},\mathtt{b},\mathtt{c}\in\Sigma$, we have (a)
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}={\gamma}_{{\texttt{-}}\rightarrow{\mathtt{a}}}>0$;
(b) ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}>0$ if
$\mathtt{a}\not=\mathtt{b}$, and
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=0$ if $\mathtt{a}=\mathtt{b}$;
(c) if
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}<{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{b}}}$,
then
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$;
(d)
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}+{\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}$;
and (e)
$\min\\{{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}},{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{c}}}\\}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}+{\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{c}}}$.
Moreover, the class $\mathbb{M}^{\mathrm{N}}$ is such that (a)
$\mathbb{M}^{\mathrm{N}}\subseteq\mathbb{M}^{\mathrm{W}}$ and (b)
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}\leq
2\,{\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}$ for each
$\mathtt{a},\mathtt{b}\in\Sigma$.

For a set $S$, we say that $f:S\times S\rightarrow\mathbb{R}$ is a _distance
function_ or _metric on $S$_ if $f$ satisfies for all $s,t,u\in S$,:

  1. 1.

$f(s,s)=0$ (_reflexivity_);

  2. 2.

$f(s,t)>0$ if $s\not=t$ (_strict positiveness_);

  3. 3.

$f(s,t)=f(t,s)$ (_symmetry_); and

  4. 4.

$f(s,u)\leq f(s,t)+f(t,u)$ (_triangle inequality_).

If a given criterion $v$ depends on a scoring matrix $\gamma$ and it is a
metric on $\Sigma^{*}$, we say that the scoring matrix $\gamma$ _induces_ a
$\mathrm{opt}_{v}$-distance on $\Sigma^{*}$. Sellers [Sel74] showed that
matrices in $\mathbb{M}^{\mathrm{C}}$ induce an
$\mathrm{opt}{\mathrm{A}_{\gamma}}$-distance on $\Sigma^{*}$. Araujo and
Soares [AS06] showed that $\gamma\in\mathbb{M}^{\mathrm{W}}$ and
$\gamma\in\mathbb{M}^{\mathrm{N}}$ if and only if $\gamma$ induces an
$\mathrm{opt}{\mathrm{A}_{\gamma}}$-distance and an
$\mathrm{opt}{\mathrm{N}_{\gamma}}$-distance on $\Sigma^{*}$ respectively.
Figure 2 shows the relationship between these classes.

$\mathbb{M}^{\mathrm{W}}$$\mathbb{M}^{\mathrm{C}}$$\mathbb{M}^{\mathrm{N}}$
Figure 2: Relationship between scoring matrices. Araujo and Soares [AS06]
showed that $\mathbb{M}^{\mathrm{C}}\subseteq\mathbb{M}^{\mathrm{W}}$,
$\mathbb{M}^{\mathrm{N}}\subseteq\mathbb{M}^{\mathrm{W}}$,
$\mathbb{M}^{\mathrm{C}}\not\subseteq\mathbb{M}^{\mathrm{N}}$ and
$\mathbb{M}^{\mathrm{N}}\not\subseteq\mathbb{M}^{\mathrm{C}}$. Moreover, the
scoring matrix $\gamma$ such that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{a}}}=0$ for each $\mathtt{a}$ and
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=1$ for each
$\mathtt{a}\not=\mathtt{b}$ is in
$\mathbb{M}^{\mathrm{C}}\cap\mathbb{M}^{\mathrm{N}}$, which implies that
$\mathbb{M}^{\mathrm{C}}\cap\mathbb{M}^{\mathrm{N}}\not=\emptyset$.

Given a scoring function $v$ for alignments of 2-sequences $s,t$ that depends
on a scoring matrix, we say that two scoring matrices $\gamma$ and $\rho$ are
_equivalent_ considering $v$ when $v_{\gamma}[A]\leq v_{\gamma}[B]$ if and
only if $v_{\rho}[A]\leq v_{\rho}[B]$ for any pair of alignments $A,B$ of
sequences $s,t$. If $\rho$ is a matrix obtained from $\gamma$ by multiplying
each entry of $\gamma$ by a constant $c>0$, then
$v{\mathrm{A}_{\rho}}[A]=c\cdot v{\mathrm{A}_{\gamma}}[A]$ and
$v{\mathrm{N}_{\rho}}[A]=c\cdot v{\mathrm{N}_{\gamma}}[A]$, which implies that
$\gamma$ and $\rho$ are equivalent. As a consequence, when the scoring
function is $v{\mathrm{A}_{\gamma}}$ or $v{\mathrm{N}_{\gamma}}$ and it is
convenient, we can suppose that all entries of $\gamma$ are integers instead
of rationals.

###  2.2 $v{\mathrm{SP}_{\\!\gamma}}$-score for $k$ sequences

Consider a scoring matrix $\gamma$. Let $S=s_{1},\ldots,s_{k}$ be a
$k$-sequence whose length is $\vec{n}$ and
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ be an alignment of $S$. The
criterion $v{\mathrm{SP}_{\\!\gamma}}$, also called _SP-score_ , for scoring
the alignment $A$ is

$\displaystyle\textstyle
v{\mathrm{SP}_{\\!\gamma}}[A]=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]\,.$
(3)

We define $\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}$ as the optimal function for
the criterion $v{\mathrm{SP}_{\\!\gamma}}$. An alignment $A$ of $S$ such that
$v{\mathrm{SP}_{\\!\gamma}}[A]=\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$ is
called _$v{\mathrm{SP}_{\\!\gamma}}$ -optimal alignment_. Regardless its
decision or optimization version, we call the associated problem as _multiple
sequence alignment problem_ ($\mathbf{MSA}$). Formally,

######  Problem 2 (Multiple sequence alignment).

Let $\gamma$ be a fixed scoring matrix. Given a $k$-sequence $S$, find
$\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$.

In order to compute $\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}$, we extend the
definition of $v{\mathrm{SP}_{\\!\gamma}}$ considering a column of an
alignment $A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ as its parameter. Thus,
$v{\mathrm{SP}_{\\!\gamma}}[A(j)]=v{\mathrm{SP}_{\\!\gamma}}[A[\vec{j}]]=\sum_{i<h}{\gamma}_{{s^{\prime}_{i}(j)}\rightarrow{s^{\prime}_{h}(j)}}$
assuming that ${\gamma}_{{\texttt{-}}\rightarrow{\texttt{-}}}=0$ and
$\vec{j}=[j,\ldots,j]$ and

$\displaystyle\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$
$\displaystyle=\min_{A\in\mathcal{A}_{S}}v{\mathrm{SP}_{\\!\gamma}}[A]=\left\\{\begin{array}[]{ll}0&\mbox{if
$S=\emptyset$}\\\
\textstyle\min_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{n}}\Big{\\{}\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S(1\\!:\\!\vec{n}-\vec{b}))+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{n})]\Big{\\}}&\mbox{otherwise}.\end{array}\right.$ (6)

Recurrence (6) can be computed using a dynamic programming algorithm,
obtaining
$D(\vec{\jmath})=\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S(1\\!:\\!\vec{\jmath}))$
for all $\vec{\jmath}\leq\vec{n}$. This task can be performed by generating
all indexes of $D$ in lexicographical order, starting with $D(\vec{0})=0$, as
presented in Algorithm 1.

Algorithm 1

0: $S=s_{1},\ldots,s_{k}\in(\Sigma^{*})^{k}$

0: $\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$

1: $D(\vec{0})\leftarrow 0$

2: for each $\vec{\jmath}\leq\vec{n}$ in lexicographical order do

3:
$D(\vec{\jmath})\leftarrow\min_{\vec{b}\in\mathcal{B}^{{k}},\,\vec{b}\leq\vec{\jmath}}\big{\\{}D(\vec{\jmath}-\vec{b})+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{\jmath})]\big{\\}}$

4: return $D(\vec{n})$

Suppose that $\left|s_{i}\right|=n$ for each $i$. Notice that the space to
store the matrix $D$ is $\Theta((n+1)^{k})$ and thus Algorithm 1 uses
$\Theta((n+1)^{k})$-space. Besides that, Algorithm 1 checks, in the worst
case, $\Theta(2^{k})$ entries for computing all entries in the matrix $D$ and
each computation spends $\Theta(k^{2})$-time. Therefore, its running time is
$O(2^{k}k^{2}(n+1)^{k})$. Observe that when the distance is small, not all
entries in $D$ need to be computed, such as in the Carrillo and Lipman’s
algorithm [CL88].

We can also describe an obvious but unusual variant of this problem that
consider a scoring matrix for each pair of the sequences. Formally,
considering an scoring matrix array
$\vec{\gamma}=[\gamma^{(12)},\gamma^{(13)},\ldots,\gamma^{(1k)},\gamma^{(23)},\ldots,\gamma^{(2k)},\ldots,\gamma^{((k-1)k)}]$
and an alignment $A$ of a $k$-sequence,

$\displaystyle
v{\mathrm{SP}_{\\!\vec{\gamma}}}[A]=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{A}_{\gamma^{(hi)}}}[A_{\\{h,i\\}}]\,.$

Thus, given a $k$-sequence $S$, we ask for finding
$\mathrm{opt}{\mathrm{SP}_{\\!\vec{\gamma}}}(S)=\min_{A\in\mathcal{A}_{S}}\\{v{\mathrm{SP}_{\\!\vec{\gamma}}}[A]\\}$.
Algorithm 1 can be easily modified in order to solve this extended version
with same time and space complexity. This is important here because this
version is used as a subroutine of one of the normalized version.

###  2.3 ${\mathrm{V}^{i}_{\\!\gamma}}$-score for $k$ sequences

In this section we define a new criteria to normalize the
$v{\mathrm{SP}_{\\!\gamma}}$-score of a multiple alignment. The new criteria
for aligning sequences takes into account the length of the alignments
according to the following:

$\displaystyle{\mathrm{V}^{1}_{\\!\gamma}}[A]$
$\displaystyle=\left\\{\begin{array}[]{ll}0\,,&\mbox{if
$\left|A\right|=0$\,,}\\\
v{\mathrm{SP}_{\\!\gamma}}[A]/\left|A\right|\,,&\mbox{otherwise}\,,\\\
\end{array}\right.$ (9) $\displaystyle{\mathrm{V}^{2}_{\\!\gamma}}[A]$
$\displaystyle=\textstyle\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]\,,$
(10) $\displaystyle{\mathrm{V}^{3}_{\\!\gamma}}[A]$
$\displaystyle=\left\\{\begin{array}[]{ll}0\,,&\mbox{if
$\left|A\right|=0$\,,}\\\
v{\mathrm{SP}_{\\!\gamma}}[A]\big{/}\big{(}\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}|A_{\\{h,i\\}}|\big{)}\,,\big{.}&\mbox{otherwise}\,.\end{array}\right.$
(13)

We define $\mathrm{opt}{\mathrm{NSP}^{z}_{\\!\gamma}}$ as the optimal function
for the criterion ${\mathrm{V}^{z}_{\\!\gamma}}$, i.e., for a given
$k$-sequence $S$

$\mathrm{opt}{\mathrm{NSP}^{z}_{\\!\gamma}}(S)=\min_{A\in\mathcal{A}_{S}}{\mathrm{V}^{z}_{\\!\gamma}}[A].$

An alignment $A$ of $S$ such that
${\mathrm{V}^{z}_{\\!\gamma}}[A]=\mathrm{opt}{\mathrm{NSP}^{z}_{\\!\gamma}}(S)$
is called _${\mathrm{V}^{z}_{\\!\gamma}}$ -optimal alignment_. Moreover,
regardless its decision or optimization version, we establish the _criterion
${\mathrm{V}^{z}_{\\!\gamma}}$ for the normalized multiple sequence alignment
problem_ ($\mathbf{NMSA}\text{-}z$), for $z=1,2,3$. Formally, for a fixed
scoring matrix $\gamma$ and $z\in\\{1,2,3\\}$,

######  Problem 3 (Normalized multiple sequence alignment with score
${\mathrm{V}^{z}_{\\!\gamma}}$).

Given a $k$-sequence $S$, find
$\mathrm{opt}{\mathrm{NSP}^{z}_{\\!\gamma}}(S)$.

An interesting question is whether the definitions above represent the same
criterion. i.e., would it be possible that the optimal alignment for a given
criterion ${\mathrm{V}^{z}_{\\!\gamma}}$ also represents an optimal alignment
for another criterion ${\mathrm{V}^{z^{\prime}}_{\\!\gamma}}$,
$z\not=z^{\prime}$, regardless of the sequences and scoring matrices? The
answer is no and Figure 3 shows examples that support this claim.

$\gamma=\begin{array}[]{c|cccc}&\mathtt{a}&\mathtt{b}&\mathtt{c}&\texttt{-}\\\
\hline\cr\mathtt{a}&0&9&9&10\\\ \mathtt{b}&9&0&9&10\\\ \mathtt{c}&9&9&0&10\\\
\texttt{-}&10&10&10&0\\\ \end{array}\hskip
28.45274ptA=\left[\begin{array}[]{c}\mathtt{a}\\\ \mathtt{b}\\\
\mathtt{c}\end{array}\right]\hskip
28.45274ptB=\left[\begin{array}[]{cc}\mathtt{a}&\texttt{-}\\\
\mathtt{b}&\texttt{-}\\\ \texttt{-}&\mathtt{c}\end{array}\right]\hskip
28.45274ptC=\left[\begin{array}[]{ccc}\mathtt{a}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\mathtt{b}&\texttt{-}\\\
\texttt{-}&\texttt{-}&\mathtt{c}\end{array}\right]$

$\delta=\begin{array}[]{c|cccc}&\mathtt{a}&\mathtt{b}&\mathtt{c}&\texttt{-}\\\
\hline\cr\mathtt{a}&0&7&7&9\\\ \mathtt{b}&7&0&7&9\\\ \mathtt{c}&7&7&0&9\\\
\texttt{-}&9&9&9&0\\\ \end{array}\hskip
28.45274ptD=\left[\begin{array}[]{ccc}\mathtt{a}&\mathtt{b}&\mathtt{c}\\\
\mathtt{a}&\mathtt{c}&\mathtt{b}\\\
\mathtt{c}&\mathtt{b}&\mathtt{a}\end{array}\right]\hskip
28.45274ptE=\left[\begin{array}[]{cccc}\mathtt{a}&\mathtt{b}&\mathtt{c}&\texttt{-}\\\
\mathtt{a}&\texttt{-}&\mathtt{c}&\mathtt{b}\\\
\mathtt{c}&\mathtt{b}&\mathtt{a}&\texttt{-}\end{array}\right]\hskip
28.45274ptF=\left[\begin{array}[]{ccccc}\mathtt{a}&\mathtt{b}&\mathtt{c}&\texttt{-}&\texttt{-}\\\
\mathtt{a}&\texttt{-}&\mathtt{c}&\mathtt{b}&\texttt{-}\\\
\texttt{-}&\texttt{-}&\mathtt{c}&\mathtt{b}&\mathtt{a}\end{array}\right]$

Figure 3: Observe first that $A$, $B$ or $C$ is an
${\mathrm{V}^{z}_{\\!\gamma}}$-optimal alignment of 3-sequence
$\mathtt{a},\mathtt{b},\mathtt{c}$ for each $z$. Besides, since
${\mathrm{V}^{1}_{\\!\gamma}}[A]=27.0,{\mathrm{V}^{2}_{\\!\gamma}}[A]=27.0,{\mathrm{V}^{3}_{\\!\gamma}}[A]=9.0;{\mathrm{V}^{1}_{\\!\gamma}}[B]=24.5,{\mathrm{V}^{2}_{\\!\gamma}}[B]=29.0,{\mathrm{V}^{3}_{\\!\gamma}}[B]=9.8;{\mathrm{V}^{1}_{\\!\gamma}}[C]=20.0,{\mathrm{V}^{2}_{\\!\gamma}}[C]=30.0,{\mathrm{V}^{3}_{\\!\gamma}}[C]=10.0$,
we have that $C$ is an optimal alignment for criterion
${\mathrm{V}^{1}_{\\!\gamma}}$ but it is not for criteria
${\mathrm{V}^{2}_{\\!\gamma}}$ or ${\mathrm{V}^{3}_{\\!\gamma}}$, which
implies that an optimal alignment for criterion ${\mathrm{V}^{1}_{\\!\gamma}}$
is different when we compare it to criteria ${\mathrm{V}^{2}_{\\!\gamma}}$ and
${\mathrm{V}^{3}_{\\!\gamma}}$. Now, observe that $D$, $E$ or $F$ is an
${\mathrm{V}^{z}_{\\!\delta}}$-optimal alignment of 3-sequence
$\mathtt{a}\mathtt{b}\mathtt{c},\mathtt{a}\mathtt{c}\mathtt{b},\mathtt{c}\mathtt{b}\mathtt{a}$
for each $z$. Besides, since
${\mathrm{V}^{2}_{\\!\delta}}[D]=16.33,{\mathrm{V}^{3}_{\\!\delta}}[D]=5.44;{\mathrm{V}^{2}_{\\!\delta}}[E]=17.16,{\mathrm{V}^{3}_{\\!\delta}}[E]=5.81;{\mathrm{V}^{2}_{\\!\delta}}[F]=16.20,{\mathrm{V}^{3}_{\\!\delta}}[F]=5.53$,
we have that $D$ is an optimal alignment for criterion
${\mathrm{V}^{3}_{\\!\delta}}$ but it is not for criterion
${\mathrm{V}^{2}_{\\!\delta}}$ which implies that an optimal alignment for
criterion ${\mathrm{V}^{2}_{\\!\delta}}$ is different when we compare it to
criterion ${\mathrm{V}^{3}_{\\!\delta}}$.

##  3 Complexity

We study now the complexity of the multiple sequence alignment problem for
each new criterion defined in Section 2. We consider the decision version of
the computational problems and we prove $\mathbf{NMSA}\text{-}z$ is NP-
complete for each $z$ even though the following additional restrictions for
the scoring matrix $\gamma$ hold:
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$
and ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=0$ if and only if
$\mathtt{a}=\mathtt{b}$ for each pair
$\mathtt{a},\mathtt{b}\in\Sigma_{\texttt{-}}$. Elias [Eli06] shows that, even
considering such restrictions, $\mathbf{MSA}$ is NP-complete. We start showing
a polynomial time reduction from $\mathbf{MSA}$ to $\mathbf{NMSA}\text{-}z$.

For an instance $(S,C)$ of $\mathbf{MSA}$ ($\mathbf{NMSA}\text{-}z$), where
$S=s_{1},\ldots,s_{k}$ is a $k$-sequence and $C$ is an integer,
$\mathbf{MSA}(S,C)$ ($\mathbf{NMSA}\text{-}z(S,C)$) is the decision problem
version asking whether there exists an alignment $A$ of $S$ such that
$v{\mathrm{SP}_{\\!\gamma}}[A]\leq C$ (${\mathrm{V}^{i}_{\\!\gamma}}[A]\leq
C$).

Consider a fixed alphabet $\Sigma$ and scoring matrix $\gamma$ with the
restrictions above that are
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$
and ${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=0$. We also assume each
entry of $\gamma$ is integer. Let $\sigma\not\in\Sigma_{\texttt{-}}$ be a new
symbol and $\Sigma^{\sigma}=\Sigma\cup\\{\sigma\\}$ and $G$ the maximum number
in $\gamma$. We define a scoring matrix $\gamma^{\sigma}$ such that
${\gamma^{\sigma}\\!\\!\\!}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}},{\gamma^{\sigma}\\!\\!\\!}_{{\mathtt{a}}\rightarrow{\sigma}}={\gamma^{\sigma}\\!\\!\\!}_{{\sigma}\rightarrow{\mathtt{a}}}=G$
and ${\gamma^{\sigma}\\!\\!\\!}_{{\sigma}\rightarrow{\sigma}}=0$ for each pair
$\mathtt{a},\mathtt{b}\in\Sigma_{\texttt{-}}$. Notice that
${\gamma^{\sigma}}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma^{\sigma}}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$
and ${\gamma^{\sigma}}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=0$ if and only if
$\mathtt{a}=\mathtt{b}$ for each pair
$\mathtt{a},\mathtt{b}\in\Sigma^{\sigma}_{\texttt{-}}$ and therefore $G\geq
1$. Also, we denote $S^{L}=s_{1}\sigma^{L},\ldots,s_{k}\sigma^{L}$, where
$L=Nk^{2}MG$, $M=\max_{i}\\{\left|s_{i}\right|\\}$ and $N=\binom{k}{2}M$.

Let $A$ be an alignment of $S^{L}$. A $\sigma$-_column_ in $A$ is a column
where every symbol is equal to $\sigma$. The _tail_ of $A$ is the alignment
$A[j+1:\left|A\right|]$ if each its column is $\sigma$-columns but $A(j)$ is
not; in this case the _tail length_ of $A$ is $\left|A\right|-j$ and the
column $j$ is the _tail base_. We say that an alignment of $S^{L}$ is
_canonical_ if its tail length is $L$. If
$A=[s_{1}^{\prime\prime},\ldots,s_{k}^{\prime\prime}]$ is the alignment of
$S$, then we denote by $A^{L}$ the canonical alignment
$[s_{1}^{\prime\prime}\sigma^{L},\ldots,s_{k}^{\prime\prime}\sigma^{L}]$ of
$S^{L}$, i.e., $A^{L}[1:\left|A\right|]=A$ and
$A^{L}[\left|A\right|+1:\left|A^{L}\right|]=[\sigma^{L},\sigma^{L},\ldots,\sigma^{L}]$.
Notice that $\left|A^{L}\right|\geq L$. Then, we establish below a lower bound
for $v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]$ and
$v{\mathrm{SP}_{\\!\gamma}}[A]$.

######  Proposition 3.1.

Let $A$ be an alignment of a $k$-sequence $S=s_{1},s_{2},\ldots,s_{k}$. Then,
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]=v{\mathrm{SP}_{\\!\gamma}}[A]\leq
k^{2}MG$.

###### Proof.

Suppose that $A=[s_{1}^{\prime},\ldots,s_{k}^{\prime}]$ and then
$A^{L}=[s_{1}^{\prime}\sigma^{L},\ldots,s_{k}^{\prime}\sigma^{L}]$. Because
$M=\max_{i}\left|s_{i}\right|$, each alignment that is induced by two
sequences in $A$ has at most $2M$ columns. Moreover, each entry in $\gamma$ is
at most $G$. It follows that
$v{\mathrm{A}_{\gamma}}[s_{h}^{\prime},s_{i}^{\prime}]=v{\mathrm{A}_{\gamma}}[s_{h}^{\prime}\sigma^{L},s_{i}^{\prime}\sigma^{L}]\leq
2MG$ for each pair $h,i$ and then

$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]=v{\mathrm{SP}_{\\!\gamma}}[A]=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]\leq\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}2MG=\textstyle\binom{k}{2}2MG\leq
k^{2}MG\,.$

∎

The two following result are useful to prove Theorem 3.4, which is the main
result of this section. Let
$C^{1}:=C^{2}:=C/L,C^{3}:=C/\big{(}\binom{k}{2}L\big{)}$ and $L:=Nk^{2}MG$.

######  Lemma 3.2.

If $C\geq k^{2}MG$, then
$\mathbf{MSA}(S,C)=\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$, for each
$z=1,2,3$.

###### Proof.

Suppose that $C\geq k^{2}MG$. Let $A$ be an alignment of $S$. From Proposition
3.1,
$v{\mathrm{SP}_{\\!\gamma}}[A]=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]\leq
k^{2}MG\leq C$ which implies that $\mathbf{MSA}(S,C)=\textsf{Yes}$. Since
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C$, we have that
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{L}]=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]/L\leq
C/L=C^{1}$, and then $\mathbf{NMSA}\text{-}1(S^{L},C^{1})=\textsf{Yes}$. Since
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C$ and
$|A_{\\{h,i\\}}^{L}|\geq L$, we have

${\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A^{L}]=\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{\big{|}A_{\\{h,i\\}}^{L}\big{|}}\leq\frac{\displaystyle\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{L}=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{L}\leq\frac{C}{L}=C^{2}\,,$

and thus $\mathbf{NMSA}\text{-}2(S^{L},C^{2})=\textsf{Yes}$. Again, since
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C$ and
$|A_{\\{h,i\\}}^{L}|\geq L$, we have

${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{L}]=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\displaystyle\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}\big{|}A_{\\{h,i\\}}^{L}\big{|}}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\displaystyle\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}L}=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\binom{k}{2}L}\leq\frac{C}{\binom{k}{2}L}=C^{3}\,,$

and then $\mathbf{NMSA}\text{-}3(S^{L},C^{3})=\textsf{Yes}$.

Therefore, if $C\geq k^{2}MG$, then
$\mathbf{MSA}(S,C)=\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$ for each
$z$. ∎

######  Lemma 3.3.

There exists a canonical alignment of $S^{L}$ which is
${\mathrm{V}^{z}_{\\!\gamma^{\sigma}}}$-optimal for each $z$.

###### Proof.

Suppose by contradiction that any canonical alignment of $S^{L}$ is not
${\mathrm{V}^{z}_{\\!\gamma^{\sigma}}}$-optimal. Let
$A=[s_{1}^{\prime},\ldots,s_{k}^{\prime}]$ be a
${\mathrm{V}^{z}_{\\!\gamma^{\sigma}}}$-optimal alignment of $S^{L}$ with
maximum tail length and maximum number of $\sigma$ in the tail base. Note
that, by hypothesis, $A$ is not canonical.

Let $q$ be the index of the tail base of $A$. Since $A$ is not canonical, the
column $q$ contains only symbols - and $\sigma$. Let $p$ be the greatest index
such that $p<q$ and there exists an integer $i$ where
$s_{i}^{\prime}(p)=\sigma$ and $s_{i}^{\prime}(q)=\texttt{-}$. Let
$A^{\prime}=[s_{1}^{\prime\prime},\ldots,s_{k}^{\prime\prime}]$ be an
alignment of $S^{L}$ such that $A^{\prime}$ is almost the same as $A$, except
for columns $p$ and $q$, that are defined as following. For each $h$, we have

$s_{h}^{\prime\prime}=\left\\{\begin{array}[]{ll}s_{h}^{\prime}\,,&\text{if
$s_{h}^{\prime}(p)\neq\sigma$~{}\text{or}~{}$s_{h}^{\prime}(q)\neq\texttt{-}$}\,,\\\
s_{h}^{\prime}(1\\!:\\!p-1)\cdot\texttt{-}\cdot
s_{h}^{\prime}(p+1\\!:\\!q-1)\cdot\sigma\cdot
s_{h}^{\prime}(q+1\\!:\\!\left|s_{h}^{\prime}\right|)\,,&\text{otherwise}\,.\end{array}\right.$

Observe that either the tail length of $A^{\prime}$ is greater than the tail
length of $A$ or the tail lengths of $A$ and $A^{\prime}$ are the same but the
number of $\sigma$ in the tail base of $A^{\prime}$ is greater than this
number in $A$. Thus, by the choice of $A$, the alignment $A^{\prime}$ is not
${\mathrm{V}^{z}_{\\!\gamma^{\sigma}}}$-optimal.

Let $h,i$ be integers. We classify the induced alignment $A_{\\{h,i\\}}$ of
$A$ as follows:

  * •

Type 1: if
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]$
and $|A_{\\{h,i\\}}|=|A_{\\{h,i\\}}^{\prime}|$ ;

  * •

Type 2: if $v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]\neq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]$ and
$|A_{\\{h,i\\}}|=|A_{\\{h,i\\}}^{\prime}|$. In this case, the only possibility
is that in one of the sequences, say $s_{h}^{\prime}$, is such that
$s_{h}^{\prime}(p)=\sigma$ and $s_{h}^{\prime}(q)=\texttt{-}$, and the other,
$s_{i}^{\prime}$, is such that $s_{i}^{\prime}(p)=x$ and
$s_{i}^{\prime}(q)=\sigma$, where $x\in\Sigma$. By hypothesis,
$G\geq{\gamma}_{{x}\rightarrow{\texttt{-}}}={\gamma}_{{\texttt{-}}\rightarrow{x}}$.
Then,

$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-G+{\gamma}_{{x}\rightarrow{\texttt{-}}}(={\gamma}_{{\texttt{-}}\rightarrow{x}})\leq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]\,.$

Therefore, $v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\leq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]$ ;

  * •

Type 3: if $|A_{\\{h,i\\}}|\neq|A_{\\{h,i\\}}^{\prime}|$. In this case, the
only possibility is that in one of the sequences, say $s_{h}^{\prime}$, is
such that $s_{h}^{\prime}(p)=\sigma$ and $s_{h}^{\prime}(q)=\texttt{-}$, and
the other, $s_{i}^{\prime}$, is such that $s_{i}^{\prime}(p)=\texttt{-}$ and
$s_{i}^{\prime}(q)=\sigma$. It follows that

$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G\qquad\text{and}\qquad|A_{\\{h,i\\}}|=|A_{\\{h,i\\}}^{\prime}|+1\,.$

We consider now the case $z=1$. Suppose that
$\left|A^{\prime}\right|=\left|A\right|$. Analyzing the types above,
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\leq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]$, which implies that
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{\prime}]\leq
v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]$ and
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}(A^{\prime})=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{\prime}]/\left|A^{\prime}\right|\leq
v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]/\left|A\right|={\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A]$,
which contradicts $A^{\prime}$ is not
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}$-optimal. Then, we assume
$\left|A^{\prime}\right|\neq\left|A\right|$ which implies that
$\left|A^{\prime}\right|=\left|A\right|-1$ and at least one alignment
$A_{\\{h,i\\}}$ is of type 3, meaning that
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G$.
It follows that $v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{\prime}]\leq
v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-2G$. Then,

${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{\prime}]=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{\prime}]}{\left|A^{\prime}\right|}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-2G}{\left|A\right|-1}\,.$
(14)

Let $B$ be a canonical alignment. By Proposition 3.1, we have that
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[B]\leq k^{2}MG$. By the choice of $A$, we
have
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A]\leq{\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[B]$.
Since $G\geq 1$ and $\left|B\right|\geq L=Nk^{2}MG$, then

${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A]\leq{\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[B]=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[B]}{\left|B\right|}\leq\frac{k^{2}MG}{Nk^{2}MG}=\frac{1}{N}\leq
G\,.$

Since $v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]/\left|A\right|\leq G$, we have
$(v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-G)/(\left|A\right|-1)\leq
v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]/\left|A\right|$ which implies, by
equation (14), $G\geq 1$ and by the definition of
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A]$, that

${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{\prime}]\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-2G}{\left|A\right|-1}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-G}{\left|A\right|-1}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]}{\left|A\right|}={\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A]\,,$

which contradicts again that $A^{\prime}$ is not
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}$-optimal. Thus, there exists a
canonical alignment of $S^{L}$ which is
${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}$-optimal.

Now, we consider the case $z=2$. If an induced alignment $A_{\\{h,i\\}}$ is of
type 1 or 2, then $v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\leq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]$ and
$|A_{\\{h,i\\}}^{\prime}|=|A_{\\{h,i\\}}|$, which implies that

$v{\mathrm{N}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]}{|A_{\\{h,i\\}}^{\prime}|}\leq\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]}{|A_{\\{h,i\\}}|}=v{\mathrm{N}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]\,.$
(15)

If $A_{\\{h,i\\}}$ is of type 3, then
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G$
and $|A_{\\{h,i\\}}^{\prime}|=|A_{\\{h,i\\}}|-1$ which implies that

$v{\mathrm{N}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]}{|A_{\\{h,i\\}}^{\prime}|}=\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G}{|A_{\\{h,i\\}}|-1}\leq\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-G}{|A_{\\{h,i\\}}|-1}\leq\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]}{|A_{\\{h,i\\}}|}\leq
v{\mathrm{N}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]\,,$ (16)

where the first inequality is a consequence of $G\geq 1$ and the second, since
$G$ is the maximum value in $\gamma^{\sigma}$ and therefore $G$ is an upper
bound to $v{\mathrm{N}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]$, is a consequence of
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]/|A_{\\{h,i\\}}|\leq G$. As a
consequence of equations (15) and (16) we have that
${\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A^{\prime}]\leq{\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A]$
contradicting the assumption that $A^{\prime}$ is not
${\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}$-optimal. Thus, there exists a
canonical alignment of $S^{L}$ which is
${\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}$-optimal.

Finally, we show the case when $z=3$. We denote $T_{j}$ the set of all pairs
$(h,i)$ such that $A_{\\{h,i\\}}$ is of type $j$. Recall that each induced
alignment $A_{\\{h,i\\}}$ of types 1 and 2 are such that
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\leq
v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]$ and
$|A_{\\{h,i\\}}^{\prime}|=|A_{\\{h,i\\}}|$. Thus, the total contribution of
the induced alignments of types 1 and 2 to the
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}$-score is

$\sum_{\mathclap{(h,i)\in T_{1}\cup
T_{2}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\,\leq\quad\sum_{\mathclap{(h,i)\in
T_{1}\cup
T_{2}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]\qquad\text{and}\qquad\sum_{\mathclap{(h,i)\in
T_{1}\cup T_{2}}}|A_{\\{h,i\\}}^{\prime}|\,=\quad\sum_{\mathclap{(h,i)\in
T_{1}\cup T_{2}}}|A_{\\{h,i\\}}|\,.$

And since each alignment $A_{\\{h,i\\}}$ of type 3 is such that
$v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]=v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G$
and $|A_{\\{h,i\\}}^{\prime}|=|A_{\\{h,i\\}}|-1$, we have

$\sum_{\mathclap{(h,i)\in
T_{3}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]\;=\;\sum_{\mathclap{(h,i)\in
T_{3}}}\big{(}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G\big{)}\qquad\text{and}\qquad\sum_{\mathclap{(h,i)\in
T_{3}}}|A_{\\{h,i\\}}^{\prime}|\;=\;\sum_{\mathclap{(h,i)\in
T_{3}}}\big{(}|A_{\\{h,i\\}}|-1\big{)}\,.$

It follows that

$\displaystyle{\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{\prime}]$
$\displaystyle=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{\prime}]}{\left|A^{\prime}\right|}\;=\quad\frac{\displaystyle\sum_{\mathclap{(h,i)\in
T_{1}\cup
T_{2}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]+\sum_{\mathclap{(h,i)\in
T_{3}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{\prime}]}{\displaystyle\sum_{\mathclap{(h,i)\in
T_{1}\cup T_{2}}}|A_{\\{h,i\\}}^{\prime}|+\sum_{\mathclap{(h,i)\in
T_{3}}}|A_{\\{h,i\\}}^{\prime}|}\leq\;\quad\frac{\displaystyle\sum_{\mathclap{(h,i)\in
T_{1}\cup
T_{2}}}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]+\sum_{\mathclap{(h,i)\in
T_{3}}}\big{(}v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}]-2G\big{)}}{\displaystyle\sum_{\mathclap{(h,i)\in
T_{1}\cup T_{2}}}|A_{\\{h,i\\}}|+\sum_{\mathclap{(h,i)\in
T_{3}}}\big{(}|A_{\\{h,i\\}}|-1\big{)}}$
$\displaystyle=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-2\left|T_{3}\right|G}{\left(\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\left|A_{\\{h,i\\}}\right|\right)-\left|T_{3}\right|}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]-\left|T_{3}\right|G}{\left(\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\left|A_{\\{h,i\\}}\right|\right)-\left|T_{3}\right|}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]}{\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\left|A_{\\{h,i\\}}\right|}={\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A]\,,$

where the second inequality is a consequence of $G\geq 1$, and the last
inequality is a consequence of
$v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A]/\left|A\right|\leq G$ since $G$ is the
maximum value in $\gamma^{\sigma}$ and then $G$ is an upper bound to
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A]$. Thus,
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{\prime}]\leq{\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A]$,
which contradicts the assumption that $A^{\prime}$ is not
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}$-optimal. Therefore, there exists a
canonical alignment of $S^{L}$ which is
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}$-optimal. ∎

######  Theorem 3.4.

$\mathbf{NMSA}\text{-}z$ is NP-complete for each $z$.

###### Proof.

Given a $k$-sequence $S$, an alignment $A$ of $S$ and a integer $C$, it is
easy to check in polynomial time on the length of $A$ that
${\mathrm{V}^{z}_{\\!\gamma}}[A]\leq C$ for $z\in\\{1,2,3\\}$. Then,
$\mathbf{NMSA}\text{-}z$ is in NP.

Now, we prove that $\mathbf{MSA}(S,C)=\textsf{Yes}$ if and only if
$\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$ for each $z\in\\{1,2,3\\}$.
If $C\geq k^{2}MG$, from Lemma 3.2 the theorem is proved. Thus, we assume
$C<k^{2}MG$.

Suppose that $\mathbf{MSA}(S,C)=\textsf{Yes}$ and, hence, there exists an
alignment $A$ such that $v{\mathrm{SP}_{\\!\gamma}}[A]\leq C$:

$\displaystyle\\!\\!\\!\\!\\!\\!{\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{L}]$
$\displaystyle\\!=\\!\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{|A^{L}|}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{L}=\frac{v{\mathrm{SP}_{\\!\gamma}}[A]}{L}\leq\frac{C}{L}=C^{1}\,,$
$\displaystyle\\!\\!\\!\\!\\!\\!{\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A^{L}]$
$\displaystyle\\!=\\!\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}\\!\\!\\!\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{|A_{\\{h,i\\}}^{L}|}\\!\leq\\!\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\\!\\!\\!\frac{v{\mathrm{A}_{\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{L}\\!=\\!\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{L}\\!=\\!\frac{v{\mathrm{SP}_{\\!\gamma}}[A]}{L}\\!\leq\\!\frac{C}{L}\\!=\\!C^{2},$
$\displaystyle\\!\\!\\!\\!\\!\\!{\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{L}]$
$\displaystyle\\!=\\!\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\displaystyle\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}|A_{\\{h,i\\}}^{L}|}\leq\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\displaystyle\sum_{h=1}^{k-1}\sum_{i=k+1}^{k}L}=\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\binom{k}{2}L}=\frac{v{\mathrm{SP}_{\\!\gamma}}[A]}{\binom{k}{2}L}\leq\frac{C}{\binom{k}{2}L}=C^{3}\,,$

where the first inequality in each equation follows from either $A^{L}$ or
each alignment induced by $A^{L}$ has length at least $L$ and the second
inequality follows from $v{\mathrm{SP}_{\\!\gamma}}[A]\leq C$. Thus, if
$\mathbf{MSA}(S,C)=\textsf{Yes}$ then
$\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$.

Conversely, suppose that $\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$.
It follows from Lemma 3.3 that there exists a canonical alignment $A^{L}$ of
$S^{L}$ such that ${\mathrm{V}^{z}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C^{z}$ for
each $z$. Thus, considering ${\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{L}]\leq
C^{1}$, we have

$\displaystyle v{\mathrm{SP}_{\\!\gamma}}[A]$
$\displaystyle=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]=(N+L)\,\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{N+L}\leq(N+L)\,\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{|A^{L}|}=(N+L)\,{\mathrm{V}^{1}_{\\!\gamma^{\sigma}}}[A^{L}]$
$\displaystyle\leq(N+L)\,C^{1}=(N+L)\,\frac{C}{L}=\frac{NC}{L}+C<\frac{Nk^{2}MG}{L}+C=1+C\,,$

where the first equality holds since $A^{L}$ is canonical, the first
inequality holds since $|A^{L}|\leq N+L$ and the second and the third
inequalities hold by hypothesis. Considering
${\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C^{2}$, we have

$\displaystyle v{\mathrm{SP}_{\\!\gamma}}[A]$
$\displaystyle=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]=(N+L)\,\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{N+L}=(N+L)\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\frac{v{\mathrm{A}_{\\!\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{N+L}$
$\displaystyle\leq(N+L)\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\frac{v{\mathrm{A}_{\\!\gamma^{\sigma}}}[A_{\\{h,i\\}}^{L}]}{|A_{\\{h,i\\}}^{L}|}=(N+L)\,{\mathrm{V}^{2}_{\\!\gamma^{\sigma}}}[A^{L}]$
$\displaystyle\leq(N+L)\,C^{2}=(N+L)\,\frac{C}{L}=\frac{NC}{L}+C<\frac{Nk^{2}MG}{L}+C=1+C\,,$

where the first equality holds since $A^{L}$ is canonical, the first
inequality holds since, for each $h,i$, $|A_{\\{h,i\\}}^{L}|\leq N+L$, and the
second and the third inequalities hold by hypothesis. And finally, considering
${\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{L}]\leq C^{3}$, we have

$\displaystyle v{\mathrm{SP}_{\\!\gamma}}[A]$
$\displaystyle=v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]=\big{(}N+{\textstyle\binom{k}{2}}L\big{)}\,\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{N+{\textstyle\binom{k}{2}}L}$
$\displaystyle\leq\big{(}N+{\textstyle\binom{k}{2}}L\big{)}\,\frac{v{\mathrm{SP}_{\\!\gamma^{\sigma}}}[A^{L}]}{\displaystyle\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\big{|}A_{\\{h,i\\}}^{L}\big{|}}=\big{(}N+{\textstyle\binom{k}{2}}L\big{)}\,{\mathrm{V}^{3}_{\\!\gamma^{\sigma}}}[A^{L}]\leq\big{(}N+{\textstyle\binom{k}{2}}L\big{)}\,C^{3}$
$\displaystyle=\big{(}N+{\textstyle\binom{k}{2}}L\big{)}\,\frac{C}{\binom{k}{2}L}=\frac{NC}{\binom{k}{2}L}+C<\frac{Nk^{2}MG}{\binom{k}{2}L}+C=\frac{1}{\binom{k}{2}}+C\leq
1+C\,,$

where the first equality holds since $A^{L}$ is canonical, the first
inequality holds since the sum of lengths of two sequences induced by a
canonical alignment is at most $N+\binom{k}{2}L$ and the second and the third
inequalities hold by hypothesis. Therefore, if
$\mathbf{NMSA}\text{-}z(S^{L},C^{z})=\textsf{Yes}$ then
$v{\mathrm{SP}_{\\!\gamma}}[A]<1+C$ for any $z\in\\{1,2,3\\}$. Since the
entries in the scoring matrix are integers, we have that
$v{\mathrm{SP}_{\\!\gamma}}[A]$ is an integer. And since $C$ is an integer, it
follows that $v{\mathrm{SP}_{\\!\gamma}}[A]\leq C$.

∎

##  4 Exact algorithms

In the following sections we describe exact dynamic programming algorithms for
$\mathbf{NMSA}\text{-}z$, with $z=1,2,3$.

###  4.1 $\mathbf{NMSA}\text{-}1$

Let $S=s_{1},\ldots,s_{k}$ be a $k$-sequence and
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ be an alignment of $S$. As defined
in Equation (9), ${\mathrm{V}^{1}_{\\!\gamma}}[A]$ takes into account the
length of $A$, and the optimal function is given by
$\mathrm{opt}{\mathrm{V}^{1}_{\\!\gamma}}(S)=\min_{A\in\mathcal{A}_{S}}\big{\\{}{\mathrm{V}^{1}_{\\!\gamma}}[A]\big{\\}}$.
In the optimization version of $\mathbf{NMSA}\text{-}1$, we are given a
$k$-sequence $S$ and we want to compute
$\mathrm{opt}{\mathrm{V}^{1}_{\\!\gamma}}(S)$ for a fixed matrix $\gamma$. We
can solve $\mathbf{NMSA}\text{-}1$ by calculating the minimum SP-score
considering every possible length of an alignment. That is, we compute the
entries of a table $D$ indexed by $V_{\vec{n}}\times\\{0,1,\ldots,N\\}$, where
$\vec{n}=[\left|s_{1}\right|,\ldots,\left|s_{k}\right|]$ and
$N=\sum_{i=1}^{k}|s_{i}|$. The entry $D(\vec{v},L)$ stores the score of an
alignment of $S(\vec{v})$ of length $L$ with minimum SP-score. Notice that
$D(\vec{0},0)=0$, $D(\vec{v}\not=\vec{0},0)=D(\vec{0},L\not=0)=\infty$.
Therefore, the table entries can be calculated as:

$D(\vec{v},L)\\!=\\!\left\\{\\!\\!\begin{array}[]{ll}\\!0\,,&\mbox{\\!\\!\\!\\!if
$\vec{v}\\!=\\!\vec{0},L\\!=\\!0$}\,,\\\ \\!\infty\,,&\mbox{\\!\\!\\!\\!if
$\vec{v}\\!=\\!\vec{0},L\\!\not=\\!0$ or
$\vec{v}\\!\not=\\!\vec{0},L\\!=\\!0$}\,,\\\
\\!\min_{\vec{b}\in\mathcal{B}_{k},\vec{b}\leq\vec{v}}\big{\\{}D(\vec{v}-\vec{b},L-1)+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{v})]\big{\\}},&\mbox{\\!\\!\\!\\!otherwise}\,.\end{array}\right.$

Table $D$ is computed for all possible values of $L=0,\ldots,N$. Consequently,
$\mathrm{opt}{\mathrm{V}^{1}_{\\!\gamma}}(S)=\min_{L}\left\\{D(\vec{n},L)/L\right\\}$
is returned. Algorithm 2 describes this procedure more precisely.

Algorithm 2

0: $k$-sequence $S=s_{1},\ldots,s_{k}$ such that $n_{i}=\left|s_{i}\right|$

0: $\mathrm{opt}{\mathrm{V}^{1}_{\\!\gamma}}(S)$

1: $D(\vec{0},0)\leftarrow 0$

2: for each $L\not=0$ do $D(\vec{0},L)\leftarrow\infty$

3: for each $\vec{v}\not=\vec{0}$ do $D(\vec{v},0)\leftarrow\infty$

4: for each $\vec{0}<\vec{v}\leq\vec{n}$ in lexicographical order do

5: for each $L\leftarrow 1,2,\ldots,N$ do

6:
$D(\vec{v},L)\leftarrow\min_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{v}}\big{\\{}D(\vec{v}-\vec{b},L-1)+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{v})]\big{\\}}$

7: return $\min_{L}\big{\\{}D(\vec{n},L)/L\big{\\}}$

Suppose that $n_{i}=\left|s_{i}\right|=n$ for each $i$ which implies that
$\left|V_{n}\right|=(n+1)^{k}$ and $N=nk$. Notice that the space to store the
matrix $D$ is $\Theta(N\cdot\left|V_{n}\right|=kn\cdot(n+1)^{k})$. The time
consumption of Algorithm 2 corresponds to the time needed to fill the table
$D$ up, plus the running time of line 7. Each entry of $D$ can be computed in
$O((2^{k}-1)\cdot{k\choose 2})=O(2^{k}k^{2})$-time. Therefore, the algorithm
spends $O(2^{k}k^{2}\cdot kn(n+1)^{k})=O(2^{k}k^{3}(n+1)^{k+1})$-time to
compute the entire table $D$. Line 7 is computed in $\Theta(N=kn)$-time.
Therefore, the running time of Algorithm 2 is
$O(2^{k}k^{3}(n+1)^{k+1})+\Theta(N)=O(2^{k}k^{3}(n+1)^{k+1})$.

###  4.2 $\mathbf{NMSA}\text{-}2$

Let $S=s_{1},\ldots,s_{k}$ be a $k$-sequence and
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ be an alignment of $S$. As defined
in Equation (10), ${\mathrm{V}^{2}_{\\!\gamma}}[A]$ takes into account the
lengths of the induced alignments in $A$. In the optimization version of
$\mathbf{NMSA}\text{-}2$, we are given a $k$-sequence $S$ and we want to
compute $\mathrm{opt}{\mathrm{V}^{2}_{\\!\gamma}}(S)$ for a fixed scoring
matrix $\gamma$.

Let $\vec{L}=[L_{12},\ldots,L_{hi},\ldots,L_{(k-1)k}]$ be a ${k\choose
2}$-vector indexed by the set of pairs of integers $\\{h,i\\}$ such that
$1\leq h<i\leq k$ and $L_{hi}$ denotes the element of $\vec{L}$ of index
$\\{h,i\\}$. The lengths of the induced alignments can be represented by a
vector $\vec{L}$. Thus, if $A$ is an alignment and $|A_{\\{h,i\\}}|=L_{hi}$
for each pair $h,i$, we say that $\vec{L}$ is the _induced length_ of $A$. For
a $k$-sequence $S=s_{1},\ldots,s_{k}$, where $n_{i}=\left|s_{i}\right|$ for
each $i$, we define

$\mathbb{L}=\big{\\{}\vec{L}=[{L_{12},L_{13},\ldots,L_{1k},L_{23},\ldots
L_{2k},\ldots,L_{(k-1)k}}]:0\leq L_{hi}\leq n_{h}+n_{i}\big{\\}}.$

Therefore, $\mathbb{L}$ contains the induced length of alignment $A$ of $S$
for all $A\in\mathcal{A}_{S}$. Note that if $n$ is the length of each sequence
in $S$, then $\left|\mathbb{L}\right|=(2n+1)^{k\choose 2}$. Let
$\vec{b}=[b_{1},\ldots,b_{k}]$ be a $k$-vector of bits. Overloading the minus
operator “$-$”, we define $\vec{L}-\vec{b}$ to be a ${k\choose 2}$-vector
$\vec{L^{\prime}}$ such that

$L^{\prime}_{hi}=\left\\{\begin{array}[]{ll}L_{hi}\,,&\mbox{if
$b_{h}=b_{i}=0$}\,,\\\ L_{hi}-1\,,&\mbox{otherwise}\,.\end{array}\right.$

Observe that if $\vec{L}$ is the induced length of an alignment $A$ of
$S(\vec{v})$ and $\vec{b}$ is a $k$-vector of bits such that $\vec{b}\cdot
S(\vec{v})$ is the last column of $A$, then $\vec{L^{\prime}}=\vec{L}-\vec{b}$
is the induced length of the alignment $A(1\\!:\\!\left|A\right|-1)$.

From a $k\choose 2$-vector $\vec{L}$ and a scoring matrix $\gamma$, we can
define an array of $k\choose 2$ scoring matrices
$\vec{\gamma}=\gamma\times\vec{L}=[\ldots,\gamma^{(hi)},\ldots]$ indexed by
$\\{1,\ldots k\\}\times\\{1,\ldots,k\\}$ such that

${\gamma^{(hi)}}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}=\frac{{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}}{L_{hi}},$

for each $\mathtt{a},\mathtt{b}\in\Sigma_{\texttt{-}}$. Observe that

${\mathrm{V}^{2}_{\\!\gamma}}[A]=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\left(v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}](=\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]}{\left|A_{\\{h,i\\}}\right|})\right)=v{\mathrm{A}_{\gamma^{(hi)}}}[A_{\\{h,i\\}}]=v{\mathrm{SP}_{\\!\vec{\gamma}}}[A]$

where
$\vec{\gamma}=\gamma\times[\left|A_{\\{1,2\\}}\right|,\ldots,\left|A_{\\{k-1,k\\}}\right|]$.
Besides, if $\vec{\mathcal{L}}$ is the induced length of a
${\mathrm{V}^{2}_{\\!\gamma}}$-optimal alignment of $S$, then we can compute
$\mathrm{opt}{\mathrm{V}^{2}_{\\!\gamma}}$ through the recurrence

$\displaystyle
D_{\vec{\mathcal{L}}}(\vec{v},\vec{L})=\left\\{\begin{array}[]{ll}0\,,&\mbox{if
$\vec{v}=\vec{0}$ and $\vec{L}=\vec{0}$}\,,\\\ \infty\,,&\mbox{if
$\vec{v}=\vec{0}$ and $\vec{L}\not=\vec{0}$}\,,\\\ \infty\,,&\mbox{if
$\vec{v}\not=\vec{0}$ and $\vec{L}=\vec{0}$}\,,\\\
\displaystyle\min_{\vec{b}\in\mathcal{B}_{k},\vec{b}\leq\vec{v},\vec{b}\leq\vec{L}}\big{\\{}D_{\vec{\mathcal{L}}}(\vec{v}-\vec{b},\vec{L}-\vec{b})+v{\mathrm{SP}_{\\!\vec{\gamma}}}[\vec{b}\cdot
S(\vec{v})]\big{\\}}\,,&\mbox{otherwise},\end{array}\right.$

where $\vec{b}\leq\vec{L}$ is also an overloading, meaning that
$\vec{L}-\vec{b}\geq\vec{0}$, and
$\vec{\gamma}=\gamma\times\vec{\mathcal{L}}$. In this case,
$\mathrm{opt}{\mathrm{V}^{2}_{\\!\gamma}}(S)=D_{\vec{\mathcal{L}}}(\vec{v},\vec{\mathcal{L}})$.

Algorithm 3 described below finds
$\mathrm{opt}{\mathrm{V}^{2}_{\\!\gamma}}(S)$.

Algorithm 3

0: A $k$-sequence $S=s_{1},\ldots,s_{k}$ such that $n_{i}=\left|s_{i}\right|$

0: $\mathrm{opt}{\mathrm{V}^{2}_{\\!\gamma}}(S)$

1: for each $\vec{\mathcal{L}}\in\vec{\mathbb{L}}$ do

2: $D_{\vec{\mathcal{L}}}(\vec{0},\vec{0})\leftarrow 0$

3: for each $\vec{L}\not=\vec{0}$ do
$D_{\vec{\mathcal{L}}}(\vec{0},\vec{L})\leftarrow\infty$

4: for each $\vec{v}\not=\vec{0}$ do
$D_{\vec{\mathcal{L}}}(\vec{v},\vec{0})\leftarrow\infty$

5: $\vec{\gamma}\leftarrow\gamma\times\vec{\mathcal{L}}$

6: for each $\vec{0}<\vec{v}\leq\vec{n}$ in lexicographical order do

7: for each $\vec{L}\not=\vec{0}$ in lexicographical order do

8:
$D_{\vec{\mathcal{L}}}(\vec{v},\vec{L})=\min_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{v},\vec{b}\leq\vec{L}}\big{\\{}D_{\vec{\mathcal{L}}}(\vec{v}-\vec{b},\vec{L}-\vec{b})+v{\mathrm{SP}_{\\!\vec{\gamma}}}[\vec{b}\cdot
S(\vec{v})]\big{\\}}$

9: return
$\min_{\vec{\mathcal{L}}\in\vec{\mathbb{L}}}\\{D_{\vec{\mathcal{L}}}(\vec{n},\vec{\mathcal{L}})\\}$

For $k$ sequences of length $n$, Algorithm 3 needs $(2n+1)^{k\choose
2}\cdot(n+1)^{k}$ space to store the table $D_{\vec{\mathcal{L}}}$. For each
of the $(2n+1)^{k\choose 2}$ values $\vec{\mathcal{L}}\in\vec{\mathbb{L}}$,
table $D_{\vec{\mathcal{L}}}$ is recalculated. Since the computation of each
entry takes $O(2^{k}k^{2})$-time, the total time is

$O\left(2^{k}k^{2}\cdot(2n+1)^{k\choose 2}\cdot(2n+1)^{k\choose
2}(n+1)^{k}=\Big{(}1+\frac{1}{2n+1}\Big{)}^{k}(2n+1)^{k^{2}}k^{2}\right)\,.$

Therefore, if $k\leq 2n+1$, the total time is
$O\big{(}(2n+1)^{k^{2}}k^{2})\big{)}$, since
$(1+1/(2n+1))^{k}\leq(1+1/k)^{k}\leq e\leq 2.72$ is constant.

#### Existence of an alignment $A$ for a given $\vec{L}$

Consider a 3-sequence $S=s_{1},s_{2},s_{3}$ with length $\vec{n}=[4,3,5]$ and
suppose we are interested in an alignment $A$ of $S$ with induced length equal
to $\vec{\mathcal{L}}=[4,7,5]$, i.e.,
$\left|A_{\\{1,2\\}}\right|=4,\left|A_{\\{1,3\\}}\right|=7,\left|A_{\\{2,3\\}}\right|=5$.
Computing $D_{\vec{\mathcal{L}}}(\vec{v},\vec{\mathcal{L}})$ as in previous
section reveals that $D_{\vec{\mathcal{L}}}(\vec{v},\vec{\mathcal{L}})=\infty$
which means that such alignment doesn’t exist. In fact, we can check that each
symbol in sequence 2 is aligned with one symbol in the first and one symbol in
the third sequence which implies that there are at least 3 symbols of the
first sequence aligned with symbols in the third sequence. Thus,
$\left|A_{\\{1,3\\}}\right|\leq 6$. Because, computing
$D_{\vec{\mathcal{L}}}(\vec{v},\vec{\mathcal{L}})$ spends exponential time, it
would be great if we could decide whether there exists an associated alignment
with the $\vec{\mathcal{L}}$. before computing
$D_{\vec{\mathcal{L}}}(\vec{v},\vec{\mathcal{L}})$. Thus, an interesting
problem arises and we define it below.

######  Problem 4 (Existence of an alignment that is associated with an
induced length).

Given the length $\vec{n}$ of a $k$-sequence and a $k\choose 2$-vector
$\vec{L}$, decide whether there exists an alignment $A$ of $S$ such that
$\vec{L}$ is the induced length of $A$.

We denote Problem 4 by EAIL. Considering $\vec{n}$ the length of the $k$
sequence $S=s_{1},\ldots,s_{k}$, an alternative way to represent $\vec{n}$ is
through a matrix of integers $M$ that it is indexed by $\\{1,2,\ldots,k\\}$
and

$M(h,i)=\left\\{\begin{array}[]{ll}\left|s_{h}\right|&\mbox{if $h=i$},\\\
\left|s_{h}\right|+\left|s_{i}\right|-L_{hi}&\mbox{otherwise}\end{array}\right.$

i.e, $M(h,i)$ is the number of symbols in $s_{h}$ aligned with symbols in
$s_{i}$. Thus, we decide whether exists a collection of sets
$c_{1},\ldots,c_{k}$ such that $\left|c_{h}\cap c_{i}\right|=M[h,i]$, where
$c_{h}$ is a set of indices $j$ of some alignment $A$ of $S$ with
$A[h,j]\not=\texttt{-}$. This different way to see the problem is exactly
another that is known as _Recognizing Intersection Patterns_ (RIP). Notice
that the instance of RIP can be obtained in linear time and no extra space
from the instance of EAIL.

Thus, consider an example where $\vec{n}=[5,5,5]$ and $L_{12}=L_{13}=8$ and
$L_{23}=10$. In this case, EAIL returns Yes since the induced alignments by
the following alignment with $11$ columns

$\left[\begin{array}[]{ccccccccccc}s_{1}(1)&s_{1}(2)&s_{1}(3)&s_{1}(4)&s_{1}(5)&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}\\\
s_{2}(1)&s_{2}(2)&\texttt{-}&\texttt{-}&\texttt{-}&s_{2}(3)&s_{2}(4)&s_{2}(5)&\texttt{-}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\texttt{-}&s_{3}(1)&s_{3}(2)&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&s_{3}(3)&s_{3}(4)&s_{3}(5)\end{array}\right]$

respects required restrictions. On the other hand, in the alternative RIP
formulation of this instance, we want to find a collection of three sets for
the matrix

$M=\begin{array}[]{c|ccc}&1&2&3\\\ \hline\cr 1&5&2&2\\\ 2&2&5&0\\\
3&2&0&5\end{array}$

that satisfies the aforementioned property. The answer to RIP is Yes, as we
can see in Figure 4.

$c_{6}$$c_{8}$$c_{7}$$c_{3}$$c_{4}$$c_{2}$$c_{5}$$c_{9}$$c_{10}$$c_{11}$$c_{1}$

Figure 4: An instance of RIP for which the answer is Yes.

In another example, suppose that $\vec{n}=[5,5,5]$, $L_{12}=L_{13}=7$ and
$L_{23}=10$. In this case the answer is No. To check it, suppose by
contradiction that there is an alignment $A$ of a $3$-tuple
$s_{1},s_{2},s_{3}$ for this instance. Since $L_{23}=10$, we have that $s_{2}$
and $s_{3}$ has no ($5+5-10=0$) aligned symbol. Since $L_{12}=7$, then $s_{1}$
must have $5+5-7=3$ symbols aligned with $s_{2}$ that cannot be aligned with
any symbol of $s_{3}$ because $s_{2}$ and $s_{3}$ has no symbol aligned. On
the other hand, since $L_{13}=7$, we have that $s_{1}$ and $s_{3}$ must have
$3$ aligned symbols. Since $s_{1}$ has 3 symbols not alignment and 3 symbols
aligned with $s_{3}$, it follows that $s_{1}$ has at least $6$ symbols, which
is a contradiction.

Chvátal [Chv80] showed that for a special class of matrices $M$ where
$M[i,i]=3$ for every $i$, RIP is NP-complete. Therefore, we have the following
result

######  Theorem 4.1.

EAIL is NP-complete when $\left|s\right|=3$ for each sequence in $k$-sequence
and it is NP-hard if its lengths are arbitrary.

###  4.3 $\mathbf{NMSA}\text{-}3$

Let $S=s_{1},\ldots,s_{k}$ be a $k$-sequence and
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$ be an alignment of $S$. As defined
in Equation (13), ${\mathrm{V}^{3}_{\\!\gamma}}[A]$ takes into account the
lengths of induced alignments of $A$. In the optimization version of
$\mathbf{NMSA}\text{-}3$, given a $k$-tuple $S$, the task is to determine
$\mathrm{opt}{\mathrm{V}^{3}_{\\!\gamma}}(S)$ for a fixed matrix $\gamma$.

Let $N=\sum_{i}\left|s_{i}\right|$. Notice that an alignment $A$ that has
exactly only one symbol different of space in each column is such that
$\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\left|A_{(h,i)}\right|=(k-1)N$.

Here, each entry $D(\vec{v},L)$ of $D$ stores the SP-score of an alignment $A$
of the prefix $S(\vec{v})$ with the minimum SP-score such that
$\sum_{i<h}|A_{\\{i,h\\}}|=L$. The Boolean vectors $\vec{b}$ are used to
represent the contribution to the sum of the lengths of the induced
alignments. Thus, we define $\|\vec{b}\|={k\choose
2}-\sum_{h<i,b_{h}=b_{i}=0}1$. Notice that if $\vec{b}\cdot S(\vec{v})$ is the
last column of an alignment $A$ and
$L=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}|A_{\\{h,i\\}}|$ is the sum of the lengths
of the alignments induced by $A$, then the sum of the lengths of the
alignments induced by $A(1\\!:\\!\left|A\right|-1)$ is $L-\|\vec{b}\|$.
Therefore,

$D(\vec{v},L)=\left\\{\begin{array}[]{ll}0\,,&\mbox{if $\vec{v}=\vec{0}$,
$L=0$}\,,\\\ \infty\,,&\mbox{if $\vec{v}=\vec{0}$, $L\not=0$ or
$\vec{v}\not=\vec{0}$, $L=0$}\,,\\\
\displaystyle\min_{\vec{b}\in\mathcal{B}_{k},\vec{b}\leq\vec{v},\|\vec{b}\|\leq
L}\left\\{D(\vec{v}-\vec{b},L-\|\vec{b}\|)+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{v})]\right\\}\,,&\mbox{otherwise}\,.\end{array}\right.$

Algorithm 4 provides more details about the procedure for computing
$\mathrm{opt}{\mathrm{V}^{3}_{\\!\gamma}}$.

Algorithm 4

0: a $k$-sequence $S=s_{1},\ldots,s_{k}$ such that $n_{i}=\left|s_{i}\right|$

0: $\mathrm{opt}{\mathrm{V}^{3}_{\\!\gamma}}(S)$

1: $D(\vec{0},0)\leftarrow 0$

2: for each $L\not=0$ do $D(\vec{0},L)\leftarrow\infty$

3: for each $\vec{v}\not=\vec{0}$ do $D(\vec{v},0)\leftarrow\infty$

4: for each $\vec{0}<\vec{v}\leq\vec{n}$ in lexicographical order do

5: for $L\leftarrow 1,2,\ldots,N(k-1)$ do

6:
$D(\vec{v},L)\leftarrow\min_{\vec{b}\in\mathcal{B}^{{k}},\vec{b}\leq\vec{v},\|\vec{b}\|\leq
L}\big{\\{}D(\vec{v}-\vec{b},L-\|\vec{b}\|)+v{\mathrm{SP}_{\\!\gamma}}[\vec{b}\cdot
S(\vec{v})]\big{\\}}$

7: return $\min_{L}\big{\\{}D(\vec{n},L)/L\big{\\}}$

Assume that all sequences in $S$ have length $n$. In this case, table $D$ has
$(nk^{2}-nk+1)\cdot(n+1)^{k}=O(k^{2}(n+1)^{k+1})$ entries. Since the time
required to determine each entry of $D$ is $O(2^{k}k^{2})$, the running time
of Algorithm 4 is $O(2^{k}k^{2}\cdot
k^{2}(n+1)^{k+1})=O(2^{k}k^{4}(n+1)^{k+1})$.

##  5 Approximation algorithms for $\mathbf{MSA}$ and $\mathbf{NMSA}\text{-}2$

Gusfield [Gus93] described a 2-approximation algorithm for $\mathbf{MSA}$
assuming that $\gamma\in\mathbb{M}^{\mathrm{C}}$. In this section, we adapt
Gusfield’s algorithm, thus proposing a 6-approximation algorithm for
$\mathbf{MSA}$ when $\gamma\in\mathbb{M}^{\mathrm{W}}$ and a 12-approximation
algorithm for $\mathbf{NMSA}\text{-}2$ problem when
$\gamma\in\mathbb{M}^{\mathrm{N}}$.

We consider here a scoring function $v=v{\mathrm{A}_{\gamma}}$ and
$v=v{\mathrm{N}_{\gamma}}$ when $\gamma\in\mathbb{M}^{\mathrm{W}}$ and
$\gamma\in\mathbb{M}^{\mathrm{N}}$, respectively. Also, for a 2-sequence
$s,t$, define $\mathrm{opt}(s,t)=\min_{A\in\mathcal{A}_{s,t}}\\{v[A]\\}$ and
an $v$-_optimal alignment_ of $s,t$ is an alignment $A$ such
$v[A]=\mathrm{opt}(s,t)$. It follows from [AS06] that $\mathrm{opt}$ is a
metric on $\Sigma^{*}$. For a $k$-sequence $S$, define
$V[A]=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v[A_{\\{h,i\\}}]$ and
$\mathrm{OPT}(S)=\min_{A\in\mathcal{A}_{S}}v(A)$ and a _$V$ -optimal
alignment_ of $S$ is an alignment $A$ such that $V[A]=\mathrm{OPT}(S)$.

Let $c$ be an integer, $1\leq c\leq k$. A _star $X$ with center $c$_ (also
called _$c$ -star_) of the $k$-sequence $S=s_{1},\ldots,s_{k}$ is a collection
of $k-1$ alignments: $X_{h}=[s^{\prime}_{h},s^{h}_{c}]$ of $s_{h},s_{c}$ for
each $h<c$ and $X_{h}=[s^{h}_{c},s^{\prime}_{h}]$ of $s_{c},s_{h}$ for each
$h>c$. The set of all stars with center $c$ is denoted by $\mathcal{X}_{c}$.
The score of the $c$-star $X$ is $cStar(X)=\sum_{h\not=c}v[X_{h}]$ and an _$v$
-optimal star_ is one whose score is
$\mathrm{optStar}(S)=\min_{X\in\mathcal{X}_{c},c\in\mathbb{N}}\\{cStar(X)\\}$.
Notice that in a $v$-optimal $c$-star, $v(X_{h})=\mathrm{opt}(s_{h},s_{c})$ if
$h<c$ and $v(X_{h})=\mathrm{opt}(s_{c},s_{h})$ if $c<h$ and because the
symmetry property of $\mathrm{opt}$, we have

$\mathrm{optStar}(S)=\min_{c}\left\\{\sum_{h\not=c}\mathrm{opt}(s_{h},s_{c})\right\\},$

and if $\left|s\right|\leq n$ for each $s\in S$, $\mathrm{optStar}(S)$ can be
computed in $O(k^{2}n^{2})$-time when $v=v{\mathrm{A}_{\gamma}}$ and
$O(k^{2}n^{3})$-time when $v=v{\mathrm{N}_{\gamma}}$.

We say that alignment $A$ of $S$ and $c$-star $X$ are _compatible_ ($A$ is
compatible with $X$ and $X$ is compatible with $A$) in $S$ when either
$A_{\\{h,c\\}}$ (when $h<c$) or $A_{\\{c,h\\}}$ (when $c<h$) is equal to
$X_{h}$ for each $h$. Given the alignment $A$ of $S$, it is easy to obtain the
$c$-star $X$ compatible with $A$ (and there exists only one) considering fixed
$c$. On the other hand, an important known result in alignment studies from
Feng and Doolitte [FD87] is that we can find an alignment $A$ that is
compatible with a given $c$-star $X$ in $O(kn)$, where $n\leq\left|s\right|$
for each sequence $s$ in $S$. In general in this case, there exists many
compatible alignments with $X$.

It is easy to adapt the following result from Gusfield [Gus93] to a
$k$-sequence.

######  Lemma 5.1.

Given a $k$-sequence $S$,

$\mathrm{optStar}(S)\leq\frac{2}{k}\cdot\mathrm{OPT}(S)\,.$

###### Proof.

Let $X$ be a $v$-optimal star of $S$ and $c$ its center, and $A$ an
$v$-optimal alignment of $S$. Then,

$\displaystyle k\cdot\mathrm{optStar}(S)$ $\displaystyle=k\cdot
cStar(X)=\sum_{h=1}^{k}cStar(X)=\sum_{h=1}^{k}\sum_{h\not=c}v[X_{h}]=\sum_{h=1}^{k}\sum_{h\not=c}\mathrm{opt}(s_{h},s_{c})$
(18) $\displaystyle\leq
2\cdot\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\mathrm{opt}(s_{h},s_{i})$ (19)
$\displaystyle\leq
2\cdot\sum_{i=1}^{k}\sum_{h\not=i}v[A_{\\{h,i\\}}]=2\,V[A]=2\cdot\mathrm{OPT}(S)\,,$
(20)

where (18) follows from the definition of a star and from the optimality of
star $X$; (19) follows from triangle inequality of $\mathrm{opt}$; and (20)
follows from the optimality of alignment $A$.

Therefore, $\mathrm{optStar}\leq(2/k)\cdot\mathrm{opt}(S)$. ∎

Let $A=[s^{\prime},t^{\prime}]$ be an alignment of a 2-sequence $s,t$. We say
that a column $j$ is _splittable in $A$_ if $s^{\prime}(j)\not=\texttt{-}$,
$t^{\prime}(j)\not=\texttt{-}$ and
$\min\\{{\gamma}_{{t^{\prime}(j)}\rightarrow{\texttt{-}}},{\gamma}_{{s^{\prime}(j)}\rightarrow{\texttt{-}}}\\}\leq{\gamma}_{{s^{\prime}(j)}\rightarrow{t^{\prime}(j)}}$.
Let $J:=\\{j_{i}\in\mathbb{N}:1\leq
j_{1}<\cdots<j_{m}\leq\left|A\right|\mbox{and $j_{i}$ is splittable in
$A$}\\}$. An _$A$ -splitting_ is the alignment

$\left[\begin{array}[]{cccccccccc}s^{\prime}(1\\!:\\!j_{1}-1)&s^{\prime}(j_{1})&\texttt{-}&s^{\prime}(j_{1}+1\\!:\\!j_{2}-1)&s^{\prime}(j_{2})&\texttt{-}&\ldots&s^{\prime}(j_{m})&-&s^{\prime}(j_{m}+1\\!:\\!\left|A\right|)\\\
t^{\prime}(1\\!:\\!j_{1}-1)&\texttt{-}&t^{\prime}(j_{1})&t^{\prime}(j_{1}+1\\!:\\!j_{2}-1)&\texttt{-}&t^{\prime}(j_{2})&\ldots&-&t^{\prime}(j_{m})&t^{\prime}(j_{m}+1\\!:\\!\left|A\right|)\end{array}\right].$

We say that $J$ is _required to split $A$_. The following proposition is used
to check properties of an $A$-splitting.

######  Proposition 5.2.

Consider $\gamma\in\mathbb{M}^{\mathrm{W}}$ and
$\mathtt{a},\mathtt{b}\in\Sigma$. If
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}$
or
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$,
then
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$.

###### Proof.

Since $\gamma\in\mathbb{M}^{\mathrm{W}}$, we have that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}={\gamma}_{{\texttt{-}}\rightarrow{\mathtt{a}}}>0$
and
${\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}={\gamma}_{{\texttt{-}}\rightarrow{\mathtt{b}}}>0$.
Suppose that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}$.
Then,
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{b}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}$,
and we have that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$
since $\gamma\in\mathbb{M}^{\mathrm{W}}$. Assume now that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$.
It follows that
${\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{a}}}>{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{a}}}={\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$,
which implies that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\mathtt{a}}}$
since $\gamma\in\mathbb{M}^{\mathrm{W}}$. ∎

Let $X=\\{X_{1},\ldots,X_{c-1},X_{c+1},X_{k}\\}$ be a $c$-star. A
$X$-_starsplitting_ is the $c$-star
$Y=\\{Y_{1},\ldots,Y_{c-1},Y_{c+1},Y_{k}\\}$ where $Y_{j}$ is the
$X_{j}$-splitting for each $j$. The next result shows that the $v$-score of
the star $Y$ is bounded by the $v$-score of star $X$ when
$\gamma\in\mathbb{M}^{\mathrm{W}}$ and $v=v{\mathrm{A}_{\gamma}}$ or
$\gamma\in\mathbb{M}^{\mathrm{N}}$ and $v=v{\mathrm{N}_{\gamma}}$.

######  Lemma 5.3.

Let $S$ be a $k$-sequence, $X$ be a star of $S$, $Y$ be the $X$-starsplitting
and $v$ be a function to score alignments. Consider
$\gamma\in\mathbb{M}^{\mathrm{W}}$ and $v=v{\mathrm{A}_{\gamma}}$ or
$v=v{\mathrm{N}_{\gamma}}$. Then, $Y$ is also a $c$-star and

$cStar(Y)\leq 3\cdot cStar(X)\,.$

###### Proof.

Consider an alignment $X_{h}=[s^{\prime},t^{\prime}]\in X$ and a set $J$ which
is required to split $X_{h}$. Then,

$\displaystyle v{\mathrm{A}_{\gamma}}[Y_{h}]$
$\displaystyle=v{\mathrm{A}_{\gamma}}[X_{h}]+\sum_{j\in
J}\left({\gamma}_{{s^{\prime}(j)}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{t^{\prime}(j)}}-{\gamma}_{{s^{\prime}(j)}\rightarrow{t^{\prime}(j)}}\right)$
$\displaystyle\leq v{\mathrm{A}_{\gamma}}[X_{h}]+\sum_{j\in
J}\left({\gamma}_{{s^{\prime}(j)}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{t^{\prime}(j)}}\right)\leq
v{\mathrm{A}_{\gamma}}[X_{h}]+2\cdot\sum_{j\in
J}\min\\{{\gamma}_{{s^{\prime}(j)}\rightarrow{\texttt{-}}},{\gamma}_{{\texttt{-}}\rightarrow{t^{\prime}(j)}}\\}$
(21) $\displaystyle\leq v{\mathrm{A}_{\gamma}}[X_{h}]+2\cdot\sum_{j\in
J}{\gamma}_{{s^{\prime}(j)}\rightarrow{t^{\prime}(j)}},\leq
v{\mathrm{A}_{\gamma}}[X_{h}]+2\cdot v{\mathrm{A}_{\gamma}}[X_{h}]=3\cdot
v{\mathrm{A}_{\gamma}}[X_{h}]\,,$ (22)

where (21) hold because, since $\gamma\in\mathbb{M}^{\mathrm{W}}$,
${\gamma}_{{s^{\prime}(j)}\rightarrow{t^{\prime}(j)}}$ and (22) hold because
$j$ is splittable. Thus, $v{\mathrm{A}_{\gamma}}[Y_{h}]\leq 3\cdot
v{\mathrm{A}_{\gamma}}[X_{h}]$. Furthermore,

$\displaystyle v{\mathrm{N}_{\gamma}}[Y_{h}]$
$\displaystyle=\frac{v{\mathrm{A}_{\gamma}}[Y_{h}]}{\left|Y_{h}\right|}\leq\frac{3\cdot
v{\mathrm{A}_{\gamma}}[X_{h}]}{\left|Y_{h}\right|}\leq\frac{3\cdot
v{\mathrm{A}_{\gamma}}[X_{h}]}{\left|X_{h}\right|}=3\cdot
v{\mathrm{N}_{\gamma}}[X_{h}]\,.$

Hence, $v(Y_{h})\leq 3\cdot v[X_{h}]$ when .$v=v{\mathrm{A}_{\gamma}}$ or
$v=v{\mathrm{A}_{\gamma}}$ and $\gamma\in\mathbb{M}^{\mathrm{W}}$ which
implies that

$cStar(Y)=\sum_{h\not=c}v[Y_{h}]\leq 3\cdot\sum_{h\not=c}v[X_{h}]=3\cdot
cStar(X)\,.$

∎

Notice that the time consumption for computing an $X$-splitting from $X$ is
$O(kn)$ when $\left|s\right|\leq n$ for each $s\in S$.

Considering a star $X$ with center $c$ of $S=s_{1},\ldots,s_{k}$, there can
exist many compatible alignments with a star $Y$ which is a $X$-splitting. Let
CompatibleAlign be a subroutine that receives the star $Y$ and returns an
alignment $A$ compatible with $Y$. It is quite simple: if symbols
$s_{h}(j_{1})$ and $s_{c}(j_{2})$ are aligned in $X_{h}$, they are also
aligned in $A$. Otherwise, $s_{h}(j)$ aligns only with - in $A$. This property
is enough to guarantee the approximation factor of $\mathbf{MSA}$ and
$\mathbf{NMSA}\text{-}2$. As an example, for
$S=\mathtt{a}\mathtt{a}\mathtt{a},\mathtt{b}\mathtt{b}\mathtt{b}\mathtt{b}\mathtt{b},\mathtt{c}\mathtt{c},\mathtt{d}\mathtt{d}\mathtt{d},\mathtt{e}\mathtt{e}\mathtt{e}\mathtt{e}\mathtt{e}\mathtt{e}$
and

$X=\left\\{\left[\begin{array}[]{cccc}\mathtt{a}&\mathtt{a}&\mathtt{a}&\texttt{-}\\\
\texttt{-}&\mathtt{d}&\mathtt{d}&\mathtt{d}\\\
\end{array}\right],\left[\begin{array}[]{cccccc}\mathtt{b}&\mathtt{b}&\texttt{-}&\mathtt{b}&\mathtt{b}&\mathtt{b}\\\
\texttt{-}&\mathtt{d}&\mathtt{d}&\texttt{-}&\texttt{-}&\mathtt{d}\end{array}\right],\left[\begin{array}[]{ccc}\mathtt{c}&\mathtt{c}&\texttt{-}\\\
\mathtt{d}&\mathtt{d}&\mathtt{d}\end{array}\right],\left[\begin{array}[]{ccccccc}\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{d}&\mathtt{d}&\mathtt{d}&\texttt{-}\\\
\mathtt{e}&\mathtt{e}&\mathtt{e}&\mathtt{e}&\texttt{-}&\mathtt{e}&\mathtt{e}\end{array}\right]\right\\}$

a star with center $4$, we obtain the alignment

$\left[\begin{array}[]{ccccccccccc}\mathtt{a}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{a}&\mathtt{a}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\mathtt{b}&\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{b}&\texttt{-}&\mathtt{b}&\mathtt{b}&\mathtt{b}&\texttt{-}\\\
\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{c}&\mathtt{c}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}\\\
\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{d}&\mathtt{d}&\texttt{-}&\texttt{-}&\mathtt{d}&\texttt{-}\\\
\texttt{-}&\texttt{-}&\mathtt{e}&\mathtt{e}&\mathtt{e}&\mathtt{e}&\texttt{-}&\texttt{-}&\texttt{-}&\mathtt{e}&\mathtt{e}\end{array}\right]\,.$

Let
$Q_{\max}:=\max_{\mathtt{a}\in\Sigma}\\{{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}},{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{a}}}\\}$
and consider the following result.

######  Proposition 5.4.

Let $S$ be a $k$-sequence, $X$ be a star of $S$ with center $c$ and $Y$ be the
$X$-starsplitting. Assume that $\gamma\in\mathbb{M}^{\mathrm{W}}$ and that
$\textsc{Compati\\-bleAlign}(Y)$ returns
$A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$. If $h\not=c$ and $i\not=c$, we
have that

  1. (i)

${\gamma}_{{s^{\prime}_{h}(j)}\rightarrow{s^{\prime}_{i}(j)}}\leq{\gamma}_{{s^{\prime}_{h}(j)}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{s^{\prime}_{i}(j)}}$
for each $j=1,\ldots,\left|A\right|$, and

  2. (ii)

$v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]\leq 2\cdot Q_{\max}$.

###### Proof.

Assume that $s^{\prime}_{h}(j)=\mathtt{a},s^{\prime}_{i}(j)=\mathtt{b}$ and
$s^{\prime}_{c}(j)=\mathtt{c}$.

First we show that (i)
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}+{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}$
for each $j=1,\ldots,\left|A\right|$, by analyzing all possible values of
$\mathtt{a},\mathtt{b}$ and $\mathtt{c}$. The case when
$\mathtt{a}=\texttt{-}$ or $\mathtt{b}=\texttt{-}$ can be checked by
definition of $\gamma\in\mathbb{M}^{\mathrm{W}}$. Thus, we assume that
$\mathtt{a}\not=\texttt{-}$ and $\mathtt{b}\not=\texttt{-}$, which implies by
the alignment construction in CompatibleAlign, that
$\mathtt{c}\not=\texttt{-}$. Since $\mathtt{a}\not=\texttt{-}$,
$\mathtt{b}\not=\texttt{-}$, $\mathtt{c}\not=\texttt{-}$ and $Y$ is a
starsplitting, we have that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{a}}}$,
${\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}$
and, since $\gamma\in\mathbb{M}^{\mathrm{W}}$,
${\gamma}_{{\texttt{-}}\rightarrow{\mathtt{b}}}={\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}$.
Since
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{a}}}$,
it follows from Proposition 5.2 that
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}$.
Hence,
${\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}+{\gamma}_{{\texttt{-}}\rightarrow{\mathtt{b}}}>{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}+{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}$,
which implies from the definition of $\mathbb{M}^{\mathrm{W}}$ that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}+{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}$.

Finally, we show (ii). Here, it is enough to prove that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}\leq 2\cdot Q_{\max}$ for each
column $[\mathtt{a},\mathtt{b}]$ of $v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]$.
Again, the case when $\mathtt{a}=\texttt{-}$ or $\mathtt{b}=\texttt{-}$ can
easily be checked. Thus, assume that $\mathtt{a}\not=\texttt{-}$ and
$\mathtt{b}\not=\texttt{-}$ which implies by construction that
$\mathtt{c}\not=\texttt{-}$. Since $Y$ is a splitting, it follows that
${\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{a}}}<{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}$
and
${\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}<{\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}$.
Since
${\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{a}}}<{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}$,
it follows from Preposition 5.2 that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}<{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}$.
It follows from (i) that
${\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{b}}}\leq{\gamma}_{{\mathtt{a}}\rightarrow{\mathtt{c}}}+{\gamma}_{{\mathtt{c}}\rightarrow{\mathtt{b}}}<{\gamma}_{{\mathtt{a}}\rightarrow{\texttt{-}}}+{\gamma}_{{\mathtt{b}}\rightarrow{\texttt{-}}}\leq
Q_{\max}+Q_{\max}=2\cdot Q_{\max}$. Consequently, we have that
$v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]=v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]/\left|A_{\\{h,i\\}}\right|\leq
2\cdot Q_{\max}\left|A_{\\{h,i\\}}\right|/\left|A_{\\{h,i\\}}\right|=2\cdot
Q_{\max}$. ∎

######  Lemma 5.5.

Let $S$ be a $k$-sequence, $X$ a star of $S$ with center $c$, $Y$ a
$X$-starsplitting and $A=\textsc{CompatibleAlign}(Y)$. Then,

  1. (i)

$v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]\leq
v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]$
when $\gamma\in\mathbb{M}^{\mathrm{W}}$ and

  2. (ii)

$v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]\leq
2\cdot\Big{(}v{\mathrm{N}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{N}_{\gamma}}[A_{\\{c,i\\}}]\Big{)}$
when $\gamma\in\mathbb{M}^{\mathrm{N}}$,

for each $h<i$, $h\not=c$, $i\not=c$.

###### Proof.

Consider $A=[s^{\prime}_{1},\ldots,s^{\prime}_{k}]$, $h,i\in\mathbb{N}$ and
$J=\\{j:s^{\prime}_{c}(j)\not=\texttt{-}\mbox{ and
}s^{\prime}_{h}(j)=s^{\prime}_{i}(j)=\texttt{-}\\}$. Then,

$\displaystyle v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]+\sum_{j\in
J}({\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}})$
$\displaystyle=\sum_{j\not\in
J}{\gamma}_{{s^{\prime}_{h}(j)}\rightarrow{s^{\prime}_{i}(j)}}+\sum_{j\in
J}({\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}})$
$\displaystyle\leq\sum_{j\not\in
J}\left({\gamma}_{{s^{\prime}_{h}(j)}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{s^{\prime}_{i}(j)}}\right)+\sum_{j\in
J}({\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}})$
$\displaystyle=v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]\,,$

where the inequality holds due to Proposition 5.4. Therefore,

$\displaystyle v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]$ $\displaystyle\leq
v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]-\sum_{j\in
X}({\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}})\,.$
(23)

Since $\gamma\in\mathbb{M}^{\mathrm{W}}$, we have that
${\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}},{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}}>0$.
It follows from (23) that (i) is proven.

For (ii), observe that, by definition of $\mathbb{M}^{\mathrm{W}}$, we have
that

$Q_{\max}=\max_{\sigma\in\Sigma}\big{\\{}{\gamma}_{{\sigma}\rightarrow{\texttt{-}}},{\gamma}_{{\texttt{-}}\rightarrow{\sigma}}\big{\\}}=\max_{\sigma\in\Sigma}\big{\\{}{\gamma}_{{\sigma}\rightarrow{\texttt{-}}}\big{\\}}\leq
2\,{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}}={\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}}$

for every $j$. Furthermore, following these statements, we have that

$\displaystyle v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]$
$\displaystyle=\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]}{|A_{\\{h,i\\}}|}$
$\displaystyle\leq\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]+2\cdot
Q_{\max}\left|J\right|}{|A_{\\{h,i\\}}|+\left|J\right|}\;\leq\;2\cdot\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]+Q_{\max}\left|J\right|}{|A_{\\{h,i\\}}|+\left|J\right|}$
(24) $\displaystyle\leq
2\cdot\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]-\sum_{j\in
J}({\gamma}_{{\texttt{-}}\rightarrow{s^{\prime}_{c}(j)}}+{\gamma}_{{s^{\prime}_{c}(j)}\rightarrow{\texttt{-}}})+Q_{\max}\left|J\right|}{|A_{\\{h,i,c\\}}|-\left|J\right|+\left|J\right|}$
(25) $\displaystyle\leq
2\cdot\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]-Q_{\max}\left|J\right|+Q_{\max}\left|J\right|}{|A_{\\{h,i,c\\}}|-\left|J\right|+\left|J\right|}=2\cdot\left(\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]}{|[A_{\\{h,i,c\\}}]|}+\frac{v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]}{|[A_{\\{h,i,c\\}}]|}\right)$
(26) $\displaystyle\leq
2\cdot\left(\frac{v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]}{|A_{\\{h,c\\}}|}+\frac{v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]}{|A_{\\{c,i\\}}|}\right)=2\cdot\Big{(}v{\mathrm{N}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{N}_{\gamma}}[A_{\\{c,i\\}}]\Big{)}\,,$
(27)

where the first inequality of (24) is a consequence of Proposition 5.4 and the
second inequality follows since every entry of $\gamma$ is nonnegative, (25)
follows from (23) and from $|A_{\\{h,i\\}}|=|A_{\\{h,i,c\\}}|-\left|J\right|$,
(26) follows as a consequence of $\gamma\in\mathbb{M}^{\mathrm{N}}$, and (27)
follows as a consequence of $|A_{\\{h,c\\}}|\leq|A_{\\{h,i,c\\}}|$ and
$|A_{\\{c,i\\}}|\leq|A_{\\{h,i,c\\}}|$. ∎

Observe now that the running time of CompatibleAlign is $O(k^{2}n)$.

Algorithm 5

0: $k$-sequence $S$

0: $v[A]$ such that $A\in\mathcal{A}_{S}$
and$v{\mathrm{SP}_{\\!\gamma}}[A]\leq
6\cdot\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$ if $v=v{\mathrm{A}_{\gamma}}$
and $\gamma\in\mathbb{M}^{\mathrm{W}}$,
and${\mathrm{V}^{2}_{\\!\gamma}}[A]\leq
12\cdot\mathrm{opt}{\mathrm{NSP}^{2}_{\\!\gamma}}(S)$ if
$v=v{\mathrm{N}_{\gamma}}$ and $\gamma\in\mathbb{M}^{\mathrm{N}}$.

1: Let $X$ be a $v$-optimal star of $S$ with center $c$

2: Compute the $X$-splitting $Y$

3: $A\leftarrow\textsc{CompatibleAlign}(Y)$

4: return $v[A]$

######  Theorem 5.6.

Let $S$ be a $k$-sequence and $\gamma$ be a scoring matrix. Then, Algorithm 5
computes $v[A]$ correctly,

  1. (i)

in $O(k^{2}n^{2})$-time such that $v{\mathrm{SP}_{\\!\gamma}}[A]\leq
6\cdot\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)$, if $v=v{\mathrm{A}_{\gamma}}$
and $\gamma=\mathbb{M}^{\mathrm{W}}$,

  2. (ii)

in $O(k^{2}n^{3})$-time such that ${\mathrm{V}^{2}_{\\!\gamma}}[A]\leq
12\cdot\mathrm{opt}{\mathrm{NSP}^{2}_{\\!\gamma}}(S)$, if
$v=v{\mathrm{N}_{\gamma}}$ and $\gamma\in\mathbb{M}^{\mathrm{N}}$ ,

where $A$ is the alignment of $S$ computed by the algorithm.

###### Proof.

Clearly, the value returned by the Algorithm 5 is a score of an alignment of
$S$.

We show then that the approximation factor is as expected. Let $c$ be a center
of the stars $X$ and $Y$ found in the first two steps of Algorithm 5. Notice
then that

$\displaystyle\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\big{(}v[A_{\\{h,c\\}}]+v[A_{\\{c,i\\}}]\Big{)}$
$\displaystyle=(k-1)\cdot cStar(Y)$ (28) $\displaystyle\leq 3\cdot(k-1)\cdot
cStar(D(X))$ (29) $\displaystyle\leq
3\cdot(k-1)\cdot\frac{2}{k}\cdot\mathrm{opt}(S)=6\cdot\frac{k-1}{h}\cdot\mathrm{opt}(S)\leq
6\cdot\mathrm{opt}(S)\,,$ (30)

where the equality (28) follows since $c$ is the center of star $Y$ which is a
compatible with alignment $A$, (29) follows from Lemma 5.3 and (30) follows
from Lemma 5.1.

Suppose then that $v=v{\mathrm{A}_{\gamma}}$ and
$\gamma\in\mathbb{M}^{\mathrm{W}}$. Thus,

$\displaystyle v{\mathrm{SP}_{\\!\gamma}}[A]$
$\displaystyle=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{A}_{\gamma}}[A_{\\{h,i\\}}]$
$\displaystyle\leq\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\Big{(}v{\mathrm{A}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{A}_{\gamma}}[A_{\\{c,i\\}}]\Big{)}\leq
6\cdot\mathrm{opt}{\mathrm{SP}_{\\!\gamma}}(S)\,,$

where the first inequality follows from Lemma 5.5 and the second follows from
Equation (30).

Suppose now that $v=v{\mathrm{N}_{\gamma}}$ and
$\gamma\in\mathbb{M}^{\mathrm{N}}$. Thus,

$\displaystyle{\mathrm{V}^{\gamma}_{\\!2}}[A]$
$\displaystyle=\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}v{\mathrm{N}_{\gamma}}[A_{\\{h,i\\}}]$
$\displaystyle\leq
2\cdot\sum_{h=1}^{k-1}\sum_{i=h+1}^{k}\Big{(}v{\mathrm{N}_{\gamma}}[A_{\\{h,c\\}}]+v{\mathrm{N}_{\gamma}}[A_{\\{c,i\\}}]\Big{)}$
$\displaystyle\leq 2\cdot
6\cdot\mathrm{opt}{\mathrm{NSP}^{\gamma}_{\\!2}}(S)=12\cdot\mathrm{opt}{\mathrm{NSP}^{\gamma}_{\\!2}}(S)\,,$

where, similarly, the first inequality follows from Lemma 5.5 and the second
follows from Equation (30).

The time required to find an optimal $v$-star is the time to compute the
pairwise alignments of $S$, which is ${k\choose 2}O(n^{2})$ if
$v=v{\mathrm{A}_{\gamma}}$ and it is ${k\choose 2}O(n^{3})$ if
$v=v{\mathrm{N}_{\gamma}}$. Additionally, we have to consider the time to
determine the optimal star, which is $O(k^{2})$, implying that the time
required to compute line 1 of Algorithm 5 is ${k\choose
2}O(n^{2})+O(k^{2})=O(k^{2}n^{2})$ if $v=v{\mathrm{A}_{\gamma}}$ and
${k\choose 2}O(n^{3})+O(k^{2})=O(k^{2}n^{3})$ if $v=v{\mathrm{N}_{\gamma}}$.
The time spent to compute lines 2 and 3 are $O(kn)$ and $O(k^{2}n)$,
respectively, and to compute line 4 is $O(k^{3}n)$, since we have to compute
the score of ${k\choose 2}=O(k^{2})$ pairwise alignments of length $O(kn)$.
Therefore, the total time spent by the algorithm is $O(k^{2}n^{2}+k^{3}n)$ if
$v=v{\mathrm{A}_{\gamma}}$ and $O(k^{2}n^{3}+k^{3}n)$ if
$v=v{\mathrm{N}_{\gamma}}$. ∎

##  6 Conclusion and future work

We presented and discussed multiple aspects of normalized multiple sequence
alignment (NMSA). We defined three new criteria for computing normalized
scores when aligning multiple sequences, showing the NP-hardness and exact
algorithms for solving the $\mathbf{NMSA}\text{-}z$ given each criterion
$z=1,2,3$. In addition, we adapted an existing 2-approximation algorithm for
$\mathbf{MSA}$ when the scoring matrix $\gamma$ is in the classical class
$\mathbb{M}^{\mathrm{C}}$, leading to a 6-approximation algorithm for
$\mathbf{MSA}$ when $\gamma$ is in the broader class
$\mathbb{M}^{\mathrm{W}}\supseteq\mathbb{M}^{\mathrm{C}}$ and to a
12-approximation for $\mathbf{NMSA}\text{-}2$ when $\gamma$ is in
$\mathbb{M}^{\mathrm{N}}\subseteq\mathbb{M}^{\mathrm{W}}$, a slightly more
restricted class such that the cost of deletion for any symbol is at most
twice the cost for any other. We summarize these contributions in
Table=reftableconclusion.

problems | time of exact algorithms | time of approximation algorithm
---|---|---
$\mathbf{MSA}$ | — | $O(k^{2}n^{2}+k^{3}n)$
$\mathbf{NMSA}\text{-}1$ | $O(2^{k}k^{3}(n+1)^{k+1})$ | —
$\mathbf{NMSA}\text{-}2$ | $O\left(\left(1+\frac{1}{2n+1}\right)^{k}(2n+1)^{k^{2}}k^{2}\right)$ | $O(k^{2}n^{2}+k^{3}n)$
$\mathbf{NMSA}\text{-}3$ | $O(2^{k}k^{4}(n+1)^{k+1})$ | —
Table 1: We are considering a $k$-sequence where each sequence has maximum
length of $n$; all the problem decision version are NP-complete.

This work is an effort to expand the boundaries of multiple sequence alignment
algorithms towards normalization, an unexplored domain that can produce
results with higher accuracy in some applications. In future work, we will
implement our algorithms in order to verify how large are the sequences our
algorithms are able to handle. Also, we plan to perform practical experiments,
measuring how well alignments provided by our algorithms and other MSA
algorithms agree with multiple alignment benchmarks. In addition, we intend to
measure the accuracy of phylogenetic tree reconstruction based on our
alignments for simulated and real genomes. Finally, we will work on heuristics
and parallel versions of our algorithms in order to faster process large
datasets.

## References

  * [AE99] A. N. Arslan and Ö. Egecioglu.  An efficient uniform-cost normalized edit distance algorithm.  In Proc. of SPIRE, pages 9–15. IEEE, 1999.
  * [AG97] A. Apostolico and Z. Galil.  Pattern Matching Algorithms.  Oxford University Press, 1997.
  * [AKO10] A. Andoni, R. Krauthgamer, and K. Onak.  Polylogarithmic approximation for edit distance and the asymmetric query complexity.  In Proc. of FOCS, pages 377–386. IEEE, 2010.
  * [AS06] E. Araujo and J. Soares.  Scoring matrices that induce metrics on sequences.  In Proc. of LATIN, pages 68–79, 2006.
  * [AT00] A. Abbott and A. Tsay.  Sequence analysis and optimal matching methods in sociology: Review and prospect.  Sociol Method Res, 29(1):3–33, 2000.
  * [BI18] A. Backurs and P. Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  SIAM J Comput, 47(3):1087–1097, 2018.
  * [BL02] R. Barzilay and L. Lee.  Bootstrapping lexical choice via multiple-sequence alignment.  In Proc. of EMNLP, pages 164–171, USA, 2002. Association for Computational Linguistics.
  * [CB99] J. A. Cuff and G. J. Barton.  Evaluation and improvement of multiple sequence methods for protein secondary structure prediction.  Proteins, 34(4):508–519, 1999.
  * [CDG+20] D. Chakraborty, D. Das, E. Goldenberg, M. Kouckỳ, and M. Saks.  Approximating edit distance within constant factor in truly sub-quadratic time.  J ACM, 67(6):1–22, 2020.
  * [Chv80] V. Chvátal.  Recognizing intersection patterns.  Ann Discrete Math, 8:249–251, 1980.
  * [CL88] H. Carrillo and D. Lipman.  The multiple sequence alignment problem in biology.  SIAM J Appl Math, 48(5):1073–1082, 1988.
  * [CLZU03] Maxime Crochemore, Gad M Landau, and Michal Ziv-Ukelson.  A subquadratic sequence alignment algorithm for unrestricted scoring matrices.  SIAM journal on computing, 32(6):1654–1673, 2003.
  * [Eli06] I. Elias.  Settling the intractability of multiple alignment.  J Comput Biol, 13(7):1323–1339, 2006.
  * [FD87] D.-F. Feng and R. F. Doolittle.  Progressive sequence alignment as a prerequisitetto correct phylogenetic trees.  J Mol Evol, 25(4):351–360, 1987.
  * [Gus93] D. Gusfield.  Efficient methods for multiple sequence alignment with guaranteed error bounds.  Bull Math Biol, 55(1):141–154, 1993.
  * [HAR09] W. Haque, A. Aravind, and B. Reddy.  Pairwise sequence alignment algorithms: A survey.  In Proc. of ISTA, pages 96–103. ACM Press, 2009.
  * [HTHI95] M. Hirosawa, Y. Totoki, M. Hoshida, and M. Ishikawa.  Comprehensive study on iterative algorithms of multiple sequence alignment.  Bioinformatics, 11(1):13–18, 1995.
  * [Lev66] V. I. Levenshtein.  Binary codes capable of correcting deletions, insertions and reversals.  Dokl. Akad. Nauk., 10(8):707–710, 1966.
  * [MP80] W. J. Masek and M. S. Paterson.  A faster algorithm computing string edit distances.  J Comput Syst Sci, 20(1):18–31, 1980.
  * [MV93] A. Marzal and E. Vidal.  Computation of normalized edit distance and applications.  IEEE T Pattern Anal, 15(9):926–932, 1993.
  * [NW70] S. B. Needleman and C. D. Wunsch.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  J Mol Biol, 48(3):443–453, 1970.
  * [OR06] T. H. Ogden and M. S. Rosenberg.  Multiple sequence alignment accuracy and phylogenetic inference.  Syst Biol, 55(2):314–328, 2006.
  * [Sel74] P. H. Sellers.  On the theory and computation of evolutionary distances.  SIAM J Appl Math, 26(4):787–793, 1974.
  * [SH14] F. Sievers and D. G. Higgins.  Clustal Omega.  Curr Protoc Bioinfo, 48(1):3.13.1–3.13.16, 2014.
  * [SWD+11] F. Sievers, A. Wilm, D. Dineen, T. J. Gibson, K. Karplus, W. Li, R. Lopez, H. McWilliam, M. Remmert, J. Söding, J. D. Thompson, and D. G. Higgins.  Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega.  Mol Syst Biol, 7(1):539, 2011.
  * [TPP99] J. D. Thompson, F. Plewniak, and O. Poch.  A comprehensive comparison of multiple sequence alignment programs.  Nucleic Acids Res, 27(13):2682–2690, 1999.
  * [VMA95] E. Vidal, A. Marzal, and P. Aibar.  Fast computation of normalized edit distances.  IEEE T Pattern Anal, 17(9):899–902, 1995.
  * [WLXZ15] X.-D. Wang, J.-X. Liu, Y. Xu, and J. Zhang.  A survey of multiple sequence alignment techniques.  In Proc. of ICIC, pages 529–538. Springer, 2015.
  * [WOHN06] I. M. Wallace, O. O’Sullivan, D. G. Higgins, and C. Notredame.  M-Coffee: combining multiple sequence alignment methods with T-Coffee.  Nucleic Acids Res, 34(6):1692–1699, 2006.