(Weighted) Sum of pairs ((W)SOP)

Die gebräuchlichste Kostenfunktion ist sicherlich die (weighted) sum of pairs     Kostenfunktion, in der man die (gewichtete) Summe aus den Kosten der paarweisen Projektionen berechnet.

$$c(A)=\sum_{h=1}^{k-1}\sum_{i=h+1}^k c(A_{i,j})$$

oder, wenn man d(-,-)=0 setzt:

$$c(A)=\sum_{h=1}^{l}\sum_{i=1}^{k-1}\sum_{j=i+1}^k d(A[h,i],A[h,j])$$

Beispiel 10   Sei d(A,B)=2 für $A\neq B$, d(A,-)=d(-,A)=1 für $A\neq '-'$, 0 sonst.

             S1 = - G C T G A T A T A A C T
             S2 = G G G T G A T - T A G C T
             S3 = A G C G G A - A C A C C T
                  -------------------------
Spaltenwert:      4 0 4 4 0 0 2 2 4 0 6 0 0 = 26