How to find gaps without gap penalty?

Sequence alignment is always based (i) on the substitution weight matrix (that has some biological motivation) and (ii) on the gap penalties (which are pre-determined from experience, even in the absence of any guarantee that they must be the same for all sequences). Our approach to constructing alignments without any pre-determined gap penalties is based on the following observation.

The gaps in the "random" and in the related sequences play fundamentally different roles. If two random sequences are bing aligned, a new gap does not usually lead to a considerable gain in the number of matches. On the other hand, correct gaps in related biological sequences reconstitute matching of rather long similar segments and, therefore, the number of matches increases substantially. Thus, an alignment with all "biologically correct" gaps corresponds to the "break point" of the plot which shows the maximal total substitution weight S(g) as a function of the allowed number of gaps g = 0, 1, ....

The approach is tested on artificial (random) sequences, on the protein sequences of different level of similarity, and on comparison of protein sequences with profiles. For the tested proteins, the constructed alignments are very close to those based on their 3D-structures. The algorithm computing the S(g) values and corresponding alignments is based on the dynamic programming applied to the vector alignment weights rather than usual scalar weights (here p is a gap penalty).