src/jalview/analysis/scoremodels/FeatureDistanceModel.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.scoremodels;
  22
  23 import jalview.api.AlignmentViewPanel;
  24 import jalview.api.FeatureRenderer;
  25 import jalview.api.analysis.DistanceScoreModelI;
  26 import jalview.api.analysis.ViewBasedAnalysisI;
  27 import jalview.datamodel.AlignmentView;
  28 import jalview.datamodel.SeqCigar;
  29 import jalview.datamodel.SequenceFeature;
  30 import jalview.math.Matrix;
  31 import jalview.math.MatrixI;
  32 import jalview.util.SetUtils;
  33
  34 import java.util.HashMap;
  35 import java.util.HashSet;
  36 import java.util.List;
  37 import java.util.Map;
  38 import java.util.Set;
  39
  40 public class FeatureDistanceModel implements DistanceScoreModelI,
  41         ViewBasedAnalysisI
  42 {
  43   FeatureRenderer fr;
  44
  45   @Override
  46   public boolean configureFromAlignmentView(AlignmentViewPanel view)
  47
  48   {
  49     fr = view.cloneFeatureRenderer();
  50     return true;
  51   }
  52
  53   /**
  54    * Calculates a distance measure [i][j] between each pair of sequences as the
  55    * average number of features they have but do not share. That is, find the
  56    * features each sequence pair has at each column, ignore feature types they
  57    * have in common, and count the rest. The totals are normalised by the number
  58    * of columns processed.
  59    */
  60   @Override
  61   public MatrixI findDistances(AlignmentView seqData)
  62   {
  63     List<String> dft = fr.getDisplayedFeatureTypes();
  64     SeqCigar[] seqs = seqData.getSequences();
  65     int noseqs = seqs.length;
  66     int cpwidth = 0;// = seqData.getWidth();
  67     double[][] distances = new double[noseqs][noseqs];
  68     if (dft.isEmpty())
  69     {
  70       return new Matrix(distances);
  71     }
  72
  73     // need to get real position for view position
  74     int[] viscont = seqData.getVisibleContigs();
  75
  76     /*
  77      * scan each column, compute and add to each distance[i, j]
  78      * the number of feature types that seqi and seqj do not share
  79      */
  80     for (int vc = 0; vc < viscont.length; vc += 2)
  81     {
  82       for (int cpos = viscont[vc]; cpos <= viscont[vc + 1]; cpos++)
  83       {
  84         cpwidth++;
  85
  86         /*
  87          * first pass: record features types in column for each sequence
  88          */
  89         Map<SeqCigar, Set<String>> sfap = findFeatureTypesAtColumn(
  90                 seqs, cpos);
  91
  92         /*
  93          * count feature types on either i'th or j'th sequence but not both
  94          * and add this 'distance' measure to the total for [i, j] for j > i
  95          */
  96         for (int i = 0; i < (noseqs - 1); i++)
  97         {
  98           for (int j = i + 1; j < noseqs; j++)
  99           {
 100             int seqDistance = SetUtils.countDisjunction(sfap.get(seqs[i]),
 101                     sfap.get(seqs[j]));
 102             distances[i][j] += seqDistance;
 103           }
 104         }
 105       }
 106     }
 107
 108     /*
 109      * normalise the distance scores (summed over columns) by the
 110      * number of visible columns used in the calculation
 111      * and fill in the bottom half of the matrix
 112      */
 113     // TODO JAL-2424 cpwidth may be out by 1 - affects scores but not tree shape
 114     for (int i = 0; i < noseqs; i++)
 115     {
 116       for (int j = i + 1; j < noseqs; j++)
 117       {
 118         distances[i][j] /= cpwidth;
 119         distances[j][i] = distances[i][j];
 120       }
 121     }
 122     return new Matrix(distances);
 123   }
 124
 125   /**
 126    * Builds and returns a list (one per SeqCigar) of visible feature types at
 127    * the given column position
 128    *
 129    * @param seqs
 130    * @param columnPosition
 131    * @return
 132    */
 133   protected Map<SeqCigar, Set<String>> findFeatureTypesAtColumn(
 134           SeqCigar[] seqs, int columnPosition)
 135   {
 136     Map<SeqCigar, Set<String>> sfap = new HashMap<SeqCigar, Set<String>>();
 137     for (SeqCigar seq : seqs)
 138     {
 139       Set<String> types = new HashSet<String>();
 140       int spos = seq.findPosition(columnPosition);
 141       if (spos != -1)
 142       {
 143         List<SequenceFeature> sfs = fr.findFeaturesAtRes(seq.getRefSeq(),
 144                 spos);
 145         for (SequenceFeature sf : sfs)
 146         {
 147           types.add(sf.getType());
 148         }
 149       }
 150       sfap.put(seq, types);
 151     }
 152     return sfap;
 153   }
 154
 155   @Override
 156   public String getName()
 157   {
 158     return "Sequence Feature Similarity";
 159   }
 160
 161   @Override
 162   public boolean isDNA()
 163   {
 164     return true;
 165   }
 166
 167   @Override
 168   public boolean isProtein()
 169   {
 170     return true;
 171   }
 172
 173   @Override
 174   public String toString()
 175   {
 176     return "Score between sequences based on hamming distance between binary vectors marking features displayed at each column";
 177   }
 178 }