Online Lectures on Bioinformatics

Suboptimal AlignmentsStabilityDefinition: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 alignmentspans 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 