src/jalview/analysis/AlignSeq.java

   1 /*
   2 * Jalview - A Sequence Alignment Editor and Viewer
   3 * Copyright (C) 2006 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4 *
   5 * This program is free software; you can redistribute it and/or
   6 * modify it under the terms of the GNU General Public License
   7 * as published by the Free Software Foundation; either version 2
   8 * of the License, or (at your option) any later version.
   9 *
  10 * This program is distributed in the hope that it will be useful,
  11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 * GNU General Public License for more details.
  14 *
  15 * You should have received a copy of the GNU General Public License
  16 * along with this program; if not, write to the Free Software
  17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18 */
  19 package jalview.analysis;
  20
  21 import jalview.datamodel.SequenceI;
  22
  23 import jalview.schemes.*;
  24
  25 import jalview.util.*;
  26
  27 import java.awt.*;
  28
  29 import java.util.*;
  30
  31
  32 /**
  33  *
  34  *
  35  * @author $author$
  36  * @version $Revision$
  37  */
  38 public class AlignSeq
  39 {
  40     public static final String PEP = "pep";
  41     public static final String DNA = "dna";
  42     /** DOCUMENT ME!! */
  43     public static java.util.Hashtable dnaHash = new java.util.Hashtable();
  44
  45     static
  46     {
  47         dnaHash.put("C", new Integer(0));
  48         dnaHash.put("T", new Integer(1));
  49         dnaHash.put("A", new Integer(2));
  50         dnaHash.put("G", new Integer(3));
  51         dnaHash.put("-", new Integer(4));
  52     }
  53
  54     static String[] dna = { "C", "T", "A", "G", "-" };
  55     static String[] pep =
  56     {
  57         "A", "R", "N", "D", "C", "Q", "E", "G", "H", "I", "L", "K", "M", "F",
  58         "P", "S", "T", "W", "Y", "V", "B", "Z", "X", "-"
  59     };
  60     int[][] score;
  61     int[][] E;
  62     int[][] F;
  63     int[][] traceback;
  64     int[] seq1;
  65     int[] seq2;
  66     SequenceI s1;
  67     SequenceI s2;
  68     public String s1str;
  69     public String s2str;
  70     int maxi;
  71     int maxj;
  72     int[] aseq1;
  73     int[] aseq2;
  74     public String astr1="";
  75     public String astr2="";
  76
  77     /** DOCUMENT ME!! */
  78     public int seq1start;
  79
  80     /** DOCUMENT ME!! */
  81     public int seq1end;
  82
  83     /** DOCUMENT ME!! */
  84     public int seq2start;
  85
  86     /** DOCUMENT ME!! */
  87     public int seq2end;
  88     int count;
  89
  90     /** DOCUMENT ME!! */
  91     public int maxscore;
  92     float pid;
  93     int prev = 0;
  94     int gapOpen = 120;
  95     int gapExtend = 20;
  96     int[][] lookup = ResidueProperties.getBLOSUM62();
  97     String[] intToStr = pep;
  98     int defInt = 23;
  99     StringBuffer output = new StringBuffer();
 100     String type;
 101
 102     /**
 103      * Creates a new AlignSeq object.
 104      *
 105      * @param s1 DOCUMENT ME!
 106      * @param s2 DOCUMENT ME!
 107      * @param type DOCUMENT ME!
 108      */
 109     public AlignSeq(SequenceI s1, SequenceI s2, String type)
 110     {
 111         SeqInit(s1, s1.getSequenceAsString(), s2,  s2.getSequenceAsString(), type);
 112     }
 113
 114     /**
 115      * Creates a new AlignSeq object.
 116      *
 117      * @param s1 DOCUMENT ME!
 118      * @param s2 DOCUMENT ME!
 119      * @param type DOCUMENT ME!
 120      */
 121     public AlignSeq(SequenceI s1,
 122                     String string1,
 123                     SequenceI s2,
 124                     String string2,
 125                     String type)
 126     {
 127         SeqInit(s1, string1, s2,  string2,  type);
 128     }
 129
 130     /**
 131      * DOCUMENT ME!
 132      *
 133      * @return DOCUMENT ME!
 134      */
 135     public int getMaxScore()
 136     {
 137         return maxscore;
 138     }
 139
 140     /**
 141      * DOCUMENT ME!
 142      *
 143      * @return DOCUMENT ME!
 144      */
 145     public int getSeq2Start()
 146     {
 147         return seq2start;
 148     }
 149
 150     /**
 151      * DOCUMENT ME!
 152      *
 153      * @return DOCUMENT ME!
 154      */
 155     public int getSeq2End()
 156     {
 157         return seq2end;
 158     }
 159
 160     /**
 161      * DOCUMENT ME!
 162      *
 163      * @return DOCUMENT ME!
 164      */
 165     public int getSeq1Start()
 166     {
 167         return seq1start;
 168     }
 169
 170     /**
 171      * DOCUMENT ME!
 172      *
 173      * @return DOCUMENT ME!
 174      */
 175     public int getSeq1End()
 176     {
 177         return seq1end;
 178     }
 179
 180     /**
 181      * DOCUMENT ME!
 182      *
 183      * @return DOCUMENT ME!
 184      */
 185     public String getOutput()
 186     {
 187         return output.toString();
 188     }
 189
 190     /**
 191      * DOCUMENT ME!
 192      *
 193      * @return DOCUMENT ME!
 194      */
 195     public String getAStr1()
 196     {
 197         return astr1;
 198     }
 199
 200     /**
 201      * DOCUMENT ME!
 202      *
 203      * @return DOCUMENT ME!
 204      */
 205     public String getAStr2()
 206     {
 207         return astr2;
 208     }
 209
 210     /**
 211      * DOCUMENT ME!
 212      *
 213      * @return DOCUMENT ME!
 214      */
 215     public int[] getASeq1()
 216     {
 217         return aseq1;
 218     }
 219
 220     /**
 221      * DOCUMENT ME!
 222      *
 223      * @return DOCUMENT ME!
 224      */
 225     public int[] getASeq2()
 226     {
 227         return aseq2;
 228     }
 229
 230     /**
 231      * DOCUMENT ME!
 232      *
 233      * @return DOCUMENT ME!
 234      */
 235     public SequenceI getS1()
 236     {
 237         return s1;
 238     }
 239
 240     /**
 241      * DOCUMENT ME!
 242      *
 243      * @return DOCUMENT ME!
 244      */
 245     public SequenceI getS2()
 246     {
 247         return s2;
 248     }
 249
 250     /**
 251      * DOCUMENT ME!
 252      *
 253      * @param s1 DOCUMENT ME!
 254      * @param string1 -  string to align for sequence1
 255      * @param s2 sequence 2
 256      * @param string2 -  string to align for sequence2
 257      * @param type DNA or PEPTIDE
 258      */
 259     public void SeqInit(SequenceI s1,
 260                         String string1,
 261                         SequenceI s2,
 262                         String string2,
 263                         String type)
 264     {
 265       this.s1 = s1;
 266       this.s2 = s2;
 267       setDefaultParams(type);
 268       SeqInit(string1,string2);
 269     }
 270     public void SeqInit(SequenceI s1,
 271         String string1,
 272         SequenceI s2,
 273         String string2,
 274         ScoreMatrix scoreMatrix) {
 275       this.s1=s1;
 276       this.s2=s2;
 277       setType(scoreMatrix.isDNA() ? AlignSeq.DNA : AlignSeq.PEP);
 278       lookup=scoreMatrix.getMatrix();
 279     }
 280     /**
 281      * construct score matrix for string1 and string2 (after removing any existing gaps
 282      * @param string1
 283      * @param string2
 284      */
 285     private void SeqInit(String string1, String string2) {
 286       s1str = extractGaps(jalview.util.Comparison.GapChars, string1);
 287       s2str = extractGaps(jalview.util.Comparison.GapChars, string2);
 288
 289       if(s1str.length()==0 || s2str.length()==0)
 290       {
 291         output.append("ALL GAPS: " +
 292                            (s1str.length()==0?s1.getName():" ")
 293                            +(s2str.length()==0?s2.getName():""));
 294         return;
 295       }
 296
 297       //System.out.println("lookuip " + rt.freeMemory() + " "+  rt.totalMemory());
 298       seq1 = new int[s1str.length()];
 299
 300       //System.out.println("seq1 " + rt.freeMemory() +" "  + rt.totalMemory());
 301       seq2 = new int[s2str.length()];
 302
 303       //System.out.println("seq2 " + rt.freeMemory() + " " + rt.totalMemory());
 304       score = new int[s1str.length()][s2str.length()];
 305
 306       //System.out.println("score " + rt.freeMemory() + " " + rt.totalMemory());
 307       E = new int[s1str.length()][s2str.length()];
 308
 309       //System.out.println("E " + rt.freeMemory() + " " + rt.totalMemory());
 310       F = new int[s1str.length()][s2str.length()];
 311       traceback = new int[s1str.length()][s2str.length()];
 312
 313       //System.out.println("F " + rt.freeMemory() + " " + rt.totalMemory());
 314       seq1 = stringToInt(s1str, type);
 315
 316       //System.out.println("seq1 " + rt.freeMemory() + " " + rt.totalMemory());
 317       seq2 = stringToInt(s2str, type);
 318
 319       //System.out.println("Seq2 " + rt.freeMemory() + " " + rt.totalMemory());
 320       //   long tstart = System.currentTimeMillis();
 321       //    calcScoreMatrix();
 322       //long tend = System.currentTimeMillis();
 323       //System.out.println("Time take to calculate score matrix = " + (tend-tstart) + " ms");
 324       //   printScoreMatrix(score);
 325       //System.out.println();
 326       //printScoreMatrix(traceback);
 327       //System.out.println();
 328       //  printScoreMatrix(E);
 329       //System.out.println();
 330       ///printScoreMatrix(F);
 331       //System.out.println();
 332       // tstart = System.currentTimeMillis();
 333       //traceAlignment();
 334       //tend = System.currentTimeMillis();
 335       //System.out.println("Time take to traceback alignment = " + (tend-tstart) + " ms");
 336     }
 337
 338     private void setDefaultParams(String type) {
 339         setType(type);
 340
 341         if (type.equals(AlignSeq.PEP))
 342         {
 343             lookup = ResidueProperties.getDefaultPeptideMatrix();
 344         }
 345         else if (type.equals(AlignSeq.DNA))
 346         {
 347             lookup = ResidueProperties.getDefaultDnaMatrix();
 348         }
 349     }
 350
 351     private void setType(String type2) {
 352       this.type = type2;
 353       if (type.equals(AlignSeq.PEP))
 354       {
 355           intToStr = pep;
 356           defInt = 23;
 357       }
 358       else if (type.equals(AlignSeq.DNA))
 359       {
 360           intToStr = dna;
 361           defInt = 4;
 362       }
 363       else
 364       {
 365           output.append("Wrong type = dna or pep only");
 366           throw new Error("Unknown Type "+type2+" - dna or pep are the only allowed values.");
 367       }
 368     }
 369
 370     /**
 371      * DOCUMENT ME!
 372      */
 373     public void traceAlignment()
 374     {
 375         // Find the maximum score along the rhs or bottom row
 376         int max = -9999;
 377
 378         for (int i = 0; i < seq1.length; i++)
 379         {
 380             if (score[i][seq2.length - 1] > max)
 381             {
 382                 max = score[i][seq2.length - 1];
 383                 maxi = i;
 384                 maxj = seq2.length - 1;
 385             }
 386         }
 387
 388         for (int j = 0; j < seq2.length; j++)
 389         {
 390             if (score[seq1.length - 1][j] > max)
 391             {
 392                 max = score[seq1.length - 1][j];
 393                 maxi = seq1.length - 1;
 394                 maxj = j;
 395             }
 396         }
 397
 398         //  System.out.println(maxi + " " + maxj + " " + score[maxi][maxj]);
 399         int i = maxi;
 400         int j = maxj;
 401         int trace;
 402         maxscore = score[i][j] / 10;
 403
 404         seq1end = maxi + 1;
 405         seq2end = maxj + 1;
 406
 407         aseq1 = new int[seq1.length + seq2.length];
 408         aseq2 = new int[seq1.length + seq2.length];
 409
 410         count = (seq1.length + seq2.length) - 1;
 411
 412         while ((i > 0) && (j > 0))
 413         {
 414             if ((aseq1[count] != defInt) && (i >= 0))
 415             {
 416                 aseq1[count] = seq1[i];
 417                 astr1 = intToStr[seq1[i]] + astr1;
 418             }
 419
 420             if ((aseq2[count] != defInt) && (j > 0))
 421             {
 422                 aseq2[count] = seq2[j];
 423                 astr2 = intToStr[seq2[j]] + astr2;
 424             }
 425
 426             trace = findTrace(i, j);
 427
 428             if (trace == 0)
 429             {
 430                 i--;
 431                 j--;
 432             }
 433             else if (trace == 1)
 434             {
 435                 j--;
 436                 aseq1[count] = defInt;
 437                 astr1 = "-" + astr1.substring(1);
 438             }
 439             else if (trace == -1)
 440             {
 441                 i--;
 442                 aseq2[count] = defInt;
 443                 astr2 = "-" + astr2.substring(1);
 444             }
 445
 446             count--;
 447         }
 448
 449         seq1start = i + 1;
 450         seq2start = j + 1;
 451
 452         if (aseq1[count] != defInt)
 453         {
 454             aseq1[count] = seq1[i];
 455             astr1 = intToStr[seq1[i]] + astr1;
 456         }
 457
 458         if (aseq2[count] != defInt)
 459         {
 460             aseq2[count] = seq2[j];
 461             astr2 = intToStr[seq2[j]] + astr2;
 462         }
 463     }
 464
 465     /**
 466      * DOCUMENT ME!
 467      */
 468     public void printAlignment(java.io.PrintStream os)
 469     {
 470         // Find the biggest id length for formatting purposes
 471         int maxid = s1.getName().length();
 472
 473         if (s2.getName().length() > maxid)
 474         {
 475             maxid = s2.getName().length();
 476         }
 477
 478         int len = 72 - maxid - 1;
 479         int nochunks = ((aseq1.length - count) / len) + 1;
 480         pid = 0;
 481
 482         output.append("Score = " + score[maxi][maxj] + "\n");
 483         output.append("Length of alignment = " + (aseq1.length - count) + "\n");
 484         output.append("Sequence ");
 485         output.append(new Format("%" + maxid + "s").form(s1.getName()));
 486         output.append(" :  " + s1.getStart() + " - " + s1.getEnd() + " (Sequence length = " +
 487             s1str.length() + ")\n");
 488         output .append("Sequence ");
 489         output.append(new Format("%" + maxid + "s").form(s2.getName()));
 490         output.append(" :  " + s2.getStart() + " - " + s2.getEnd() + " (Sequence length = " +
 491             s2str.length() + ")\n\n");
 492
 493         for (int j = 0; j < nochunks; j++)
 494         {
 495             // Print the first aligned sequence
 496             output.append(new Format("%" + (maxid) + "s").form(s1.getName()) + " ");
 497
 498             for (int i = 0; i < len; i++)
 499             {
 500                 if ((count + i + (j * len)) < aseq1.length)
 501                 {
 502                     output.append(new Format("%s").form(intToStr[aseq1[count + i +
 503                             (j * len)]]));
 504                 }
 505             }
 506
 507             output.append("\n");
 508             output.append(new Format("%" + (maxid) + "s").form(" ") + " ");
 509
 510             // Print out the matching chars
 511             for (int i = 0; i < len; i++)
 512             {
 513                 if ((count + i + (j * len)) < aseq1.length)
 514                 {
 515                     if (intToStr[aseq1[count + i + (j * len)]].equals(
 516                                 intToStr[aseq2[count + i + (j * len)]]) &&
 517                             !intToStr[aseq1[count + i + (j * len)]].equals("-"))
 518                     {
 519                         pid++;
 520                         output.append("|");
 521                     }
 522                     else if (type.equals("pep"))
 523                     {
 524                         if (ResidueProperties.getPAM250(
 525                                     intToStr[aseq1[count + i + (j * len)]],
 526                                     intToStr[aseq2[count + i + (j * len)]]) > 0)
 527                         {
 528                             output.append(".");
 529                         }
 530                         else
 531                         {
 532                             output.append(" ");
 533                         }
 534                     }
 535                     else
 536                     {
 537                         output.append(" ");
 538                     }
 539                 }
 540             }
 541
 542             // Now print the second aligned sequence
 543             output = output.append("\n");
 544             output = output.append(new Format("%" + (maxid) + "s").form(s2.getName()) + " ");
 545
 546             for (int i = 0; i < len; i++)
 547             {
 548                 if ((count + i + (j * len)) < aseq1.length)
 549                 {
 550                     output .append(new Format("%s").form(intToStr[aseq2[count + i +
 551                             (j * len)]]));
 552                 }
 553             }
 554
 555             output = output .append("\n\n");
 556         }
 557
 558         pid = pid / (float) (aseq1.length - count) * 100;
 559         output = output.append(new Format("Percentage ID = %2.2f\n\n").form(pid));
 560
 561         try{
 562           os.print(output.toString());
 563         }catch(Exception ex){}
 564     }
 565
 566     /**
 567      * DOCUMENT ME!
 568      *
 569      * @param mat DOCUMENT ME!
 570      */
 571     public void printScoreMatrix(int[][] mat)
 572     {
 573         int n = seq1.length;
 574         int m = seq2.length;
 575
 576         for (int i = 0; i < n; i++)
 577         {
 578             // Print the top sequence
 579             if (i == 0)
 580             {
 581                 Format.print(System.out, "%8s", s2str.substring(0, 1));
 582
 583                 for (int jj = 1; jj < m; jj++)
 584                 {
 585                     Format.print(System.out, "%5s", s2str.substring(jj, jj + 1));
 586                 }
 587
 588                 System.out.println();
 589             }
 590
 591             for (int j = 0; j < m; j++)
 592             {
 593                 if (j == 0)
 594                 {
 595                     Format.print(System.out, "%3s", s1str.substring(i, i + 1));
 596                 }
 597
 598                 Format.print(System.out, "%3d ", mat[i][j] / 10);
 599             }
 600
 601             System.out.println();
 602         }
 603     }
 604
 605     /**
 606      * DOCUMENT ME!
 607      *
 608      * @param i DOCUMENT ME!
 609      * @param j DOCUMENT ME!
 610      *
 611      * @return DOCUMENT ME!
 612      */
 613     public int findTrace(int i, int j)
 614     {
 615         int t = 0;
 616         int max = score[i - 1][j - 1] + (lookup[seq1[i]][seq2[j]] * 10);
 617
 618         if (F[i][j] > max)
 619         {
 620             max = F[i][j];
 621             t = -1;
 622         }
 623         else if (F[i][j] == max)
 624         {
 625             if (prev == -1)
 626             {
 627                 max = F[i][j];
 628                 t = -1;
 629             }
 630         }
 631
 632         if (E[i][j] >= max)
 633         {
 634             max = E[i][j];
 635             t = 1;
 636         }
 637         else if (E[i][j] == max)
 638         {
 639             if (prev == 1)
 640             {
 641                 max = E[i][j];
 642                 t = 1;
 643             }
 644         }
 645
 646         prev = t;
 647
 648         return t;
 649     }
 650
 651     /**
 652      * DOCUMENT ME!
 653      */
 654     public void calcScoreMatrix()
 655     {
 656         int n = seq1.length;
 657         int m = seq2.length;
 658
 659         // top left hand element
 660         score[0][0] = lookup[seq1[0]][seq2[0]] * 10;
 661         E[0][0] = -gapExtend;
 662         F[0][0] = 0;
 663
 664         // Calculate the top row first
 665         for (int j = 1; j < m; j++)
 666         {
 667             // What should these values be? 0 maybe
 668             E[0][j] = max(score[0][j - 1] - gapOpen, E[0][j - 1] - gapExtend);
 669             F[0][j] = -gapExtend;
 670
 671             score[0][j] = max(lookup[seq1[0]][seq2[j]] * 10, -gapOpen,
 672                     -gapExtend);
 673
 674             traceback[0][j] = 1;
 675         }
 676
 677         // Now do the left hand column
 678         for (int i = 1; i < n; i++)
 679         {
 680             E[i][0] = -gapOpen;
 681             F[i][0] = max(score[i - 1][0] - gapOpen, F[i - 1][0] - gapExtend);
 682
 683             score[i][0] = max(lookup[seq1[i]][seq2[0]] * 10, E[i][0], F[i][0]);
 684             traceback[i][0] = -1;
 685         }
 686
 687         // Now do all the other rows
 688         for (int i = 1; i < n; i++)
 689         {
 690             for (int j = 1; j < m; j++)
 691             {
 692                 E[i][j] = max(score[i][j - 1] - gapOpen, E[i][j - 1] -
 693                         gapExtend);
 694                 F[i][j] = max(score[i - 1][j] - gapOpen, F[i - 1][j] -
 695                         gapExtend);
 696
 697                 score[i][j] = max(score[i - 1][j - 1] +
 698                         (lookup[seq1[i]][seq2[j]] * 10), E[i][j], F[i][j]);
 699                 traceback[i][j] = findTrace(i, j);
 700             }
 701         }
 702     }
 703
 704
 705
 706     /**
 707      * DOCUMENT ME!
 708      *
 709      * @param gapChar DOCUMENT ME!
 710      * @param seq DOCUMENT ME!
 711      *
 712      * @return DOCUMENT ME!
 713      */
 714     public static String extractGaps(String gapChar, String seq)
 715     {
 716         StringTokenizer str = new StringTokenizer(seq, gapChar);
 717         StringBuffer newString = new StringBuffer();
 718
 719         while (str.hasMoreTokens())
 720         {
 721             newString.append( str.nextToken() );
 722         }
 723
 724         return newString.toString();
 725     }
 726
 727     /**
 728      * DOCUMENT ME!
 729      *
 730      * @param i1 DOCUMENT ME!
 731      * @param i2 DOCUMENT ME!
 732      * @param i3 DOCUMENT ME!
 733      *
 734      * @return DOCUMENT ME!
 735      */
 736     public int max(int i1, int i2, int i3)
 737     {
 738         int max = i1;
 739
 740         if (i2 > i1)
 741         {
 742             max = i2;
 743         }
 744
 745         if (i3 > max)
 746         {
 747             max = i3;
 748         }
 749
 750         return max;
 751     }
 752
 753     /**
 754      * DOCUMENT ME!
 755      *
 756      * @param i1 DOCUMENT ME!
 757      * @param i2 DOCUMENT ME!
 758      *
 759      * @return DOCUMENT ME!
 760      */
 761     public int max(int i1, int i2)
 762     {
 763         int max = i1;
 764
 765         if (i2 > i1)
 766         {
 767             max = i2;
 768         }
 769
 770         return max;
 771     }
 772
 773     /**
 774      * DOCUMENT ME!
 775      *
 776      * @param s DOCUMENT ME!
 777      * @param type DOCUMENT ME!
 778      *
 779      * @return DOCUMENT ME!
 780      */
 781     public int[] stringToInt(String s, String type)
 782     {
 783         int[] seq1 = new int[s.length()];
 784
 785         for (int i = 0; i < s.length(); i++)
 786         {
 787            // String ss = s.substring(i, i + 1).toUpperCase();
 788             char c = s.charAt(i);
 789             if ('a' <= c && c <= 'z')
 790             {
 791               // TO UPPERCASE !!!
 792               c -= ('a' - 'A');
 793             }
 794
 795
 796             try
 797             {
 798                 if (type.equals("pep"))
 799                 {
 800                     seq1[i] = ResidueProperties.aaIndex[c];
 801                 }
 802                 else if (type.equals("dna"))
 803                 {
 804                     seq1[i] = ResidueProperties.nucleotideIndex[c];
 805                 }
 806
 807                 if (seq1[i] > 23)
 808                 {
 809                     seq1[i] = 23;
 810                 }
 811             }
 812             catch (Exception e)
 813             {
 814                 if (type.equals("dna"))
 815                 {
 816                     seq1[i] = 4;
 817                 }
 818                 else
 819                 {
 820                     seq1[i] = 23;
 821                 }
 822             }
 823         }
 824
 825         return seq1;
 826     }
 827
 828     /**
 829      * DOCUMENT ME!
 830      *
 831      * @param g DOCUMENT ME!
 832      * @param mat DOCUMENT ME!
 833      * @param n DOCUMENT ME!
 834      * @param m DOCUMENT ME!
 835      * @param psize DOCUMENT ME!
 836      */
 837     public static void displayMatrix(Graphics g, int[][] mat, int n, int m,
 838         int psize)
 839     {
 840         int max = -1000;
 841         int min = 1000;
 842
 843         for (int i = 0; i < n; i++)
 844         {
 845             for (int j = 0; j < m; j++)
 846             {
 847                 if (mat[i][j] >= max)
 848                 {
 849                     max = mat[i][j];
 850                 }
 851
 852                 if (mat[i][j] <= min)
 853                 {
 854                     min = mat[i][j];
 855                 }
 856             }
 857         }
 858
 859         System.out.println(max + " " + min);
 860
 861         for (int i = 0; i < n; i++)
 862         {
 863             for (int j = 0; j < m; j++)
 864             {
 865                 int x = psize * i;
 866                 int y = psize * j;
 867
 868                 //      System.out.println(mat[i][j]);
 869                 float score = (float) (mat[i][j] - min) / (float) (max - min);
 870                 g.setColor(new Color(score, 0, 0));
 871                 g.fillRect(x, y, psize, psize);
 872
 873                 //      System.out.println(x + " " + y + " " + score);
 874             }
 875         }
 876     }
 877 }