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