Online Lectures on Bioinformatics

Algorithms for SPoptimal multiple alignmentsReduction of search spaceFollowing an approach of Carrillo and Lipman [CL88], it's possible to reduce the search space in the ndimensional editgraph. The concept of the forwardbackwardmatrix is used once more: Each 'cell' of the forwardbackward 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):
M_{ij}^{(x,y)} = D_{ij}^{(x,y)} + R_{ij}^{(x,y)}
Although the alignmentscore between two sequences in an optimal multiple alignment is not necessarily optimal in the pairwise sense, a lower bound L_{xy} 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 alignmentscore of a pair of sequences allows to exclude certain cells in the forwardbackwardmatrix from being candidates for an optimal multiple alignment of all sequences, and thus the ndimensional search space is reduced by eliminating regions where
M_{ij}^{(x,y)} < L_{xy}
Note:
L_{x,y} as defined below is a lower bound for the pairwise alignment score of an optimal multiple alignment between the two sequences x and y:
Comments are very welcome. luz@molgen.mpg.de 