previous section previous page next page next section
CMB

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 or 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