src/jalview/analysis/AlignSeq.java

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