JAL-98 JAL-1854 encapsulate 'magic number' threshold 3 in Conservation
[jalview.git] / src / jalview / analysis / Conservation.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
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
10  * of the License, or (at your option) any later version.
11  *  
12  * Jalview is distributed in the hope that it will be useful, but 
13  * WITHOUT ANY WARRANTY; without even the implied warranty 
14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
15  * PURPOSE.  See the GNU General Public License for more details.
16  * 
17  * You should have received a copy of the GNU General Public License
18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
19  * The Jalview Authors are detailed in the 'AUTHORS' file.
20  */
21 package jalview.analysis;
22
23 import jalview.datamodel.AlignmentAnnotation;
24 import jalview.datamodel.Annotation;
25 import jalview.datamodel.ResidueCount;
26 import jalview.datamodel.ResidueCount.SymbolCounts;
27 import jalview.datamodel.Sequence;
28 import jalview.datamodel.SequenceI;
29 import jalview.schemes.ResidueProperties;
30 import jalview.util.Comparison;
31
32 import java.awt.Color;
33 import java.util.List;
34 import java.util.Map;
35 import java.util.Map.Entry;
36 import java.util.TreeMap;
37 import java.util.Vector;
38
39 /**
40  * Calculates conservation values for a given set of sequences
41  */
42 public class Conservation
43 {
44   /*
45    * need to have a minimum of 3% of sequences with a residue
46    * for it to be included in the conservation calculation
47    */
48   private static final int THRESHOLD_PERCENT = 3;
49
50   private static final int TOUPPERCASE = 'a' - 'A';
51
52   SequenceI[] sequences;
53
54   int start;
55
56   int end;
57
58   Vector<int[]> seqNums; // vector of int vectors where first is sequence
59                          // checksum
60
61   int maxLength = 0; // used by quality calcs
62
63   boolean seqNumsChanged = false; // updated after any change via calcSeqNum;
64
65   /*
66    * a map per column with {property, conservation} where conservation value is
67    * 1 (property is conserved), 0 (absence of property is conserved) or -1
68    * (property is not conserved i.e. column has residues with and without it)
69    */
70   Map<String, Integer>[] total;
71
72   boolean canonicaliseAa = true; // if true then conservation calculation will
73
74   // map all symbols to canonical aa numbering
75   // rather than consider conservation of that
76   // symbol
77
78   /** Stores calculated quality values */
79   private Vector<Double> quality;
80
81   /** Stores maximum and minimum values of quality values */
82   private double[] qualityRange = new double[2];
83
84   private Sequence consSequence;
85
86   /*
87    * percentage of residues in a column to qualify for counting conservation
88    */
89   private int threshold;
90
91   private String name = "";
92
93   private int[][] cons2;
94
95   private String[] consSymbs;
96
97   /**
98    * Constructor using default threshold of 3%
99    * 
100    * @param name
101    *          Name of conservation
102    * @param sequences
103    *          sequences to be used in calculation
104    * @param start
105    *          start residue position
106    * @param end
107    *          end residue position
108    */
109   public Conservation(String name, List<SequenceI> sequences, int start,
110           int end)
111   {
112     this(name, THRESHOLD_PERCENT, sequences, start, end);
113   }
114
115   /**
116    * Constructor
117    * 
118    * @param name
119    *          Name of conservation
120    * @param threshold
121    *          percentage of sequences at or below which property conservation is
122    *          ignored
123    * @param sequences
124    *          sequences to be used in calculation
125    * @param start
126    *          start column position
127    * @param end
128    *          end column position
129    */
130   public Conservation(String name, int threshold,
131           List<SequenceI> sequences, int start, int end)
132   {
133     this.name = name;
134     this.threshold = threshold;
135     this.start = start;
136     this.end = end;
137
138     maxLength = end - start + 1; // default width includes bounds of
139     // calculation
140
141     int s, sSize = sequences.size();
142     SequenceI[] sarray = new SequenceI[sSize];
143     this.sequences = sarray;
144     try
145     {
146       for (s = 0; s < sSize; s++)
147       {
148         sarray[s] = sequences.get(s);
149         if (sarray[s].getLength() > maxLength)
150         {
151           maxLength = sarray[s].getLength();
152         }
153       }
154     } catch (ArrayIndexOutOfBoundsException ex)
155     {
156       // bail - another thread has modified the sequence array, so the current
157       // calculation is probably invalid.
158       this.sequences = new SequenceI[0];
159       maxLength = 0;
160     }
161   }
162
163   /**
164    * Translate sequence i into a numerical representation and store it in the
165    * i'th position of the seqNums array.
166    * 
167    * @param i
168    */
169   private void calcSeqNum(int i)
170   {
171     String sq = null; // for dumb jbuilder not-inited exception warning
172     int[] sqnum = null;
173
174     int sSize = sequences.length;
175
176     if ((i > -1) && (i < sSize))
177     {
178       sq = sequences[i].getSequenceAsString();
179
180       if (seqNums.size() <= i)
181       {
182         seqNums.addElement(new int[sq.length() + 1]);
183       }
184
185       if (sq.hashCode() != seqNums.elementAt(i)[0])
186       {
187         int j;
188         int len;
189         seqNumsChanged = true;
190         len = sq.length();
191
192         if (maxLength < len)
193         {
194           maxLength = len;
195         }
196
197         sqnum = new int[len + 1]; // better to always make a new array -
198         // sequence can change its length
199         sqnum[0] = sq.hashCode();
200
201         for (j = 1; j <= len; j++)
202         {
203           sqnum[j] = jalview.schemes.ResidueProperties.aaIndex[sq
204                   .charAt(j - 1)];
205         }
206
207         seqNums.setElementAt(sqnum, i);
208       }
209       else
210       {
211         System.out.println("SEQUENCE HAS BEEN DELETED!!!");
212       }
213     }
214     else
215     {
216       // JBPNote INFO level debug
217       System.err
218               .println("ERROR: calcSeqNum called with out of range sequence index for Alignment\n");
219     }
220   }
221
222   /**
223    * Calculates the conservation values for given set of sequences
224    */
225   public void calculate()
226   {
227     int height = sequences.length;
228
229     total = new Map[maxLength];
230
231     for (int column = start; column <= end; column++)
232     {
233       ResidueCount values = countResidues(column);
234
235       /*
236        * percentage count at or below which we ignore residues
237        */
238       int thresh = (threshold * height) / 100;
239
240       /*
241        * check observed residues in column and record whether each 
242        * physico-chemical property is conserved (+1), absence conserved (0),
243        * or not conserved (-1)
244        * Using TreeMap means properties are displayed in alphabetical order
245        */
246       Map<String, Integer> resultHash = new TreeMap<String, Integer>();
247       SymbolCounts symbolCounts = values.getSymbolCounts();
248       char[] symbols = symbolCounts.symbols;
249       int[] counts = symbolCounts.values;
250       for (int j = 0; j < symbols.length; j++)
251       {
252         char c = symbols[j];
253         if (counts[j] > thresh)
254         {
255           recordConservation(resultHash, String.valueOf(c));
256         }
257       }
258       if (values.getGapCount() > thresh)
259       {
260         recordConservation(resultHash, "-");
261       }
262
263       if (total.length > 0)
264       {
265         total[column - start] = resultHash;
266       }
267     }
268   }
269
270   /**
271    * Updates the conservation results for an observed residue
272    * 
273    * @param resultMap
274    *          a map of {property, conservation} where conservation value is +1
275    *          (all residues have the property), 0 (no residue has the property)
276    *          or -1 (some do, some don't)
277    * @param res
278    */
279   protected static void recordConservation(Map<String, Integer> resultMap,
280           String res)
281   {
282     res = res.toUpperCase();
283     for (Entry<String, Map<String, Integer>> property : ResidueProperties.propHash
284             .entrySet())
285     {
286       String propertyName = property.getKey();
287       Integer residuePropertyValue = property.getValue().get(res);
288
289       if (!resultMap.containsKey(propertyName))
290       {
291         /*
292          * first time we've seen this residue - note whether it has this property
293          */
294         if (residuePropertyValue != null)
295         {
296           resultMap.put(propertyName, residuePropertyValue);
297         }
298         else
299         {
300           /*
301            * unrecognised residue - use default value for property
302            */
303           resultMap.put(propertyName, property.getValue().get("-"));
304         }
305       }
306       else
307       {
308         Integer currentResult = resultMap.get(propertyName);
309         if (currentResult.intValue() != -1
310                 && !currentResult.equals(residuePropertyValue))
311         {
312           /*
313            * property is unconserved - residues seen both with and without it
314            */
315           resultMap.put(propertyName, Integer.valueOf(-1));
316         }
317       }
318     }
319   }
320
321   /**
322    * Counts residues (upper-cased) and gaps in the given column
323    * 
324    * @param column
325    * @return
326    */
327   protected ResidueCount countResidues(int column)
328   {
329     ResidueCount values = new ResidueCount(false);
330
331     for (int row = 0; row < sequences.length; row++)
332     {
333       if (sequences[row].getLength() > column)
334       {
335         char c = sequences[row].getCharAt(column);
336         if (canonicaliseAa)
337         {
338           int index = ResidueProperties.aaIndex[c];
339           c = index > 20 ? '-' : ResidueProperties.aa[index].charAt(0);
340         }
341         else
342         {
343           c = toUpperCase(c);
344         }
345         if (Comparison.isGap(c))
346         {
347           values.addGap();
348         }
349         else
350         {
351           values.add(c);
352         }
353       }
354       else
355       {
356         values.addGap();
357       }
358     }
359     return values;
360   }
361
362   /**
363    * Counts conservation and gaps for a column of the alignment
364    * 
365    * @return { 1 if fully conserved, else 0, gap count }
366    */
367   public int[] countConservationAndGaps(int column)
368   {
369     int gapCount = 0;
370     boolean fullyConserved = true;
371     int iSize = sequences.length;
372
373     if (iSize == 0)
374     {
375       return new int[] { 0, 0 };
376     }
377
378     char lastRes = '0';
379     for (int i = 0; i < iSize; i++)
380     {
381       if (column >= sequences[i].getLength())
382       {
383         gapCount++;
384         continue;
385       }
386
387       char c = sequences[i].getCharAt(column); // gaps do not have upper/lower case
388
389       if (Comparison.isGap((c)))
390       {
391         gapCount++;
392       }
393       else
394       {
395         c = toUpperCase(c);
396         if (lastRes == '0')
397         {
398           lastRes = c;
399         }
400         if (c != lastRes)
401         {
402           fullyConserved = false;
403         }
404       }
405     }
406
407     int[] r = new int[] { fullyConserved ? 1 : 0, gapCount };
408     return r;
409   }
410
411   /**
412    * Returns the upper-cased character if between 'a' and 'z', else the
413    * unchanged value
414    * 
415    * @param c
416    * @return
417    */
418   char toUpperCase(char c)
419   {
420     if ('a' <= c && c <= 'z')
421     {
422       c -= TOUPPERCASE;
423     }
424     return c;
425   }
426
427   /**
428    * Calculates the conservation sequence
429    * 
430    * @param positiveOnly
431    *          if true, calculate positive conservation; else calculate both
432    *          positive and negative conservation
433    * @param maxPercentageGaps
434    *          the percentage of gaps in a column, at or above which no
435    *          conservation is asserted
436    */
437   public void verdict(boolean positiveOnly, float maxPercentageGaps)
438   {
439     // TODO call this at the end of calculate(), should not be a public method
440
441     StringBuilder consString = new StringBuilder(end);
442
443     // NOTE THIS SHOULD CHECK IF THE CONSEQUENCE ALREADY
444     // EXISTS AND NOT OVERWRITE WITH '-', BUT THIS CASE
445     // DOES NOT EXIST IN JALVIEW 2.1.2
446     for (int i = 0; i < start; i++)
447     {
448       consString.append('-');
449     }
450     consSymbs = new String[end - start + 1];
451     for (int i = start; i <= end; i++)
452     {
453       int[] gapcons = countConservationAndGaps(i);
454       boolean fullyConserved = gapcons[0] == 1;
455       int totGaps = gapcons[1];
456       float pgaps = (totGaps * 100f) / sequences.length;
457
458       if (maxPercentageGaps > pgaps)
459       {
460         Map<String, Integer> resultHash = total[i - start];
461         int count = 0;
462         StringBuilder positives = new StringBuilder(64);
463         StringBuilder negatives = new StringBuilder(32);
464         for (String type : resultHash.keySet())
465         {
466           int result = resultHash.get(type).intValue();
467           if (result == -1)
468           {
469             /*
470              * not conserved (present or absent)
471              */
472             continue;
473           }
474           count++;
475           if (result == 1)
476           {
477             /*
478              * positively conserved property (all residues have it)
479              */
480             positives.append(positives.length() == 0 ? "" : " ");
481             positives.append(type);
482           }
483           if (result == 0 && !positiveOnly)
484           {
485             /*
486              * absense of property is conserved (all residues lack it)
487              */
488             negatives.append(negatives.length() == 0 ? "" : " ");
489             negatives.append("!").append(type);
490           }
491         }
492         if (negatives.length() > 0)
493         {
494           positives.append(" ").append(negatives);
495         }
496         consSymbs[i - start] = positives.toString();
497
498         if (count < 10)
499         {
500           consString.append(count); // Conserved props!=Identity
501         }
502         else
503         {
504           consString.append(fullyConserved ? "*" : "+");
505         }
506       }
507       else
508       {
509         consString.append('-');
510       }
511     }
512
513     consSequence = new Sequence(name, consString.toString(), start, end);
514   }
515
516   /**
517    * 
518    * 
519    * @return Conservation sequence
520    */
521   public Sequence getConsSequence()
522   {
523     return consSequence;
524   }
525
526   // From Alignment.java in jalview118
527   public void findQuality()
528   {
529     findQuality(0, maxLength - 1);
530   }
531
532   /**
533    * DOCUMENT ME!
534    */
535   private void percentIdentity2()
536   {
537     seqNums = new Vector<int[]>();
538     // calcSeqNum(s);
539     int i = 0, iSize = sequences.length;
540     // Do we need to calculate this again?
541     for (i = 0; i < iSize; i++)
542     {
543       calcSeqNum(i);
544     }
545
546     if ((cons2 == null) || seqNumsChanged)
547     {
548       cons2 = new int[maxLength][24];
549
550       // Initialize the array
551       for (int j = 0; j < 24; j++)
552       {
553         for (i = 0; i < maxLength; i++)
554         {
555           cons2[i][j] = 0;
556         }
557       }
558
559       int[] sqnum;
560       int j = 0;
561
562       while (j < sequences.length)
563       {
564         sqnum = seqNums.elementAt(j);
565
566         for (i = 1; i < sqnum.length; i++)
567         {
568           cons2[i - 1][sqnum[i]]++;
569         }
570
571         for (i = sqnum.length - 1; i < maxLength; i++)
572         {
573           cons2[i][23]++; // gap count
574         }
575
576         j++;
577       }
578
579       // unnecessary ?
580
581       /*
582        * for (int i=start; i <= end; i++) { int max = -1000; int maxi = -1; int
583        * maxj = -1;
584        * 
585        * for (int j=0;j<24;j++) { if (cons2[i][j] > max) { max = cons2[i][j];
586        * maxi = i; maxj = j; } } }
587        */
588     }
589   }
590
591   /**
592    * Calculates the quality of the set of sequences
593    * 
594    * @param startRes
595    *          Start residue
596    * @param endRes
597    *          End residue
598    */
599   public void findQuality(int startRes, int endRes)
600   {
601     quality = new Vector<Double>();
602
603     double max = -10000;
604     int[][] BLOSUM62 = ResidueProperties.getBLOSUM62();
605
606     // Loop over columns // JBPNote Profiling info
607     // long ts = System.currentTimeMillis();
608     // long te = System.currentTimeMillis();
609     percentIdentity2();
610
611     int size = seqNums.size();
612     int[] lengths = new int[size];
613     double tot, bigtot, sr, tmp;
614     double[] x, xx;
615     int l, j, i, ii, i2, k, seqNum;
616
617     for (l = 0; l < size; l++)
618     {
619       lengths[l] = seqNums.elementAt(l).length - 1;
620     }
621
622     for (j = startRes; j <= endRes; j++)
623     {
624       bigtot = 0;
625
626       // First Xr = depends on column only
627       x = new double[24];
628
629       for (ii = 0; ii < 24; ii++)
630       {
631         x[ii] = 0;
632
633         for (i2 = 0; i2 < 24; i2++)
634         {
635           x[ii] += (((double) cons2[j][i2] * BLOSUM62[ii][i2]) + 4);
636         }
637
638         x[ii] /= size;
639       }
640
641       // Now calculate D for each position and sum
642       for (k = 0; k < size; k++)
643       {
644         tot = 0;
645         xx = new double[24];
646         seqNum = (j < lengths[k]) ? seqNums.elementAt(k)[j + 1] : 23; // Sequence,
647                                                                       // or gap
648                                                                       // at the
649                                                                       // end
650
651         // This is a loop over r
652         for (i = 0; i < 23; i++)
653         {
654           sr = 0;
655
656           sr = (double) BLOSUM62[i][seqNum] + 4;
657
658           // Calculate X with another loop over residues
659           // System.out.println("Xi " + i + " " + x[i] + " " + sr);
660           xx[i] = x[i] - sr;
661
662           tot += (xx[i] * xx[i]);
663         }
664
665         bigtot += Math.sqrt(tot);
666       }
667
668       // This is the quality for one column
669       if (max < bigtot)
670       {
671         max = bigtot;
672       }
673
674       // bigtot = bigtot * (size-cons2[j][23])/size;
675       quality.addElement(new Double(bigtot));
676
677       // Need to normalize by gaps
678     }
679
680     double newmax = -10000;
681
682     for (j = startRes; j <= endRes; j++)
683     {
684       tmp = quality.elementAt(j).doubleValue();
685       tmp = ((max - tmp) * (size - cons2[j][23])) / size;
686
687       // System.out.println(tmp+ " " + j);
688       quality.setElementAt(new Double(tmp), j);
689
690       if (tmp > newmax)
691       {
692         newmax = tmp;
693       }
694     }
695
696     // System.out.println("Quality " + s);
697     qualityRange[0] = 0D;
698     qualityRange[1] = newmax;
699   }
700
701   /**
702    * Complete the given consensus and quuality annotation rows. Note: currently
703    * this method will enlarge the given annotation row if it is too small,
704    * otherwise will leave its length unchanged.
705    * 
706    * @param conservation
707    *          conservation annotation row
708    * @param quality2
709    *          (optional - may be null)
710    * @param istart
711    *          first column for conservation
712    * @param alWidth
713    *          extent of conservation
714    */
715   public void completeAnnotations(AlignmentAnnotation conservation,
716           AlignmentAnnotation quality2, int istart, int alWidth)
717   {
718     char[] sequence = getConsSequence().getSequence();
719     float minR;
720     float minG;
721     float minB;
722     float maxR;
723     float maxG;
724     float maxB;
725     minR = 0.3f;
726     minG = 0.0f;
727     minB = 0f;
728     maxR = 1.0f - minR;
729     maxG = 0.9f - minG;
730     maxB = 0f - minB; // scalable range for colouring both Conservation and
731     // Quality
732
733     float min = 0f;
734     float max = 11f;
735     float qmin = 0f;
736     float qmax = 0f;
737
738     char c;
739
740     if (conservation != null && conservation.annotations != null
741             && conservation.annotations.length < alWidth)
742     {
743       conservation.annotations = new Annotation[alWidth];
744     }
745
746     if (quality2 != null)
747     {
748       quality2.graphMax = (float) qualityRange[1];
749       if (quality2.annotations != null
750               && quality2.annotations.length < alWidth)
751       {
752         quality2.annotations = new Annotation[alWidth];
753       }
754       qmin = (float) qualityRange[0];
755       qmax = (float) qualityRange[1];
756     }
757
758     for (int i = istart; i < alWidth; i++)
759     {
760       float value = 0;
761
762       c = sequence[i];
763
764       if (Character.isDigit(c))
765       {
766         value = c - '0';
767       }
768       else if (c == '*')
769       {
770         value = 11;
771       }
772       else if (c == '+')
773       {
774         value = 10;
775       }
776
777       if (conservation != null)
778       {
779         float vprop = value - min;
780         vprop /= max;
781         int consp = i - start;
782         String conssym = (value > 0 && consp > -1 && consp < consSymbs.length) ? consSymbs[consp]
783                 : "";
784         conservation.annotations[i] = new Annotation(String.valueOf(c),
785                 conssym, ' ', value, new Color(minR + (maxR * vprop), minG
786                         + (maxG * vprop), minB + (maxB * vprop)));
787       }
788
789       // Quality calc
790       if (quality2 != null)
791       {
792         value = quality.elementAt(i).floatValue();
793         float vprop = value - qmin;
794         vprop /= qmax;
795         quality2.annotations[i] = new Annotation(" ",
796                 String.valueOf(value), ' ', value, new Color(minR
797                         + (maxR * vprop), minG + (maxG * vprop), minB
798                         + (maxB * vprop)));
799       }
800     }
801   }
802
803   /**
804    * construct and call the calculation methods on a new Conservation object
805    * 
806    * @param name
807    *          - name of conservation
808    * @param seqs
809    * @param start
810    *          first column in calculation window
811    * @param end
812    *          last column in calculation window
813    * @param positiveOnly
814    *          calculate positive (true) or positive and negative (false)
815    *          conservation
816    * @param maxPercentGaps
817    *          percentage of gaps tolerated in column
818    * @param calcQuality
819    *          flag indicating if alignment quality should be calculated
820    * @return Conservation object ready for use in visualization
821    */
822   public static Conservation calculateConservation(String name,
823           List<SequenceI> seqs, int start, int end, boolean positiveOnly,
824           int maxPercentGaps, boolean calcQuality)
825   {
826     Conservation cons = new Conservation(name, seqs, start, end);
827     cons.calculate();
828     cons.verdict(positiveOnly, maxPercentGaps);
829
830     if (calcQuality)
831     {
832       cons.findQuality();
833     }
834
835     return cons;
836   }
837
838   /**
839    * Returns the computed tooltip (annotation description) for a given column.
840    * The tip is empty if the conservation score is zero, otherwise holds the
841    * conserved properties (and, optionally, properties whose absence is
842    * conserved).
843    * 
844    * @param column
845    * @return
846    */
847   String getTooltip(int column)
848   {
849     char[] sequence = getConsSequence().getSequence();
850     char val = column < sequence.length ? sequence[column] : '-';
851     boolean hasConservation = val != '-' && val != '0';
852     int consp = column - start;
853     String tip = (hasConservation && consp > -1 && consp < consSymbs.length) ? consSymbs[consp]
854             : "";
855     return tip;
856   }
857 }