DPマッチングを用いた生物間の距離（人と猿は、人と魚より距離が近い）の算出
前提：
１．距離をアミノ酸の配列で計る
２．長い時間の間にアミノ酸が置き換わる（例えばcdefgからcdsfgに）距離２とする
３．長い時間の間に脱落が起こる（例えばcdefgがcd*fgになる）距離１とする（*は脱落）
（言葉で言うと、置換より脱落が起こりやすい、ってこと）
課題：
２つのアミノ酸配列の距離を出すとき２つを並べて比較しますが、並べ方が色々考えられます。
例えば、abcc と aebcを並べて比較する時、
(1) abcc aebc と並べるとbとe、cとbが置換されたことになり２か所置換なの距離２＊２＝４）
(2) a*bcc aebc* と並べることもできます（距離は脱落１＋１で距離２）。
このように並べ方で距離が違ってきます。
長い間にどのような置換や脱落が起こったかは不明ですが、たぶん“距離が最小の変化が起きた”と考えるのが常識的です(この例でいえば(2))
そこで、今回の課題は、２つの生物間の距離最小になるような並べ替えを行い、その距離とします。
文字列が長くなるとこの“最小距離の文字配列”をみつけるのは容易ではありません。
そこで、DPを使って計算量を最小限にしようというわけです。
＝＝
課題：
abcdef と abcddf との並べ方と最短距離を示しなさい。並べ方は複数あると思います。
また、
abcdef と abcef に関しても上と同様のことをしてみましょう。
＝＝
プログラム：
#include <stdio.h>
#define das 1
#define dsb 1
#define I 5
#define J 6
int dab, i, j, sum0, sum1, sum2, D, IJ, Ix, Jx;
char A[I]={'o','c','d','e','f'};
char Ad[I+J];
char B[J]={'o','a','b','c','d','e'};
char Bd[I+J];
int g[I][J], del[I][J];
main(){
g[0][0]=0;
for( i=1; i<I; i++){
g[i][0]= g[i-1][0]+ das;
del[i][0]=-1;
}
for( j=1; j<J; j++){
g[0][j]= g[0][j-1]+ dsb;
del[0][j]=-3;
}
for(i=1; i<I; i++){
for(j=1; j<J; j++){
if(A[i]==B[j]) dab=0;
else dab=2;
sum0= g[i-1][j]+das;
sum1= g[i-1][j-1]+ dab;
sum2= g[i][j-1] +dsb;
if(((sum0<sum1)&&(sum0<sum2))||((sum0==sum1)&&(sum0<sum2))||((sum0==sum2)&&(sum0<sum1))) {
g[i][j]= sum0;
del[i][j]= -1;
}
if(((sum1<sum0)&&(sum1<sum2))||((sum1==sum0)&&(sum1<sum2))||((sum1==sum0)&&(sum1<sum2))) {
g[i][j]= sum1;
del[i][j]= -2;
}
if(((sum2<sum0)&&(sum2<sum1))||((sum2==sum1)&&(sum2<sum0))||((sum2==sum0)&&(sum2<sum1))) {
g[i][j]= sum2;
del[i][j]= -3;
}
if((sum1==sum0)&&(sum1==sum2)) {
g[i][j]= sum1;
del[i][j]= -2;
}
}
}
// 類似度表示
printf("D=%d\n",g[I-1][J-1]);
// g[][]の表示
for(i=0; i<I; i++){
for(j=0;j<J;j++) printf("%d,",g[i][j]);
printf("\n");
}
// deltaの表示
for(i=0; i<I; i++){
for(j=0;j<J;j++) printf("%d,",del[i][j]);
printf("\n");
}
// 最短経路決定
for(i=0; i<I+J-1; i++){
Ad[i]='o';
Bd[i]='o';
}
Ix=I-1;
Jx=J-1;
for(i=I+J-1; i>0 ;i--){
if(del[Ix][Jx]==-2){
Ad[i]= A[Ix];
Bd[i]= B[Jx];
Ix--;
Jx--;
}
else if(del[Ix][Jx]==-3){
Ad[i]= '*';
Bd[i]= B[Jx];
Jx--;
}
else if(del[Ix][Jx]==-1){
Ad[i]= A[Ix];
Bd[i]= '*';
Ix--;
}
}
// 最短経路表示
for(i=0; i<I+J ;i++)
if(Ad[i]!='o') printf("%c",Ad[i]);
printf("\n");
for(i=0; i<I+J ;i++)
if(Bd[i]!='o') printf("%c",Bd[i]);
printf("\n");
}
最適（最短）経路は、ｇ[][]の、お尻(I,J)からdel[][]を使って遡ります。