formatting
[jalview.git] / 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 }