Online Lectures on Bioinformatics

navigation

Suboptimal Alignments

Stability

Definition:
A residue pair

is called

if for all other points

there exists a path in the type I graph either from (i,j) to (k,l) or from (k,l) to (i,j). Let the set of

-stable points be called

.

Theorem:

is the intersection of the points on the paths corresponding to all

-suboptimal alignments.
Proof: It is easy to see that

. To prove this let

. We have to show that

, i.e. that

there exists a path connecting the two points in the type I graph. Clearly

. Therefore

and due to

there exists a path in the type I graph linking (i,j) and (k,l). This establishes

. To see the theorem let

and choose some

-suboptimal alignment. Let the score of this alignment be

. Then

and therefore for all

there exists a path in the type I graph between (i,j) and (k,l). Assume now the

-suboptimal alignment would not contain (i,j). Then the alignment had to contain a point (m,n) which lies in the area of the path matrix that is not linked to (i,j), i.e. either

due to the definition of a type I alignment. But being part of an

-suboptimal alignment

. (i,j) was shown to be in

which means there has to exist a path linking it to any point in

, including (m,n) which leads to a contradiction. The fact that if a point is an element of every path corresponding to an

-suboptimal alignment it also is in

, is a direct consequence of the definitions of the type I alignment and the

-stable points. q.e.d.
To allow for quantitative comparison between alignment-spans in stable regions and the correct, structural alignment we need the following
Corollary: Given any

and any optimal type I alignment. Then

is a subset of the pairs in the optimal type I alignment.
Remark: It should be noted that there always exists an

, such that

because S_s comprises all matrix points.

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