mev-4.0.01/source/org/tigr/microarray/mev/cluster/algorithm/impl/terrain/Terrain.java

Code
Comments
Other
Rev Date Author Line
2 26 Feb 07 jari 1 /*
2 26 Feb 07 jari 2 Copyright @ 1999-2003, The Institute for Genomic Research (TIGR).
2 26 Feb 07 jari 3 All rights reserved.
2 26 Feb 07 jari 4 */
2 26 Feb 07 jari 5 /*
2 26 Feb 07 jari 6  * $RCSfile: Terrain.java,v $
2 26 Feb 07 jari 7  * $Revision: 1.3 $
2 26 Feb 07 jari 8  * $Date: 2006/02/23 20:59:46 $
2 26 Feb 07 jari 9  * $Author: caliente $
2 26 Feb 07 jari 10  * $State: Exp $
2 26 Feb 07 jari 11  */
2 26 Feb 07 jari 12 package org.tigr.microarray.mev.cluster.algorithm.impl.terrain;
2 26 Feb 07 jari 13
2 26 Feb 07 jari 14 import java.util.ArrayList;
2 26 Feb 07 jari 15 import java.util.Arrays;
2 26 Feb 07 jari 16
2 26 Feb 07 jari 17 import javax.vecmath.Vector2f;
2 26 Feb 07 jari 18
2 26 Feb 07 jari 19 import org.tigr.microarray.mev.cluster.Cluster;
2 26 Feb 07 jari 20 import org.tigr.microarray.mev.cluster.Node;
2 26 Feb 07 jari 21 import org.tigr.microarray.mev.cluster.NodeList;
2 26 Feb 07 jari 22 import org.tigr.microarray.mev.cluster.NodeValue;
2 26 Feb 07 jari 23 import org.tigr.microarray.mev.cluster.NodeValueList;
2 26 Feb 07 jari 24 import org.tigr.microarray.mev.cluster.algorithm.AbortException;
2 26 Feb 07 jari 25 import org.tigr.microarray.mev.cluster.algorithm.AbstractAlgorithm;
2 26 Feb 07 jari 26 import org.tigr.microarray.mev.cluster.algorithm.AlgorithmData;
2 26 Feb 07 jari 27 import org.tigr.microarray.mev.cluster.algorithm.AlgorithmEvent;
2 26 Feb 07 jari 28 import org.tigr.microarray.mev.cluster.algorithm.AlgorithmException;
2 26 Feb 07 jari 29 import org.tigr.microarray.mev.cluster.algorithm.AlgorithmParameters;
2 26 Feb 07 jari 30 import org.tigr.microarray.mev.cluster.algorithm.impl.ExperimentUtil;
2 26 Feb 07 jari 31 import org.tigr.microarray.mev.cluster.algorithm.impl.util.FloatArray;
2 26 Feb 07 jari 32 import org.tigr.microarray.mev.cluster.algorithm.impl.util.IntArray;
2 26 Feb 07 jari 33 import org.tigr.util.FloatMatrix;
2 26 Feb 07 jari 34
2 26 Feb 07 jari 35 public class Terrain extends AbstractAlgorithm implements InterfaceToObjects {
2 26 Feb 07 jari 36
2 26 Feb 07 jari 37     private FloatMatrix experiment;
2 26 Feb 07 jari 38     private IntArray[] links;
2 26 Feb 07 jari 39     private FloatArray[] distances;
2 26 Feb 07 jari 40     private float[][] coords;
2 26 Feb 07 jari 41     private boolean stop = false;
2 26 Feb 07 jari 42
2 26 Feb 07 jari 43     /**
2 26 Feb 07 jari 44      * This method execute calculation and return result,
2 26 Feb 07 jari 45      * stored in <code>AlgorithmData</code> class.
2 26 Feb 07 jari 46      *
2 26 Feb 07 jari 47      * @param data the data to be calculated.
2 26 Feb 07 jari 48      */
2 26 Feb 07 jari 49     public AlgorithmData execute(AlgorithmData data) throws AlgorithmException {
2 26 Feb 07 jari 50         AlgorithmParameters map = data.getParams();
2 26 Feb 07 jari 51         int function = map.getInt("distance-function", PEARSON);
2 26 Feb 07 jari 52         float factor = map.getFloat("distance-factor", 1.0f);
2 26 Feb 07 jari 53         boolean absolute = map.getBoolean("distance-absolute", false);
2 26 Feb 07 jari 54         int k_neighbours = map.getInt("neighbors");
2 26 Feb 07 jari 55         this.experiment = data.getMatrix("experiment");
2 26 Feb 07 jari 56
2 26 Feb 07 jari 57         // TODO: change algo to work without copy of the experiment
2 26 Feb 07 jari 58         if (!map.getBoolean("use-genes")) {
2 26 Feb 07 jari 59             FloatMatrix matrix = new FloatMatrix(experiment.getColumnDimension(), experiment.getRowDimension());
2 26 Feb 07 jari 60             for (int i=0; i<experiment.getRowDimension(); i++)
2 26 Feb 07 jari 61                 for (int j=0; j<experiment.getColumnDimension(); j++)
2 26 Feb 07 jari 62                     matrix.set(j, i, experiment.get(i, j));
2 26 Feb 07 jari 63             this.experiment = matrix;
2 26 Feb 07 jari 64         }
2 26 Feb 07 jari 65
2 26 Feb 07 jari 66         int nGenes = this.experiment.getRowDimension();
2 26 Feb 07 jari 67         int sum = nGenes*(nGenes+1)/2;
2 26 Feb 07 jari 68         int step = sum/100+1;
2 26 Feb 07 jari 69
2 26 Feb 07 jari 70         //cache distances
2 26 Feb 07 jari 71         MergeJoinBag bag = new MergeJoinBag(nGenes, Math.min(k_neighbours, nGenes));
2 26 Feb 07 jari 72
2 26 Feb 07 jari 73         AlgorithmEvent event = new AlgorithmEvent(this, AlgorithmEvent.SET_UNITS, 100, "Analyzing Links...");
2 26 Feb 07 jari 74         fireValueChanged(event);
2 26 Feb 07 jari 75         event.setId(AlgorithmEvent.PROGRESS_VALUE);
2 26 Feb 07 jari 76
2 26 Feb 07 jari 77         int progress = 0;
2 26 Feb 07 jari 78         for (int nCurIndOuter=0; nCurIndOuter<nGenes; nCurIndOuter++) {
2 26 Feb 07 jari 79             if (this.stop) {
2 26 Feb 07 jari 80                 throw new AbortException();
2 26 Feb 07 jari 81             }
2 26 Feb 07 jari 82             progress++;
2 26 Feb 07 jari 83             // calculation
2 26 Feb 07 jari 84             for (int nCurIndInner=nCurIndOuter+1; nCurIndInner<nGenes; nCurIndInner++) {
2 26 Feb 07 jari 85                 float value = ExperimentUtil.geneDistance(this.experiment, null, nCurIndOuter, nCurIndInner, function, factor, absolute);
2 26 Feb 07 jari 86                 //value = value*value;
2 26 Feb 07 jari 87                 bag.Assert(nCurIndOuter, nCurIndInner, value);
2 26 Feb 07 jari 88                 // progress events handling
2 26 Feb 07 jari 89                 progress++;
2 26 Feb 07 jari 90                 if (progress%step == 0) {
2 26 Feb 07 jari 91                     event.setIntValue(progress/step);
2 26 Feb 07 jari 92                     event.setDescription("Analysing Links...");
2 26 Feb 07 jari 93                     fireValueChanged(event);
2 26 Feb 07 jari 94                 }
2 26 Feb 07 jari 95             }
2 26 Feb 07 jari 96         }
2 26 Feb 07 jari 97         bag.Normalize(0.01f);
2 26 Feb 07 jari 98
2 26 Feb 07 jari 99         this.links = new IntArray[nGenes];
2 26 Feb 07 jari 100         this.distances = new FloatArray[nGenes];
2 26 Feb 07 jari 101         for (int i=0; i<this.links.length; i++) {
2 26 Feb 07 jari 102             this.links[i] = new IntArray();
2 26 Feb 07 jari 103             this.links[i].add(i);
2 26 Feb 07 jari 104             this.distances[i] = new FloatArray();
2 26 Feb 07 jari 105             this.distances[i].add(0f);
2 26 Feb 07 jari 106         }
2 26 Feb 07 jari 107         int bagRowCount = bag.getRowCount();
2 26 Feb 07 jari 108         int bagColCount = bag.getColumnCount();
2 26 Feb 07 jari 109         for (int i=0; i<bagRowCount; i++) {
2 26 Feb 07 jari 110             int[] pIntVect = bag.getIndVector(i);
2 26 Feb 07 jari 111             float[] pFloatVect = bag.getValVector(i);
2 26 Feb 07 jari 112             for (int j=0; j<bagColCount; j++) {
2 26 Feb 07 jari 113                 if (pIntVect[j]>=0 && pFloatVect[j]>0) {
2 26 Feb 07 jari 114                     this.links[i].add(pIntVect[j]);
2 26 Feb 07 jari 115                     this.distances[i].add(pFloatVect[j]);
2 26 Feb 07 jari 116                     this.links[pIntVect[j]].add(i);
2 26 Feb 07 jari 117                     this.distances[pIntVect[j]].add(pFloatVect[j]);
2 26 Feb 07 jari 118                 }
2 26 Feb 07 jari 119             }
2 26 Feb 07 jari 120         }
2 26 Feb 07 jari 121         // copy nodes to the cluster structure
2 26 Feb 07 jari 122         Cluster cluster = new Cluster();
2 26 Feb 07 jari 123         NodeList clusterNodeList = cluster.getNodeList();
2 26 Feb 07 jari 124         clusterNodeList.ensureCapacity(nGenes);
2 26 Feb 07 jari 125         for (int i=0; i<nGenes; i++) {
2 26 Feb 07 jari 126             NodeValueList values = new NodeValueList(1);
2 26 Feb 07 jari 127             values.addNodeValue(new NodeValue("weights", this.distances[i].toArray()));
2 26 Feb 07 jari 128             Node node = new Node(this.links[i].toArray());
2 26 Feb 07 jari 129             node.setValues(values);
2 26 Feb 07 jari 130             clusterNodeList.addNode(node);
2 26 Feb 07 jari 131         }
2 26 Feb 07 jari 132
2 26 Feb 07 jari 133         int[][] clusters = new int[this.links.length][];
2 26 Feb 07 jari 134         for (int i=0; i<clusters.length; i++)
2 26 Feb 07 jari 135             clusters[i] = this.links[i].toArray();
2 26 Feb 07 jari 136
2 26 Feb 07 jari 137         this.coords = doCircularLayout(clusters);
2 26 Feb 07 jari 138
2 26 Feb 07 jari 139         FDGLAlgoT fdgl = new FDGLAlgoT(this);
2 26 Feb 07 jari 140         fdgl.InitFromInterface();
2 26 Feb 07 jari 141
2 26 Feb 07 jari 142         event.setId(AlgorithmEvent.SET_UNITS);
2 26 Feb 07 jari 143         event.setIntValue(100);
2 26 Feb 07 jari 144         event.setDescription("Layouting...");
2 26 Feb 07 jari 145         fireValueChanged(event);
2 26 Feb 07 jari 146         event.setId(AlgorithmEvent.PROGRESS_VALUE);
2 26 Feb 07 jari 147
2 26 Feb 07 jari 148         while (!fdgl.shouldStop()) {
2 26 Feb 07 jari 149             if (this.stop) {
2 26 Feb 07 jari 150                 throw new AbortException();
2 26 Feb 07 jari 151             }
2 26 Feb 07 jari 152             fdgl.CalculateForceField();
2 26 Feb 07 jari 153             fdgl.MoveSystem();
2 26 Feb 07 jari 154             fdgl.UpdateSource();    //TODO: may be change interface for QuadTree to fdgl??
2 26 Feb 07 jari 155
2 26 Feb 07 jari 156             event.setIntValue((int)fdgl.getPercentage());
2 26 Feb 07 jari 157             event.setDescription("Layouting...");
2 26 Feb 07 jari 158             fireValueChanged(event);
2 26 Feb 07 jari 159         }
2 26 Feb 07 jari 160         float max = normalize(this.coords);
2 26 Feb 07 jari 161         float sigma = 0.02f; //FDGLAlgoT.c_RepulsiveRadius/max;
2 26 Feb 07 jari 162
2 26 Feb 07 jari 163         AlgorithmData result = new AlgorithmData();
2 26 Feb 07 jari 164         result.addCluster("links", cluster);
2 26 Feb 07 jari 165         result.addMatrix("locations", new FloatMatrix(this.coords));
2 26 Feb 07 jari 166         result.addParam("sigma", String.valueOf(sigma));
2 26 Feb 07 jari 167         return result;
2 26 Feb 07 jari 168     }
2 26 Feb 07 jari 169     /**
2 26 Feb 07 jari 170      * This method should interrupt the calculation.
2 26 Feb 07 jari 171      */
2 26 Feb 07 jari 172     public void abort() {
2 26 Feb 07 jari 173         this.stop = true;
2 26 Feb 07 jari 174     }
2 26 Feb 07 jari 175
2 26 Feb 07 jari 176     private float[][] doCircularLayout(int[][] clusters) {
2 26 Feb 07 jari 177         float[][] coords = new float[clusters.length][2];
2 26 Feb 07 jari 178         int[][] subnets = formRelevanceNetworks(clusters);
2 26 Feb 07 jari 179
2 26 Feb 07 jari 180         int x_size = (int)Math.ceil(Math.sqrt(subnets.length));
2 26 Feb 07 jari 181         int y_size = (int)Math.ceil((float)subnets.length/(float)x_size);
2 26 Feb 07 jari 182         int subnet;
2 26 Feb 07 jari 183         for (int y=0; y<y_size; y++) {
2 26 Feb 07 jari 184             for (int x=0; x<x_size; x++) {
2 26 Feb 07 jari 185                 subnet = y*x_size+x;
2 26 Feb 07 jari 186                 if (subnet >= subnets.length) {
2 26 Feb 07 jari 187                     break;
2 26 Feb 07 jari 188                 }
2 26 Feb 07 jari 189                 arrangeGraph(subnets[subnet], coords, x, y); // do layout algorithm
2 26 Feb 07 jari 190             }
2 26 Feb 07 jari 191         }
2 26 Feb 07 jari 192         return coords;
2 26 Feb 07 jari 193     }
2 26 Feb 07 jari 194
2 26 Feb 07 jari 195     private void arrangeGraph(int[] subnet, float[][] coords, int x, int y) {
2 26 Feb 07 jari 196         for (int i=0; i<subnet.length; i++) {
2 26 Feb 07 jari 197             coords[subnet[i]][0]=(float)(1000*Math.cos(2*Math.PI*i/subnet.length)+1500*(x+1)/*-1.5f*/);
2 26 Feb 07 jari 198             coords[subnet[i]][1]=(float)(1000*Math.sin(2*Math.PI*i/subnet.length)+1500*(y+1)/*-1.5f*/);
2 26 Feb 07 jari 199         }
2 26 Feb 07 jari 200     }
2 26 Feb 07 jari 201
2 26 Feb 07 jari 202     private float normalize(float[][] coords) {
2 26 Feb 07 jari 203         float max = 0;
2 26 Feb 07 jari 204         float minX = Float.MAX_VALUE;
2 26 Feb 07 jari 205         float minY = Float.MAX_VALUE;
2 26 Feb 07 jari 206         for (int i=0; i<coords.length; i++) {
2 26 Feb 07 jari 207             minX = Math.min(minX, coords[i][0]);
2 26 Feb 07 jari 208             minY = Math.min(minY, coords[i][1]);
2 26 Feb 07 jari 209         }
2 26 Feb 07 jari 210         for (int i=0; i<coords.length; i++) {
2 26 Feb 07 jari 211             coords[i][0] = coords[i][0] - minX;
2 26 Feb 07 jari 212             coords[i][1] = coords[i][1] - minY;
2 26 Feb 07 jari 213         }
2 26 Feb 07 jari 214         for (int i=0; i<coords.length; i++)
2 26 Feb 07 jari 215             max = Math.max(max, Math.max(coords[i][0], coords[i][1]));
2 26 Feb 07 jari 216
2 26 Feb 07 jari 217         for (int i=0; i<coords.length; i++) {
2 26 Feb 07 jari 218             coords[i][0] = coords[i][0]/max;
2 26 Feb 07 jari 219             coords[i][1] = coords[i][1]/max;
2 26 Feb 07 jari 220         }
2 26 Feb 07 jari 221         return max;
2 26 Feb 07 jari 222     }
2 26 Feb 07 jari 223
2 26 Feb 07 jari 224     /**
2 26 Feb 07 jari 225      * Normalize nodes coordinaties to be from 0 to 1.
2 26 Feb 07 jari 226      */
2 26 Feb 07 jari 227     private void normalize(float[][] coords, int[][] clusters) {
2 26 Feb 07 jari 228         float max = 0;
2 26 Feb 07 jari 229         float minX = Float.MAX_VALUE;
2 26 Feb 07 jari 230         float minY = Float.MAX_VALUE;
2 26 Feb 07 jari 231         for (int i=0; i<clusters.length; i++) {
2 26 Feb 07 jari 232             if (clusters[i].length > 1) {
2 26 Feb 07 jari 233                 for (int j=0; j<clusters[i].length; j++) {
2 26 Feb 07 jari 234                     minX = Math.min(minX, coords[clusters[i][j]][0]);
2 26 Feb 07 jari 235                     minY = Math.min(minY, coords[clusters[i][j]][1]);
2 26 Feb 07 jari 236                 }
2 26 Feb 07 jari 237             }
2 26 Feb 07 jari 238         }
2 26 Feb 07 jari 239         for (int i=0; i<coords.length; i++) {
2 26 Feb 07 jari 240             coords[i][0] = coords[i][0] - minX;
2 26 Feb 07 jari 241             coords[i][1] = coords[i][1] - minY;
2 26 Feb 07 jari 242         }
2 26 Feb 07 jari 243         for (int i=0; i<clusters.length; i++) {
2 26 Feb 07 jari 244             if (clusters[i].length > 1) {
2 26 Feb 07 jari 245                 for (int j=0; j<clusters[i].length; j++) {
2 26 Feb 07 jari 246                     max = Math.max(max, Math.max(coords[clusters[i][j]][0], coords[clusters[i][j]][1]));
2 26 Feb 07 jari 247                 }
2 26 Feb 07 jari 248             }
2 26 Feb 07 jari 249         }
2 26 Feb 07 jari 250         for (int i=0; i<coords.length; i++) {
2 26 Feb 07 jari 251             coords[i][0] = coords[i][0]/max;
2 26 Feb 07 jari 252             coords[i][1] = coords[i][1]/max;
2 26 Feb 07 jari 253         }
2 26 Feb 07 jari 254     }
2 26 Feb 07 jari 255
2 26 Feb 07 jari 256     /**
2 26 Feb 07 jari 257      * Returns nodes for every subnet in relnet.
2 26 Feb 07 jari 258      */
2 26 Feb 07 jari 259     public int[][] formRelevanceNetworks(int[][] clusters) {
2 26 Feb 07 jari 260         int size = clusters.length;
2 26 Feb 07 jari 261         boolean[] visited = new boolean[size];
2 26 Feb 07 jari 262         Arrays.fill(visited, false);
2 26 Feb 07 jari 263         ArrayList subnets = new ArrayList();
2 26 Feb 07 jari 264         for (int node=0; node<size; node++) {
2 26 Feb 07 jari 265             if (visited[node])
2 26 Feb 07 jari 266                 continue;
2 26 Feb 07 jari 267             subnets.add(fillSubnet(new IntArray(), node, visited, clusters));
2 26 Feb 07 jari 268         }
2 26 Feb 07 jari 269         // copy result into a new structure
2 26 Feb 07 jari 270         int subnets_size = subnets.size();
2 26 Feb 07 jari 271         int number_of_subnets = 0;
2 26 Feb 07 jari 272         for (int i=0; i<subnets_size; i++)
2 26 Feb 07 jari 273             if (((IntArray)subnets.get(i)).getSize() > 1)
2 26 Feb 07 jari 274                 number_of_subnets++;
2 26 Feb 07 jari 275
2 26 Feb 07 jari 276         int[][] result = new int[number_of_subnets][];
2 26 Feb 07 jari 277         int subnet_pos = 0;
2 26 Feb 07 jari 278         IntArray subnet;
2 26 Feb 07 jari 279         for (int i=0; i<subnets_size; i++) {
2 26 Feb 07 jari 280             subnet = (IntArray)subnets.get(i);
2 26 Feb 07 jari 281             if (subnet.getSize() > 1) {
2 26 Feb 07 jari 282                 result[subnet_pos] = subnet.toArray();
2 26 Feb 07 jari 283                 subnet_pos++;
2 26 Feb 07 jari 284             }
2 26 Feb 07 jari 285         }
2 26 Feb 07 jari 286         return result;
2 26 Feb 07 jari 287     }
2 26 Feb 07 jari 288
2 26 Feb 07 jari 289     private IntArray fillSubnet(IntArray subnet, int root, boolean[] visited, int[][] clusters) {
2 26 Feb 07 jari 290         subnet.add(root);
2 26 Feb 07 jari 291         visited[root] = true;
2 26 Feb 07 jari 292         int[] cluster = clusters[root];
2 26 Feb 07 jari 293         int node;
2 26 Feb 07 jari 294         for (int i=1; i<cluster.length; i++) {
2 26 Feb 07 jari 295             node = cluster[i];
2 26 Feb 07 jari 296             if (visited[node])
2 26 Feb 07 jari 297                 continue;
2 26 Feb 07 jari 298             fillSubnet(subnet, node, visited, clusters);
2 26 Feb 07 jari 299         }
2 26 Feb 07 jari 300         return subnet;
2 26 Feb 07 jari 301     }
2 26 Feb 07 jari 302
2 26 Feb 07 jari 303     public int[] GetAllObjectsIds() {       // returns the array of Object Identificators(ID)
2 26 Feb 07 jari 304         int number_of_genes = this.experiment.getRowDimension();
2 26 Feb 07 jari 305         int[] ids = new int[number_of_genes];
2 26 Feb 07 jari 306         for (int i=0; i<ids.length; i++)
2 26 Feb 07 jari 307             ids[i] = i;
2 26 Feb 07 jari 308         return ids;
2 26 Feb 07 jari 309     }
2 26 Feb 07 jari 310
2 26 Feb 07 jari 311     public void GetObjectGeom(int iObjID, Vector2f pt) {  // returns the metrix(x and y coords) for every object with iObjID identity
2 26 Feb 07 jari 312         pt.set(this.coords[iObjID][0], this.coords[iObjID][1]);
2 26 Feb 07 jari 313     }
2 26 Feb 07 jari 314
2 26 Feb 07 jari 315     public int GetAdjCountFor(int iObjId) {
2 26 Feb 07 jari 316         return links[iObjId].getSize()-1;
2 26 Feb 07 jari 317     }
2 26 Feb 07 jari 318
2 26 Feb 07 jari 319     public void GetAdjInfoFor(int iObjId/*in*/, IntArray rArrAdjIds/*out*/, FloatArray rArrAdjVals/*out*/) {
2 26 Feb 07 jari 320         int iSize=links[iObjId].getSize();
2 26 Feb 07 jari 321
2 26 Feb 07 jari 322         rArrAdjIds.clear();
2 26 Feb 07 jari 323         rArrAdjVals.clear();
2 26 Feb 07 jari 324         for (int i=1; i<iSize; i++) {   // 'int i=1;' to ignore first element
2 26 Feb 07 jari 325             rArrAdjIds.add(links[iObjId].get(i));
2 26 Feb 07 jari 326             rArrAdjVals.add(distances[iObjId].get(i));
2 26 Feb 07 jari 327         }
2 26 Feb 07 jari 328     }
2 26 Feb 07 jari 329
2 26 Feb 07 jari 330     // Uses to return data back to the 'storage'
2 26 Feb 07 jari 331     public void SetObjectGeom(Vector2f[] rRet) {
2 26 Feb 07 jari 332         for (int i=0; i<rRet.length; i++) {
2 26 Feb 07 jari 333             this.coords[i][0] = rRet[i].x;
2 26 Feb 07 jari 334             this.coords[i][1] = rRet[i].y;
2 26 Feb 07 jari 335         }
2 26 Feb 07 jari 336     }
2 26 Feb 07 jari 337 }

Generated on Thu Jul 20 09:25:25 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)