X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FConservation.java;h=d1a3c37b45e1c932a06714eca9e53d45d91d99e6;hb=efa724edf32b5803396087cf7c94521e3d597836;hp=19a6514069576cbae7abb15b7e9add0c7d59eb0e;hpb=2bd3c28fe234c6883bec5412db83a809ab8d1500;p=jalview.git diff --git a/src/jalview/analysis/Conservation.java b/src/jalview/analysis/Conservation.java index 19a6514..d1a3c37 100755 --- a/src/jalview/analysis/Conservation.java +++ b/src/jalview/analysis/Conservation.java @@ -20,26 +20,38 @@ */ package jalview.analysis; +import jalview.analysis.scoremodels.ScoreMatrix; +import jalview.analysis.scoremodels.ScoreModels; import jalview.datamodel.AlignmentAnnotation; import jalview.datamodel.Annotation; +import jalview.datamodel.ResidueCount; +import jalview.datamodel.ResidueCount.SymbolCounts; import jalview.datamodel.Sequence; import jalview.datamodel.SequenceI; import jalview.schemes.ResidueProperties; +import jalview.util.Comparison; import java.awt.Color; -import java.util.Hashtable; import java.util.List; import java.util.Map; +import java.util.Map.Entry; +import java.util.SortedMap; +import java.util.TreeMap; import java.util.Vector; /** * Calculates conservation values for a given set of sequences - * - * @author $author$ - * @version $Revision$ */ public class Conservation { + /* + * need to have a minimum of 3% of sequences with a residue + * for it to be included in the conservation calculation + */ + private static final int THRESHOLD_PERCENT = 3; + + private static final int TOUPPERCASE = 'a' - 'A'; + SequenceI[] sequences; int start; @@ -53,6 +65,11 @@ public class Conservation boolean seqNumsChanged = false; // updated after any change via calcSeqNum; + /* + * a map per column with {property, conservation} where conservation value is + * 1 (property is conserved), 0 (absence of property is conserved) or -1 + * (property is not conserved i.e. column has residues with and without it) + */ Map[] total; boolean canonicaliseAa = true; // if true then conservation calculation will @@ -69,6 +86,9 @@ public class Conservation private Sequence consSequence; + /* + * percentage of residues in a column to qualify for counting conservation + */ private int threshold; private String name = ""; @@ -78,12 +98,10 @@ public class Conservation private String[] consSymbs; /** - * Creates a new Conservation object. + * Constructor using default threshold of 3% * * @param name * Name of conservation - * @param threshold - * to count the residues in residueHash(). commonly used value is 3 * @param sequences * sequences to be used in calculation * @param start @@ -91,6 +109,27 @@ public class Conservation * @param end * end residue position */ + public Conservation(String name, List sequences, int start, + int end) + { + this(name, THRESHOLD_PERCENT, sequences, start, end); + } + + /** + * Constructor + * + * @param name + * Name of conservation + * @param threshold + * percentage of sequences at or below which property conservation is + * ignored + * @param sequences + * sequences to be used in calculation + * @param start + * start column position + * @param end + * end column position + */ public Conservation(String name, int threshold, List sequences, int start, int end) { @@ -125,27 +164,30 @@ public class Conservation } /** - * Translate sequence i into a numerical representation and store it in the - * i'th position of the seqNums array. + * Translate sequence i into score matrix indices and store it in the i'th + * position of the seqNums array. * * @param i + * @param sm */ - private void calcSeqNum(int i) + private void calcSeqNum(int i, ScoreMatrix sm) { - String sq = null; // for dumb jbuilder not-inited exception warning - int[] sqnum = null; - + int gapIndex = sm.getMatrixIndex(' '); int sSize = sequences.length; if ((i > -1) && (i < sSize)) { - sq = sequences[i].getSequenceAsString(); + String sq = sequences[i].getSequenceAsString(); if (seqNums.size() <= i) { seqNums.addElement(new int[sq.length() + 1]); } + /* + * the first entry in the array is the sequence's hashcode, + * following entries are matrix indices of sequence characters + */ if (sq.hashCode() != seqNums.elementAt(i)[0]) { int j; @@ -158,14 +200,18 @@ public class Conservation maxLength = len; } - sqnum = new int[len + 1]; // better to always make a new array - + int[] sqnum = new int[len + 1]; // better to always make a new array - // sequence can change its length sqnum[0] = sq.hashCode(); for (j = 1; j <= len; j++) { - sqnum[j] = jalview.schemes.ResidueProperties.aaIndex[sq - .charAt(j - 1)]; + // sqnum[j] = ResidueProperties.aaIndex[sq.charAt(j - 1)]; + sqnum[j] = sm.getMatrixIndex(sq.charAt(j - 1)); + if (sqnum[j] == -1) + { + sqnum[j] = gapIndex; + } } seqNums.setElementAt(sqnum, i); @@ -188,148 +234,187 @@ public class Conservation */ public void calculate() { - int thresh, j, jSize = sequences.length; - int[] values; // Replaces residueHash - char c; + int height = sequences.length; - total = new Hashtable[maxLength]; + total = new Map[maxLength]; - for (int i = start; i <= end; i++) + for (int column = start; column <= end; column++) { - values = new int[255]; + ResidueCount values = countResidues(column); - for (j = 0; j < jSize; j++) + /* + * percentage count at or below which we ignore residues + */ + int thresh = (threshold * height) / 100; + + /* + * check observed residues in column and record whether each + * physico-chemical property is conserved (+1), absence conserved (0), + * or not conserved (-1) + * Using TreeMap means properties are displayed in alphabetical order + */ + SortedMap resultHash = new TreeMap(); + SymbolCounts symbolCounts = values.getSymbolCounts(); + char[] symbols = symbolCounts.symbols; + int[] counts = symbolCounts.values; + for (int j = 0; j < symbols.length; j++) { - if (sequences[j].getLength() > i) + char c = symbols[j]; + if (counts[j] > thresh) { - c = sequences[j].getCharAt(i); - - if (canonicaliseAa) - { // lookup the base aa code symbol - c = (char) ResidueProperties.aaIndex[sequences[j].getCharAt(i)]; - if (c > 20) - { - c = '-'; - } - else - { - // recover canonical aa symbol - c = ResidueProperties.aa[c].charAt(0); - } - } - else - { - // original behaviour - operate on ascii symbols directly - // No need to check if its a '-' - if (c == '.' || c == ' ') - { - c = '-'; - } - - c = toUpperCase(c); - } - values[c]++; + recordConservation(resultHash, String.valueOf(c)); + } + } + if (values.getGapCount() > thresh) + { + recordConservation(resultHash, "-"); + } + + if (total.length > 0) + { + total[column - start] = resultHash; + } + } + } + + /** + * Updates the conservation results for an observed residue + * + * @param resultMap + * a map of {property, conservation} where conservation value is +1 + * (all residues have the property), 0 (no residue has the property) + * or -1 (some do, some don't) + * @param res + */ + protected static void recordConservation(Map resultMap, + String res) + { + res = res.toUpperCase(); + for (Entry> property : ResidueProperties.propHash + .entrySet()) + { + String propertyName = property.getKey(); + Integer residuePropertyValue = property.getValue().get(res); + + if (!resultMap.containsKey(propertyName)) + { + /* + * first time we've seen this residue - note whether it has this property + */ + if (residuePropertyValue != null) + { + resultMap.put(propertyName, residuePropertyValue); } else { - values['-']++; + /* + * unrecognised residue - use default value for property + */ + resultMap.put(propertyName, property.getValue().get("-")); } } + else + { + Integer currentResult = resultMap.get(propertyName); + if (currentResult.intValue() != -1 + && !currentResult.equals(residuePropertyValue)) + { + /* + * property is unconserved - residues seen both with and without it + */ + resultMap.put(propertyName, Integer.valueOf(-1)); + } + } + } + } - // What is the count threshold to count the residues in residueHash() - thresh = (threshold * (jSize)) / 100; + /** + * Counts residues (upper-cased) and gaps in the given column + * + * @param column + * @return + */ + protected ResidueCount countResidues(int column) + { + ResidueCount values = new ResidueCount(false); - // loop over all the found residues - Hashtable resultHash = new Hashtable(); - for (char v = '-'; v < 'Z'; v++) + for (int row = 0; row < sequences.length; row++) + { + if (sequences[row].getLength() > column) { - - if (values[v] > thresh) + char c = sequences[row].getCharAt(column); + if (canonicaliseAa) { - String res = String.valueOf(v); - - // Now loop over the properties - for (String type : ResidueProperties.propHash.keySet()) - { - Hashtable ht = (Hashtable) ResidueProperties.propHash - .get(type); - - // Have we ticked this before? - if (!resultHash.containsKey(type)) - { - if (ht.containsKey(res)) - { - resultHash.put(type, ht.get(res)); - } - else - { - resultHash.put(type, ht.get("-")); - } - } - else if (!resultHash.get(type).equals(ht.get(res))) - { - resultHash.put(type, new Integer(-1)); - } - } + int index = ResidueProperties.aaIndex[c]; + c = index > 20 ? '-' : ResidueProperties.aa[index].charAt(0); + } + else + { + c = toUpperCase(c); + } + if (Comparison.isGap(c)) + { + values.addGap(); + } + else + { + values.add(c); } } - - if (total.length > 0) + else { - total[i - start] = resultHash; + values.addGap(); } } + return values; } - /***************************************************************************** - * count conservation for the j'th column of the alignment + /** + * Counts conservation and gaps for a column of the alignment * - * @return { gap count, conserved residue count} + * @return { 1 if fully conserved, else 0, gap count } */ - public int[] countConsNGaps(int j) + public int[] countConservationAndGaps(int column) { - int count = 0; - int cons = 0; - int nres = 0; - int[] r = new int[2]; - char f = '$'; - int i, iSize = sequences.length; - char c; + int gapCount = 0; + boolean fullyConserved = true; + int iSize = sequences.length; - for (i = 0; i < iSize; i++) + if (iSize == 0) + { + return new int[] { 0, 0 }; + } + + char lastRes = '0'; + for (int i = 0; i < iSize; i++) { - if (j >= sequences[i].getLength()) + if (column >= sequences[i].getLength()) { - count++; + gapCount++; continue; } - c = sequences[i].getCharAt(j); // gaps do not have upper/lower case + char c = sequences[i].getCharAt(column); // gaps do not have upper/lower case - if (jalview.util.Comparison.isGap((c))) + if (Comparison.isGap((c))) { - count++; + gapCount++; } else { c = toUpperCase(c); - nres++; - - if (nres == 1) + if (lastRes == '0') { - f = c; - cons++; + lastRes = c; } - else if (f == c) + if (c != lastRes) { - cons++; + fullyConserved = false; } } } - r[0] = (nres == cons) ? 1 : 0; - r[1] = count; - + int[] r = new int[] { fullyConserved ? 1 : 0, gapCount }; return r; } @@ -344,7 +429,7 @@ public class Conservation { if ('a' <= c && c <= 'z') { - c -= (32); // 32 = 'a' - 'A' + c -= TOUPPERCASE; } return c; } @@ -352,15 +437,18 @@ public class Conservation /** * Calculates the conservation sequence * - * @param consflag - * if true, positive conservation; false calculates negative - * conservation - * @param percentageGaps - * commonly used value is 25 + * @param positiveOnly + * if true, calculate positive conservation; else calculate both + * positive and negative conservation + * @param maxPercentageGaps + * the percentage of gaps in a column, at or above which no + * conservation is asserted */ - public void verdict(boolean consflag, float percentageGaps) + public void verdict(boolean positiveOnly, float maxPercentageGaps) { - StringBuffer consString = new StringBuffer(); + // TODO call this at the end of calculate(), should not be a public method + + StringBuilder consString = new StringBuilder(end); // NOTE THIS SHOULD CHECK IF THE CONSEQUENCE ALREADY // EXISTS AND NOT OVERWRITE WITH '-', BUT THIS CASE @@ -372,44 +460,50 @@ public class Conservation consSymbs = new String[end - start + 1]; for (int i = start; i <= end; i++) { - int[] gapcons = countConsNGaps(i); + int[] gapcons = countConservationAndGaps(i); + boolean fullyConserved = gapcons[0] == 1; int totGaps = gapcons[1]; - float pgaps = ((float) totGaps * 100) / sequences.length; - consSymbs[i - start] = new String(); + float pgaps = (totGaps * 100f) / sequences.length; - if (percentageGaps > pgaps) + if (maxPercentageGaps > pgaps) { Map resultHash = total[i - start]; - // Now find the verdict int count = 0; + StringBuilder positives = new StringBuilder(64); + StringBuilder negatives = new StringBuilder(32); for (String type : resultHash.keySet()) { int result = resultHash.get(type).intValue(); - // Do we want to count +ve conservation or +ve and -ve cons.? - if (consflag) + if (result == -1) + { + /* + * not conserved (present or absent) + */ + continue; + } + count++; + if (result == 1) { - if (result == 1) - { - consSymbs[i - start] = type + " " + consSymbs[i - start]; - count++; - } + /* + * positively conserved property (all residues have it) + */ + positives.append(positives.length() == 0 ? "" : " "); + positives.append(type); } - else + if (result == 0 && !positiveOnly) { - if (result != -1) - { - if (result == 0) - { - consSymbs[i - start] = consSymbs[i - start] + " !" + type; - } - else - { - consSymbs[i - start] = type + " " + consSymbs[i - start]; - } - count++; - } + /* + * absense of property is conserved (all residues lack it) + */ + negatives.append(negatives.length() == 0 ? "" : " "); + negatives.append("!").append(type); } } + if (negatives.length() > 0) + { + positives.append(" ").append(negatives); + } + consSymbs[i - start] = positives.toString(); if (count < 10) { @@ -417,7 +511,7 @@ public class Conservation } else { - consString.append((gapcons[0] == 1) ? "*" : "+"); + consString.append(fullyConserved ? "*" : "+"); } } else @@ -434,7 +528,7 @@ public class Conservation * * @return Conservation sequence */ - public Sequence getConsSequence() + public SequenceI getConsSequence() { return consSequence; } @@ -447,37 +541,32 @@ public class Conservation /** * DOCUMENT ME! + * + * @param sm */ - private void percentIdentity2() + private void percentIdentity(ScoreMatrix sm) { seqNums = new Vector(); - // calcSeqNum(s); int i = 0, iSize = sequences.length; // Do we need to calculate this again? for (i = 0; i < iSize; i++) { - calcSeqNum(i); + calcSeqNum(i, sm); } + int gapIndex = sm.getMatrixIndex(' '); + if ((cons2 == null) || seqNumsChanged) { + // FIXME remove magic number 24 without changing calc + // sm.getSize() returns 25 so doesn't quite do it... cons2 = new int[maxLength][24]; - // Initialize the array - for (int j = 0; j < 24; j++) - { - for (i = 0; i < maxLength; i++) - { - cons2[i][j] = 0; - } - } - - int[] sqnum; int j = 0; while (j < sequences.length) { - sqnum = seqNums.elementAt(j); + int[] sqnum = seqNums.elementAt(j); for (i = 1; i < sqnum.length; i++) { @@ -486,21 +575,10 @@ public class Conservation for (i = sqnum.length - 1; i < maxLength; i++) { - cons2[i][23]++; // gap count + cons2[i][gapIndex]++; // gap count } - j++; } - - // unnecessary ? - - /* - * for (int i=start; i <= end; i++) { int max = -1000; int maxi = -1; int - * maxj = -1; - * - * for (int j=0;j<24;j++) { if (cons2[i][j] > max) { max = cons2[i][j]; - * maxi = i; maxj = j; } } } - */ } } @@ -516,13 +594,15 @@ public class Conservation { quality = new Vector(); - double max = -10000; - int[][] BLOSUM62 = ResidueProperties.getBLOSUM62(); + double max = -Double.MAX_VALUE; + ScoreMatrix blosum62 = ScoreModels.getInstance().getBlosum62(); + float[][] blosumScores = blosum62.getMatrix(); + int gapIndex = blosum62.getMatrixIndex(' '); // Loop over columns // JBPNote Profiling info // long ts = System.currentTimeMillis(); // long te = System.currentTimeMillis(); - percentIdentity2(); + percentIdentity(blosum62); int size = seqNums.size(); int[] lengths = new int[size]; @@ -535,20 +615,24 @@ public class Conservation lengths[l] = seqNums.elementAt(l).length - 1; } + // todo ? remove '*' (unused?) from score matrix and + // use getSize() here instead of getSize() - 1 ?? + final int symbolCount = blosum62.getSize() - 1; // 24; + for (j = startRes; j <= endRes; j++) { bigtot = 0; // First Xr = depends on column only - x = new double[24]; + x = new double[symbolCount]; - for (ii = 0; ii < 24; ii++) + for (ii = 0; ii < symbolCount; ii++) { x[ii] = 0; - for (i2 = 0; i2 < 24; i2++) + for (i2 = 0; i2 < symbolCount; i2++) { - x[ii] += (((double) cons2[j][i2] * BLOSUM62[ii][i2]) + 4); + x[ii] += (((double) cons2[j][i2] * blosumScores[ii][i2]) + 4); } x[ii] /= size; @@ -558,16 +642,16 @@ public class Conservation for (k = 0; k < size; k++) { tot = 0; - xx = new double[24]; - seqNum = (j < lengths[k]) ? seqNums.elementAt(k)[j + 1] - : 23; // Sequence, or gap at the end + xx = new double[symbolCount]; + seqNum = (j < lengths[k]) ? seqNums.elementAt(k)[j + 1] : gapIndex; + // Sequence, or gap at the end // This is a loop over r - for (i = 0; i < 23; i++) + for (i = 0; i < symbolCount - 1; i++) { sr = 0; - sr = (double) BLOSUM62[i][seqNum] + 4; + sr = (double) blosumScores[i][seqNum] + 4; // Calculate X with another loop over residues // System.out.println("Xi " + i + " " + x[i] + " " + sr); @@ -591,12 +675,13 @@ public class Conservation // Need to normalize by gaps } - double newmax = -10000; + double newmax = -Double.MAX_VALUE; for (j = startRes; j <= endRes; j++) { tmp = quality.elementAt(j).doubleValue(); - tmp = ((max - tmp) * (size - cons2[j][23])) / size; + // tmp = ((max - tmp) * (size - cons2[j][23])) / size; + tmp = ((max - tmp) * (size - cons2[j][gapIndex])) / size; // System.out.println(tmp+ " " + j); quality.setElementAt(new Double(tmp), j); @@ -719,35 +804,53 @@ public class Conservation * * @param name * - name of conservation - * @param threshold - * - minimum number of conserved residues needed to indicate - * conservation (typically 3) * @param seqs * @param start * first column in calculation window * @param end * last column in calculation window - * @param posOrNeg - * positive (true) or negative (false) conservation - * @param consPercGaps + * @param positiveOnly + * calculate positive (true) or positive and negative (false) + * conservation + * @param maxPercentGaps * percentage of gaps tolerated in column * @param calcQuality * flag indicating if alignment quality should be calculated * @return Conservation object ready for use in visualization */ public static Conservation calculateConservation(String name, - int threshold, List seqs, int start, int end, - boolean posOrNeg, int consPercGaps, boolean calcQuality) + List seqs, int start, int end, boolean positiveOnly, + int maxPercentGaps, boolean calcQuality) { - Conservation cons = new Conservation(name, threshold, seqs, start, end); + Conservation cons = new Conservation(name, seqs, start, end); cons.calculate(); - cons.verdict(posOrNeg, consPercGaps); - + cons.verdict(positiveOnly, maxPercentGaps); + if (calcQuality) { cons.findQuality(); } - + return cons; } + + /** + * Returns the computed tooltip (annotation description) for a given column. + * The tip is empty if the conservation score is zero, otherwise holds the + * conserved properties (and, optionally, properties whose absence is + * conserved). + * + * @param column + * @return + */ + String getTooltip(int column) + { + char[] sequence = getConsSequence().getSequence(); + char val = column < sequence.length ? sequence[column] : '-'; + boolean hasConservation = val != '-' && val != '0'; + int consp = column - start; + String tip = (hasConservation && consp > -1 && consp < consSymbs.length) ? consSymbs[consp] + : ""; + return tip; + } }