Definitions

Definition 1.3   The optimal pairwise alignment OPA(s₁, s₂) of two sequences s₁, s₂ is an alignment with the maximum score where a probabilistic scoring method [5,14] is used. We refer to a pairwise alignment of two sequences s₁, s₂ with $\langle s_1, s_2 \rangle$.

Usually the optimal score is determined via standard dynamic programming [29,16]. 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 [2].

Definition 1.4   A 1-PAM unit is the amount of evolution which will change, on average, $1\%$ of the amino acids. In mathematical terms, this is expressed as a matrix M such that $\sum_{i=1}^{20} f_i (1 - M_{ii} ) = 0.01$, where f_i is the frequency of the i^th amino acid and M_ij is the probability that an amino acid i mutates into an amino acid j at one PAM distance [5]. The function PAM(s1, s2) is the PAM distance of two sequences s_i, s₂ that maximizes the OPA score.

Definition 1.5   A Tree scoring function is a function $F: T \rightarrow I \!\! R$.

Definition 1.6   Let $\cal{T}$ be the set of all possible trees that can be generated for a given set of sequences $S=\{s_1, s_2, .., s_n\}$. The optimal tree $\bar{T} \in \cal{T}$ is a tree such that $F(\bar{T}) = \min\limits_{T \in \cal{T}}$ F(T). (For some scoring functions we use the maximum instead of the minimum.)