binaries/src/mafft/core/genalign11.c.tobisugi

   1 #include "mltaln.h"
   2 #include "dp.h"
   3
   4 #define DEBUG 0
   5 #define DEBUG2 0
   6 #define XXXXXXX    0
   7 #define USE_PENALTY_EX  1
   8
   9 static short localstop;
  10
  11 #if 0
  12 static void match_calc( float *match, char **s1, char **s2, int i1, int lgth2 )
  13 {
  14         int j;
  15         char tmpc = s1[0][i1];
  16         char *seq2 = s2[0];
  17
  18         while( lgth2-- )
  19                 *match++ = amino_dis[tmpc][*seq2++];
  20 }
  21 #else
  22 static void match_calc( float *match, char **s1, char **s2, int i1, int lgth2 )
  23 {
  24         int j;
  25
  26         for( j=0; j<lgth2; j++ )
  27                 match[j] = amino_dis[(*s1)[i1]][(*s2)[j]];
  28 }
  29 #endif
  30
  31 static void match_calc_bk( float *match, float **cpmx1, float **cpmx2, int i1, int lgth2, float **floatwork, int **intwork, int initialize )
  32 {
  33         int j, k, l;
  34         float scarr[26];
  35         float **cpmxpd = floatwork;
  36         int **cpmxpdn = intwork;
  37         int count = 0;
  38
  39         if( initialize )
  40         {
  41                 for( j=0; j<lgth2; j++ )
  42                 {
  43                         count = 0;
  44                         for( l=0; l<26; l++ )
  45                         {
  46                                 if( cpmx2[l][j] )
  47                                 {
  48                                         cpmxpd[count][j] = cpmx2[l][j];
  49                                         cpmxpdn[count][j] = l;
  50                                         count++;
  51                                 }
  52                         }
  53                         cpmxpdn[count][j] = -1;
  54                 }
  55         }
  56
  57         for( l=0; l<26; l++ )
  58         {
  59                 scarr[l] = 0.0;
  60                 for( k=0; k<26; k++ )
  61                         scarr[l] += n_dis[k][l] * cpmx1[k][i1];
  62         }
  63 #if 0 /* ¤³¤ì¤ò»È¤¦¤È¤\ad¤Ïfloatwork¤Î¥¢¥í¥±¡¼¥È¤òµÕ¤Ë¤¹¤ë */
  64         {
  65                 float *fpt, **fptpt, *fpt2;
  66                 int *ipt, **iptpt;
  67                 fpt2 = match;
  68                 iptpt = cpmxpdn;
  69                 fptpt = cpmxpd;
  70                 while( lgth2-- )
  71                 {
  72                         *fpt2 = 0.0;
  73                         ipt=*iptpt,fpt=*fptpt;
  74                         while( *ipt > -1 )
  75                                 *fpt2 += scarr[*ipt++] * *fpt++;
  76                         fpt2++,iptpt++,fptpt++;
  77                 }
  78         }
  79 #else
  80         for( j=0; j<lgth2; j++ )
  81         {
  82                 match[j] = 0.0;
  83                 for( k=0; cpmxpdn[k][j]>-1; k++ )
  84                         match[j] += scarr[cpmxpdn[k][j]] * cpmxpd[k][j];
  85         }
  86 #endif
  87 }
  88
  89 static float gentracking( float *lasthorizontalw, float *lastverticalw,
  90                                                 char **seq1, char **seq2,
  91                         char **mseq1, char **mseq2,
  92                         float **cpmx1, float **cpmx2,
  93                         short **ijpi, short **ijpj, int *off1pt, int *off2pt, int endi, int endj )
  94 {
  95         int i, j, l, iin, jin, ifi, jfi, lgth1, lgth2, k, limk;
  96         char gap[] = "-";
  97         float wm;
  98         lgth1 = strlen( seq1[0] );
  99         lgth2 = strlen( seq2[0] );
 100
 101 #if 0
 102         for( i=0; i<lgth1; i++ )
 103         {
 104                 fprintf( stderr, "lastverticalw[%d] = %f\n", i, lastverticalw[i] );
 105         }
 106 #endif
 107
 108     for( i=0; i<lgth1+1; i++ )
 109     {
 110         ijpi[i][0] = localstop;
 111         ijpj[i][0] = localstop;
 112     }
 113     for( j=0; j<lgth2+1; j++ )
 114     {
 115         ijpi[0][j] = localstop;
 116         ijpj[0][j] = localstop;
 117     }
 118
 119         mseq1[0] += lgth1+lgth2;
 120         *mseq1[0] = 0;
 121         mseq2[0] += lgth1+lgth2;
 122         *mseq2[0] = 0;
 123         iin = endi; jin = endj;
 124         limk = lgth1+lgth2;
 125         for( k=0; k<=limk; k++ )
 126         {
 127
 128                 ifi = ( ijpi[iin][jin] );
 129                 jfi = ( ijpj[iin][jin] );
 130                 l = iin - ifi;
 131 //              if( ijpi[iin][jin] < 0 || ijpj[iin][jin] < 0 )
 132 //              {
 133 //                      fprintf( stderr, "skip! %d-%d\n", ijpi[iin][jin], ijpj[iin][jin] );
 134 //                      fprintf( stderr, "1: %c-%c\n", seq1[0][iin], seq1[0][ifi] );
 135 //                      fprintf( stderr, "2: %c-%c\n", seq2[0][jin], seq2[0][jfi] );
 136 //              }
 137                 while( --l )
 138                 {
 139                         *--mseq1[0] = seq1[0][ifi+l];
 140                         *--mseq2[0] = *gap;
 141                         k++;
 142                 }
 143                 l= jin - jfi;
 144                 while( --l )
 145                 {
 146                         *--mseq1[0] = *gap;
 147                         *--mseq2[0] = seq2[0][jfi+l];
 148                         k++;
 149                 }
 150
 151                 if( iin <= 0 || jin <= 0 ) break;
 152                 *--mseq1[0] = seq1[0][ifi];
 153                 *--mseq2[0] = seq2[0][jfi];
 154                 if( ijpi[ifi][jfi] == localstop ) break;
 155                 if( ijpj[ifi][jfi] == localstop ) break; /*¤¤¤é¤Ê¤¤*/
 156                 k++;
 157                 iin = ifi; jin = jfi;
 158         }
 159         if( ifi == -1 ) *off1pt = 0; else *off1pt = ifi;
 160         if( jfi == -1 ) *off2pt = 0; else *off2pt = jfi;
 161
 162 //      fprintf( stderr, "ifn = %d, jfn = %d\n", ifi, jfi );
 163
 164
 165         return( 0.0 );
 166 }
 167
 168
 169 float genL__align11( char **seq1, char **seq2, int alloclen, int *off1pt, int *off2pt )
 170 /* score no keisan no sai motokaraaru gap no atukai ni mondai ga aru */
 171 {
 172 //      int k;
 173         register int i, j;
 174         int lasti, lastj;
 175         int lgth1, lgth2;
 176         int resultlen;
 177         float wm;   /* int ?????? */
 178         float g, g1, g2;
 179         float *currentw, *previousw;
 180 #if 1
 181         float *wtmp;
 182         short *ijpipt;
 183         short *ijpjpt;
 184         float *mjpt, *Mjpt, *prept, *curpt;
 185         int *mpjpt, *Mpjpt;
 186 #endif
 187         static float mi, *m;
 188         static float Mi, *largeM;
 189         static short **ijpi;
 190         static short **ijpj;
 191         static int mpi, *mp;
 192         static int Mpi, *Mp;
 193         static float *w1, *w2;
 194         static float *match;
 195         static float *initverticalw;    /* kufuu sureba iranai */
 196         static float *lastverticalw;    /* kufuu sureba iranai */
 197         static char **mseq1;
 198         static char **mseq2;
 199         static char **mseq;
 200         static float **cpmx1;
 201         static float **cpmx2;
 202         static int **intwork;
 203         static float **floatwork;
 204         static int orlgth1 = 0, orlgth2 = 0;
 205         float maxwm;
 206         float tbk;
 207         int tbki, tbkj;
 208         int endali, endalj;
 209 //      float localthr = 0.0;
 210 //      float localthr2 = 0.0;
 211         float fpenalty = (float)penalty;
 212         float fpenalty_OP = (float)penalty_OP;
 213         float fpenalty_ex = (float)penalty_ex;
 214         float fpenalty_EX = (float)penalty_EX;
 215         float foffset = (float)offset;
 216         float localthr = -foffset;
 217         float localthr2 = -foffset;
 218
 219
 220 //      fprintf( stderr, "@@@@@@@@@@@@@ penalty_OP = %f, penalty_EX = %f, pelanty = %f\n", fpenalty_OP, fpenalty_EX, fpenalty );
 221
 222         if( orlgth1 == 0 )
 223         {
 224                 mseq1 = AllocateCharMtx( njob, 0 );
 225                 mseq2 = AllocateCharMtx( njob, 0 );
 226         }
 227
 228
 229         lgth1 = strlen( seq1[0] );
 230         lgth2 = strlen( seq2[0] );
 231
 232         if( lgth1 > orlgth1 || lgth2 > orlgth2 )
 233         {
 234                 int ll1, ll2;
 235
 236                 if( orlgth1 > 0 && orlgth2 > 0 )
 237                 {
 238                         FreeFloatVec( w1 );
 239                         FreeFloatVec( w2 );
 240                         FreeFloatVec( match );
 241                         FreeFloatVec( initverticalw );
 242                         FreeFloatVec( lastverticalw );
 243
 244                         FreeFloatVec( m );
 245                         FreeIntVec( mp );
 246                         FreeFloatVec( largeM );
 247                         FreeIntVec( Mp );
 248
 249                         FreeCharMtx( mseq );
 250
 251                         FreeFloatMtx( cpmx1 );
 252                         FreeFloatMtx( cpmx2 );
 253
 254                         FreeFloatMtx( floatwork );
 255                         FreeIntMtx( intwork );
 256                 }
 257
 258                 ll1 = MAX( (int)(1.3*lgth1), orlgth1 ) + 100;
 259                 ll2 = MAX( (int)(1.3*lgth2), orlgth2 ) + 100;
 260
 261 #if DEBUG
 262                 fprintf( stderr, "\ntrying to allocate (%d+%d)xn matrices ... ", ll1, ll2 );
 263 #endif
 264
 265                 w1 = AllocateFloatVec( ll2+2 );
 266                 w2 = AllocateFloatVec( ll2+2 );
 267                 match = AllocateFloatVec( ll2+2 );
 268
 269                 initverticalw = AllocateFloatVec( ll1+2 );
 270                 lastverticalw = AllocateFloatVec( ll1+2 );
 271
 272                 m = AllocateFloatVec( ll2+2 );
 273                 mp = AllocateIntVec( ll2+2 );
 274                 largeM = AllocateFloatVec( ll2+2 );
 275                 Mp = AllocateIntVec( ll2+2 );
 276
 277                 mseq = AllocateCharMtx( njob, ll1+ll2 );
 278
 279                 cpmx1 = AllocateFloatMtx( 26, ll1+2 );
 280                 cpmx2 = AllocateFloatMtx( 26, ll2+2 );
 281
 282                 floatwork = AllocateFloatMtx( 26, MAX( ll1, ll2 )+2 );
 283                 intwork = AllocateIntMtx( 26, MAX( ll1, ll2 )+2 );
 284
 285 #if DEBUG
 286                 fprintf( stderr, "succeeded\n" );
 287 #endif
 288
 289                 orlgth1 = ll1 - 100;
 290                 orlgth2 = ll2 - 100;
 291         }
 292
 293
 294         mseq1[0] = mseq[0];
 295         mseq2[0] = mseq[1];
 296
 297
 298         if( orlgth1 > commonAlloc1 || orlgth2 > commonAlloc2 )
 299         {
 300                 int ll1, ll2;
 301
 302                 if( commonAlloc1 && commonAlloc2 )
 303                 {
 304                         FreeShortMtx( commonIP );
 305                         FreeShortMtx( commonJP );
 306                 }
 307
 308                 ll1 = MAX( orlgth1, commonAlloc1 );
 309                 ll2 = MAX( orlgth2, commonAlloc2 );
 310
 311 #if DEBUG
 312                 fprintf( stderr, "\n\ntrying to allocate %dx%d matrices ... ", ll1+1, ll2+1 );
 313 #endif
 314
 315                 commonIP = AllocateShortMtx( ll1+10, ll2+10 );
 316                 commonJP = AllocateShortMtx( ll1+10, ll2+10 );
 317
 318 #if DEBUG
 319                 fprintf( stderr, "succeeded\n\n" );
 320 #endif
 321
 322                 commonAlloc1 = ll1;
 323                 commonAlloc2 = ll2;
 324         }
 325         ijpi = commonIP;
 326         ijpj = commonJP;
 327
 328
 329 #if 0
 330         for( i=0; i<lgth1; i++ )
 331                 fprintf( stderr, "ogcp1[%d]=%f\n", i, ogcp1[i] );
 332 #endif
 333
 334         currentw = w1;
 335         previousw = w2;
 336
 337         match_calc( initverticalw, seq2, seq1, 0, lgth1 );
 338
 339         match_calc( currentw, seq1, seq2, 0, lgth2 );
 340
 341
 342         lasti = lgth2+1;
 343         for( j=1; j<lasti; ++j )
 344         {
 345                 m[j] = currentw[j-1]; mp[j] = 0;
 346                 largeM[j] = currentw[j-1]; Mp[j] = 0;
 347         }
 348
 349         lastverticalw[0] = currentw[lgth2-1];
 350
 351
 352 #if 0
 353 fprintf( stderr, "currentw = \n" );
 354 for( i=0; i<lgth1+1; i++ )
 355 {
 356         fprintf( stderr, "%5.2f ", currentw[i] );
 357 }
 358 fprintf( stderr, "\n" );
 359 fprintf( stderr, "initverticalw = \n" );
 360 for( i=0; i<lgth2+1; i++ )
 361 {
 362         fprintf( stderr, "%5.2f ", initverticalw[i] );
 363 }
 364 fprintf( stderr, "\n" );
 365 #endif
 366 #if DEBUG2
 367         fprintf( stderr, "\n" );
 368         fprintf( stderr, "       " );
 369         for( j=0; j<lgth2+1; j++ )
 370                 fprintf( stderr, "%c     ", seq2[0][j] );
 371         fprintf( stderr, "\n" );
 372 #endif
 373
 374         localstop = lgth1+lgth2+1;
 375         maxwm = -999.9;
 376         endali = endalj = 0;
 377 #if DEBUG2
 378         fprintf( stderr, "\n" );
 379         fprintf( stderr, "%c   ", seq1[0][0] );
 380
 381         for( j=0; j<lgth2+1; j++ )
 382                 fprintf( stderr, "%5.0f ", currentw[j] );
 383         fprintf( stderr, "\n" );
 384 #endif
 385
 386         lasti = lgth1+1;
 387         for( i=1; i<lasti; i++ )
 388         {
 389                 wtmp = previousw;
 390                 previousw = currentw;
 391                 currentw = wtmp;
 392
 393                 previousw[0] = initverticalw[i-1];
 394
 395                 match_calc( currentw, seq1, seq2, i, lgth2 );
 396 #if DEBUG2
 397                 fprintf( stderr, "%c   ", seq1[0][i] );
 398                 fprintf( stderr, "%5.0f ", currentw[0] );
 399 #endif
 400
 401 #if XXXXXXX
 402 fprintf( stderr, "\n" );
 403 fprintf( stderr, "i=%d\n", i );
 404 fprintf( stderr, "currentw = \n" );
 405 for( j=0; j<lgth2; j++ )
 406 {
 407         fprintf( stderr, "%5.2f ", currentw[j] );
 408 }
 409 fprintf( stderr, "\n" );
 410 #endif
 411 #if XXXXXXX
 412 fprintf( stderr, "\n" );
 413 fprintf( stderr, "i=%d\n", i );
 414 fprintf( stderr, "currentw = \n" );
 415 for( j=0; j<lgth2; j++ )
 416 {
 417         fprintf( stderr, "%5.2f ", currentw[j] );
 418 }
 419 fprintf( stderr, "\n" );
 420 #endif
 421                 currentw[0] = initverticalw[i];
 422
 423                 mi = previousw[0]; mpi = 0;
 424                 Mi = previousw[0]; Mpi = 0;
 425
 426 #if 0
 427                 if( mi < localthr ) mi = localthr2;
 428 #endif
 429
 430                 ijpipt = ijpi[i] + 1;
 431                 ijpjpt = ijpj[i] + 1;
 432                 mjpt = m + 1;
 433                 Mjpt = largeM + 1;
 434                 prept = previousw;
 435                 curpt = currentw + 1;
 436                 mpjpt = mp + 1;
 437                 Mpjpt = Mp + 1;
 438                 tbk = -999999.9;
 439                 tbki = 0;
 440                 tbkj = 0;
 441                 lastj = lgth2+1;
 442                 for( j=1; j<lastj; j++ )
 443                 {
 444                         wm = *prept;
 445                         *ijpipt = i-1;
 446                         *ijpjpt = j-1;
 447
 448
 449 //                      fprintf( stderr, "i,j=%d,%d %c-%c\n", i, j, seq1[0][i], seq2[0][j] );
 450 //                      fprintf( stderr, "wm=%f\n", wm );
 451 #if 0
 452                         fprintf( stderr, "%5.0f->", wm );
 453 #endif
 454                         g1 = mi + fpenalty;
 455                         g2 = *mjpt + fpenalty;
 456                         g = MAX( g1, g2 );
 457 #if 0
 458                         fprintf( stderr, "%5.0f?", g );
 459 #endif
 460                         if( g > wm )
 461                         {
 462                                 wm = g;
 463 //                              *ijpipt = i-1;
 464                                 *ijpipt = *mpjpt;
 465                                 *ijpjpt = mpi;
 466                         }
 467 //                      if( g2 > wm )
 468 //                      {
 469 //                              wm = g2;
 470 //                              *ijpipt = *mpjpt;
 471 //                              *ijpjpt = j-1;
 472 //                      }
 473 //
 474
 475                         g = *prept;
 476                         if( g > mi )
 477                         {
 478                                 mi = g;
 479                                 mpi = j-1;
 480                         }
 481
 482 #if USE_PENALTY_EX
 483                         mi += fpenalty_ex;
 484 #endif
 485
 486 #if 0
 487                         fprintf( stderr, "%5.0f->", wm );
 488 #endif
 489                         g = *prept;
 490                         if( g > *mjpt )
 491                         {
 492                                 *mjpt = g;
 493                                 *mpjpt = i-1;
 494                         }
 495 #if USE_PENALTY_EX
 496                         *mjpt += fpenalty_ex;
 497 #endif
 498
 499
 500                         g =  tbk + fpenalty_OP; /*ÊÌ¤ÎÊý¤¬¤¤¤¤¤«¤â*/
 501 //                      g =  tbk; /*ÊÌ¤ÎÊý¤¬¤¤¤¤¤«¤â*/
 502                         if( g > wm )
 503                         {
 504                                 wm = g;
 505                                 *ijpipt = tbki;
 506                                 *ijpjpt = tbkj;
 507 //                              fprintf( stderr, "hit! i%d, j%d, ijpi = %d, ijpj = %d\n", i, j, *ijpipt, *ijpjpt );
 508                         }
 509 //                      g = Mi;
 510                         if( Mi > tbk )
 511                         {
 512                                 tbk = g;
 513                                 tbki = i-1;
 514                                 tbkj = Mpi;
 515                         }
 516 //                      g = *Mjpt;
 517                         if( *Mjpt > tbk )
 518                         {
 519                                 tbk = *Mjpt;
 520                                 tbki = *Mpjpt;
 521                                 tbkj = j-1;
 522                         }
 523 //                      tbk += fpenalty_EX;// + foffset;
 524
 525 //                      g = *prept;
 526                         if( *prept > *Mjpt )
 527                         {
 528                                 *Mjpt = *prept;
 529                                 *Mpjpt = i-1;
 530                         }
 531 //                      *Mjpt += fpenalty_EX;// + foffset;
 532
 533 //                      g = *prept;
 534                         if( *prept > Mi )
 535                         {
 536                                 Mi = *prept;
 537                                 Mpi = j-1;
 538                         }
 539 //                      Mi += fpenalty_EX;// + foffset;
 540
 541
 542 //                      fprintf( stderr, "wm=%f, tbk=%f(%c-%c), mi=%f, *mjpt=%f\n", wm, tbk, seq1[0][tbki], seq2[0][tbkj], mi, *mjpt );
 543 //                      fprintf( stderr, "ijp = %c,%c\n", seq1[0][abs(*ijpipt)], seq2[0][abs(*ijpjpt)] );
 544
 545
 546                         if( maxwm < wm )
 547                         {
 548                                 maxwm = wm;
 549                                 endali = i;
 550                                 endalj = j;
 551                         }
 552 #if 1
 553                         if( wm < localthr )
 554                         {
 555 //                              fprintf( stderr, "stop i=%d, j=%d, curpt=%f\n", i, j, *curpt );
 556                                 *ijpipt = localstop;
 557 //                              *ijpjpt = localstop; /*¤¤¤é¤Ê¤¤*/
 558                                 wm = localthr2;
 559                         }
 560 #endif
 561 #if 0
 562                         fprintf( stderr, "%5.0f ", *curpt );
 563 #endif
 564 #if DEBUG2
 565                         fprintf( stderr, "%5.0f ", wm );
 566 //                      fprintf( stderr, "%c-%c *ijppt = %d, localstop = %d\n", seq1[0][i], seq2[0][j], *ijppt, localstop );
 567 #endif
 568
 569                         *curpt += wm;
 570                         ijpipt++;
 571                         ijpjpt++;
 572                         mjpt++;
 573                         Mjpt++;
 574                         prept++;
 575                         mpjpt++;
 576                         Mpjpt++;
 577                         curpt++;
 578                 }
 579 #if DEBUG2
 580                 fprintf( stderr, "\n" );
 581 #endif
 582
 583                 lastverticalw[i] = currentw[lgth2-1];
 584         }
 585
 586
 587 #if DEBUG2
 588         fprintf( stderr, "maxwm = %f\n", maxwm );
 589         fprintf( stderr, "endali = %d\n", endali );
 590         fprintf( stderr, "endalj = %d\n", endalj );
 591 #endif
 592
 593         gentracking( currentw, lastverticalw, seq1, seq2, mseq1, mseq2, cpmx1, cpmx2, ijpi, ijpj, off1pt, off2pt, endali, endalj );
 594
 595 //      fprintf( stderr, "### impmatch = %f\n", *impmatch );
 596
 597         resultlen = strlen( mseq1[0] );
 598         if( alloclen < resultlen || resultlen > N )
 599         {
 600                 fprintf( stderr, "alloclen=%d, resultlen=%d, N=%d\n", alloclen, resultlen, N );
 601                 ErrorExit( "LENGTH OVER!\n" );
 602         }
 603
 604
 605         strcpy( seq1[0], mseq1[0] );
 606         strcpy( seq2[0], mseq2[0] );
 607
 608 #if 0
 609         fprintf( stderr, "\n" );
 610         fprintf( stderr, ">\n%s\n", mseq1[0] );
 611         fprintf( stderr, ">\n%s\n", mseq2[0] );
 612 #endif
 613
 614
 615         return( wm );
 616 }
 617