src/jalview/analysis/TreeBuilder.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.api.analysis.ScoreModelI;
  24 import jalview.api.analysis.SimilarityParamsI;
  25 import jalview.datamodel.AlignmentView;
  26 import jalview.datamodel.BinaryNode;
  27 import jalview.datamodel.CigarArray;
  28 import jalview.datamodel.SeqCigar;
  29 import jalview.datamodel.SequenceI;
  30 import jalview.datamodel.SequenceNode;
  31 import jalview.viewmodel.AlignmentViewport;
  32
  33 import java.util.BitSet;
  34 import java.util.Vector;
  35
  36 public abstract class TreeBuilder extends TreeEngine
  37 {
  38   public static final String AVERAGE_DISTANCE = "AV";
  39
  40   public static final String NEIGHBOUR_JOINING = "NJ";
  41
  42   protected SequenceI[] sequences;
  43
  44   public AlignmentView seqData;
  45
  46   private AlignmentView seqStrings;
  47
  48   /**
  49    * Constructor
  50    *
  51    * @param av
  52    * @param sm
  53    * @param scoreParameters
  54    */
  55   public TreeBuilder(AlignmentViewport av, ScoreModelI sm,
  56           SimilarityParamsI scoreParameters)
  57   {
  58     int start, end;
  59     boolean selview = av.getSelectionGroup() != null
  60             && av.getSelectionGroup().getSize() > 1;
  61     seqStrings = av.getAlignmentView(selview);
  62     if (!selview)
  63     {
  64       start = 0;
  65       end = av.getAlignment().getWidth();
  66       this.sequences = av.getAlignment().getSequencesArray();
  67     }
  68     else
  69     {
  70       start = av.getSelectionGroup().getStartRes();
  71       end = av.getSelectionGroup().getEndRes() + 1;
  72       this.sequences = av.getSelectionGroup()
  73               .getSequencesInOrder(av.getAlignment());
  74     }
  75
  76     init(seqStrings, start, end);
  77
  78     computeTree(sm, scoreParameters);
  79   }
  80
  81   public SequenceI[] getSequences()
  82   {
  83     return sequences;
  84   }
  85
  86   /**
  87    *
  88    * @return true if tree has real distances
  89    */
  90   public boolean hasDistances()
  91   {
  92     return true;
  93   }
  94
  95   /**
  96    *
  97    * @return true if tree has real bootstrap values
  98    */
  99   public boolean hasBootstrap()
 100   {
 101     return false;
 102   }
 103
 104   public boolean hasRootDistance()
 105   {
 106     return true;
 107   }
 108
 109   /**
 110    * Calculates the tree using the given score model and parameters, and the
 111    * configured tree type
 112    * <p>
 113    * If the score model computes pairwise distance scores, then these are used
 114    * directly to derive the tree
 115    * <p>
 116    * If the score model computes similarity scores, then the range of the scores
 117    * is reversed to give a distance measure, and this is used to derive the tree
 118    *
 119    * @param sm
 120    * @param scoreOptions
 121    */
 122   protected void computeTree(ScoreModelI sm, SimilarityParamsI scoreOptions)
 123   {
 124     distances = sm.findDistances(seqData, scoreOptions);
 125
 126     makeLeaves();
 127
 128     noClus = clusters.size();
 129
 130     cluster();
 131   }
 132
 133   protected void init(AlignmentView seqView, int start, int end)
 134   {
 135     this.node = new Vector<BinaryNode>();
 136     if (seqView != null)
 137     {
 138       this.seqData = seqView;
 139     }
 140     else
 141     {
 142       SeqCigar[] seqs = new SeqCigar[sequences.length];
 143       for (int i = 0; i < sequences.length; i++)
 144       {
 145         seqs[i] = new SeqCigar(sequences[i], start, end);
 146       }
 147       CigarArray sdata = new CigarArray(seqs);
 148       sdata.addOperation(CigarArray.M, end - start + 1);
 149       this.seqData = new AlignmentView(sdata, start);
 150     }
 151
 152     /*
 153      * count the non-null sequences
 154      */
 155     noseqs = 0;
 156
 157     done = new BitSet();
 158
 159     for (SequenceI seq : sequences)
 160     {
 161       if (seq != null)
 162       {
 163         noseqs++;
 164       }
 165     }
 166   }
 167
 168   /**
 169    * Start by making a cluster for each individual sequence
 170    */
 171   void makeLeaves()
 172   {
 173     clusters = new Vector<BitSet>();
 174
 175     for (int i = 0; i < noseqs; i++)
 176     {
 177       SequenceNode sn = new SequenceNode();
 178
 179       sn.setElement(sequences[i]);
 180       sn.setName(sequences[i].getName());
 181       node.addElement(sn);
 182       BitSet bs = new BitSet();
 183       bs.set(i);
 184       clusters.addElement(bs);
 185     }
 186   }
 187
 188   public AlignmentView getOriginalData()
 189   {
 190     return seqStrings;
 191   }
 192
 193 }