previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation

Algorithms for SP-optimal multiple alignments


Reduction of search space

Following an approach of Carrillo and Lipman [CL88], it's possible to reduce the search space in the n-dimensional edit-graph.

The concept of the forward-backward-matrix is used once more: Each 'cell' of the forward-backward matrix of two sequences contains the total score of an alignment, which is optimal under the assumption that the two letters belonging to the cell have to be matched in the alignment (see also a previous section):


Mij(x,y) = Dij(x,y) + Rij(x,y)

Although the alignment-score between two sequences in an optimal multiple alignment is not necessarily optimal in the pairwise sense, a lower bound Lxy for this score can be specified by only computing pairwise optimal alignments and a heuristic alignment (see below). Having specified a lower bound for the alignment-score of a pair of sequences allows to exclude certain cells in the forward-backward-matrix from being candidates for an optimal multiple alignment of all sequences, and thus the n-dimensional search space is reduced by eliminating regions where


Mij(x,y) < Lxy

Note:

1.

\begin{eqnarray*}\mathcal{S}(A) & = & \mathcal{S}(\vec x_1,\ldots,\vec x_N) \\ ... ...w(x_j^{(l)},x_j^{(k)}) \\ & = & \sum_{l<k} \mathcal{S}(A_{l,k}) \end{eqnarray*}


2.
SP-alignment-score

\begin{displaymath}\Bigg\uparrow \begin{array}{lllll} \sum_{l<k} \mathcal{S}^{op... ...{heur}) & \textrm{score of a heuristic alignment} \end{array} \end{displaymath}

$\underline{\smash{\hbox{Theorem:}}}$

Lx,y as defined below is a lower bound for the pairwise alignment score of an optimal multiple alignment $ \mathcal{S}(A^{opt}_{x,y}) $ between the two sequences x and y:


\begin{displaymath}L_{x,y} \ := \ \mathcal{S}(A^{heur}) \ - \sum_{ \begin{array... ...(s^{(l)},s^{(k)}) \quad \leq \quad \mathcal{S}(A^{opt}_{x,y}) \end{displaymath}

$\underline{\smash{\hbox{Proof:}}}$


\begin{eqnarray*}\mathcal{S}(A^{heur}) & \leq & \mathcal{S}^{opt}(s^{(1)},\ldots... ...) \end{array}} \mathcal{S}^{opt}(s^{(l)},s^{(k)}) \qquad \Box \end{eqnarray*}




Comments are very welcome.
luz@molgen.mpg.de