Scoring Functions

In all our examples, the scoring function $F(\mbox{\rm A})$ of an MSA is similar to the sum-of-pairs measure [21], except that we do not add all scores of all pairwise alignments, but only the scores of the pairwise alignments in a circular order C(S) with respect to the associated evolutionary tree. Such an order can be determined without the knowledge of an evolutionary tree. For a detailed explanation see [22].

Definition 1.5   The score of the induced MSA-derived pairwise alignment
MPA(a_i, a_j) of two sequences $a_i, a_j \in \mbox{\rm A}$ is the score of the alignment of the two strings a_i and a_j, where any scoring function for pairwise alignments can be used. Opposing gaps may be removed.

Usually the optimal score for pairwise alignments is determined via standard dynamic programming [18,19]. An affine gap cost is used according to the formula $a + l \cdot b$, where a is a fixed gap cost, l is the length of the gap and b is the incremental cost [20]. The circular sum score $CS(\mbox{\rm A})$ of an MSA $\mbox{\rm A}$ is the sum of MPA scores in circular order C divided by two:

Definition 1.6   The score $CS(\mbox{\rm A})$ of an MSA $\mbox{\rm A}$ is defined as: $CS(\mbox{\rm A}) = \frac{1}{2} \sum\limits_{i=1}^{n} MPA(a_{C_{i}}, a_{C_{i+1}})$ where C_n+1 = C₁, and C is a circular order with respect to the evolutionary tree of $\mbox{\rm A}$.

Whenever we use the term score of an MSA, we mean the CS score. The term "best possible score" of an MSA refers to the CS score using the optimal scores of the pairwise alignments instead of the MPA scores. For a better explanation see [22]. In the following we classify the major problems that can arise when MSAs are built. We then present an algorithm that is derived from biological observation to improve MSAs. Then we show how to reconstruct an evolutionary tree from the gaps. Furthermore, we show how the solution of a vertex cover problem can be used for resolving conflicts that can arise when constructing trees from gaps.