From 8fbc01654883e68f8843ad6632efaabfaf21692e Mon Sep 17 00:00:00 2001 From: James Procter Date: Thu, 23 Feb 2023 16:38:04 +0000 Subject: [PATCH] JAL-4134 - brutal hack to build a tree clustering columns of PAE Matrix --- src/jalview/analysis/AlignmentSorter.java | 9 +- src/jalview/analysis/AverageDistanceEngine.java | 180 +++++++++++ src/jalview/analysis/TreeBuilder.java | 293 +----------------- src/jalview/analysis/TreeEngine.java | 317 ++++++++++++++++++++ src/jalview/analysis/TreeModel.java | 37 +-- src/jalview/appletgui/TreeCanvas.java | 28 +- src/jalview/gui/TreeCanvas.java | 34 +-- src/jalview/io/NewickFile.java | 30 +- src/jalview/io/vamsas/Tree.java | 4 +- .../analysis/AverageDistanceEngineTest.java | 68 +++++ test/jalview/io/NewickFileTests.java | 4 +- 11 files changed, 641 insertions(+), 363 deletions(-) create mode 100644 src/jalview/analysis/AverageDistanceEngine.java create mode 100644 src/jalview/analysis/TreeEngine.java create mode 100644 test/jalview/analysis/AverageDistanceEngineTest.java diff --git a/src/jalview/analysis/AlignmentSorter.java b/src/jalview/analysis/AlignmentSorter.java index 81bddc2..0f3edfd 100755 --- a/src/jalview/analysis/AlignmentSorter.java +++ b/src/jalview/analysis/AlignmentSorter.java @@ -25,6 +25,7 @@ import jalview.analysis.scoremodels.SimilarityParams; import jalview.datamodel.AlignmentAnnotation; import jalview.datamodel.AlignmentI; import jalview.datamodel.AlignmentOrder; +import jalview.datamodel.BinaryNode; import jalview.datamodel.SequenceFeature; import jalview.datamodel.SequenceGroup; import jalview.datamodel.SequenceI; @@ -534,7 +535,7 @@ public class AlignmentSorter * * @return DOCUMENT ME! */ - private static List _sortByTree(SequenceNode node, + private static List _sortByTree(BinaryNode node, List tmp, List seqset) { if (node == null) @@ -542,12 +543,12 @@ public class AlignmentSorter return tmp; } - SequenceNode left = (SequenceNode) node.left(); - SequenceNode right = (SequenceNode) node.right(); + BinaryNode left = (BinaryNode) node.left(); + BinaryNode right = (BinaryNode) node.right(); if ((left == null) && (right == null)) { - if (!node.isPlaceholder() && (node.element() != null)) + if (!(node instanceof SequenceNode && ((SequenceNode)node).isPlaceholder()) && (node.element() != null)) { if (node.element() instanceof SequenceI) { diff --git a/src/jalview/analysis/AverageDistanceEngine.java b/src/jalview/analysis/AverageDistanceEngine.java new file mode 100644 index 0000000..a330170 --- /dev/null +++ b/src/jalview/analysis/AverageDistanceEngine.java @@ -0,0 +1,180 @@ +/* + * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) + * Copyright (C) $$Year-Rel$$ The Jalview Authors + * + * This file is part of Jalview. + * + * Jalview is free software: you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, either version 3 + * of the License, or (at your option) any later version. + * + * Jalview is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR + * PURPOSE. See the GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Jalview. If not, see . + * The Jalview Authors are detailed in the 'AUTHORS' file. + */ +package jalview.analysis; + +import java.util.BitSet; +import java.util.Vector; + +import jalview.datamodel.AlignmentAnnotation; +import jalview.datamodel.BinaryNode; +import jalview.datamodel.ContactListI; +import jalview.datamodel.ContactMatrixI; +import jalview.math.Matrix; +import jalview.viewmodel.AlignmentViewport; + +/** + * This class implements distance calculations used in constructing a Average + * Distance tree (also known as UPGMA) + */ +public class AverageDistanceEngine extends TreeEngine +{ + ContactMatrixI cm; + AlignmentViewport av; + AlignmentAnnotation aa; + /** + * compute cosine distance matrix for a given contact matrix and create a UPGMA tree + * @param cm + */ + public AverageDistanceEngine(AlignmentViewport av, AlignmentAnnotation aa, ContactMatrixI cm) + { + this.av =av; + this.aa = aa; + this.cm=cm; + node = new Vector(); + clusters = new Vector(); + distances = new Matrix(new double[cm.getWidth()][cm.getWidth()]); + noseqs=cm.getWidth(); + done = new BitSet(); + for (int i=0;i clusters; - protected SequenceI[] sequences; public AlignmentView seqData; - protected BitSet done; - - protected int noseqs; - - int noClus; - - protected MatrixI distances; - - protected int mini; - - protected int minj; - - protected double ri; - - protected double rj; - - BinaryNode maxdist; - - BinaryNode top; - - double maxDistValue; - - double maxheight; - - int ycount; - - Vector node; - private AlignmentView seqStrings; /** @@ -115,116 +84,6 @@ public abstract class TreeBuilder } /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - * - * @return DOCUMENT ME! - */ - double findHeight(BinaryNode nd) - { - if (nd == null) - { - return maxheight; - } - - if ((nd.left() == null) && (nd.right() == null)) - { - nd.height = ((BinaryNode) nd.parent()).height + nd.dist; - - if (nd.height > maxheight) - { - return nd.height; - } - else - { - return maxheight; - } - } - else - { - if (nd.parent() != null) - { - nd.height = ((BinaryNode) nd.parent()).height + nd.dist; - } - else - { - maxheight = 0; - nd.height = (float) 0.0; - } - - maxheight = findHeight((BinaryNode) (nd.left())); - maxheight = findHeight((BinaryNode) (nd.right())); - } - - return maxheight; - } - - /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - */ - void reCount(BinaryNode nd) - { - ycount = 0; - // _lycount = 0; - // _lylimit = this.node.size(); - _reCount(nd); - } - - /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - */ - void _reCount(BinaryNode nd) - { - // if (_lycount<_lylimit) - // { - // System.err.println("Warning: depth of _recount greater than number of - // nodes."); - // } - if (nd == null) - { - return; - } - // _lycount++; - - if ((nd.left() != null) && (nd.right() != null)) - { - - _reCount(nd.left()); - _reCount((BinaryNode) nd.right()); - - BinaryNode l = nd.left(); - BinaryNode r = nd.right(); - - nd.count = l.count + r.count; - nd.ycount = (l.ycount + r.ycount) / 2; - } - else - { - nd.count = 1; - nd.ycount = ycount++; - } - // _lycount--; - } - - /** - * DOCUMENT ME! - * - * @return DOCUMENT ME! - */ - public BinaryNode getTopNode() - { - return top; - } - - /** * * @return true if tree has real distances */ @@ -248,40 +107,6 @@ public abstract class TreeBuilder } /** - * Form clusters by grouping sub-clusters, starting from one sequence per - * cluster, and finishing when only two clusters remain - */ - void cluster() - { - while (noClus > 2) - { - findMinDistance(); - - joinClusters(mini, minj); - - noClus--; - } - - int rightChild = done.nextClearBit(0); - int leftChild = done.nextClearBit(rightChild + 1); - - joinClusters(leftChild, rightChild); - top = (node.elementAt(leftChild)); - - reCount(top); - findHeight(top); - findMaxDist(top); - } - - /** - * Returns the minimum distance between two clusters, and also sets the - * indices of the clusters in fields mini and minj - * - * @return - */ - protected abstract double findMinDistance(); - - /** * Calculates the tree using the given score model and parameters, and the * configured tree type *

@@ -305,67 +130,9 @@ public abstract class TreeBuilder cluster(); } - /** - * Finds the node, at or below the given node, with the maximum distance, and - * saves the node and the distance value - * - * @param nd - */ - void findMaxDist(BinaryNode nd) - { - if (nd == null) - { - return; - } - - if ((nd.left() == null) && (nd.right() == null)) - { - double dist = nd.dist; - - if (dist > maxDistValue) - { - maxdist = nd; - maxDistValue = dist; - } - } - else - { - findMaxDist((BinaryNode) nd.left()); - findMaxDist((BinaryNode) nd.right()); - } - } - - /** - * Calculates and returns r, whatever that is - * - * @param i - * @param j - * - * @return - */ - protected double findr(int i, int j) - { - double tmp = 1; - - for (int k = 0; k < noseqs; k++) - { - if ((k != i) && (k != j) && (!done.get(k))) - { - tmp = tmp + distances.getValue(i, k); - } - } - - if (noClus > 2) - { - tmp = tmp / (noClus - 2); - } - - return tmp; - } - protected void init(AlignmentView seqView, int start, int end) { - this.node = new Vector(); + this.node = new Vector(); if (seqView != null) { this.seqData = seqView; @@ -399,62 +166,6 @@ public abstract class TreeBuilder } /** - * Merges cluster(j) to cluster(i) and recalculates cluster and node distances - * - * @param i - * @param j - */ - void joinClusters(final int i, final int j) - { - double dist = distances.getValue(i, j); - - ri = findr(i, j); - rj = findr(j, i); - - findClusterDistance(i, j); - - SequenceNode sn = new SequenceNode(); - - sn.setLeft((node.elementAt(i))); - sn.setRight((node.elementAt(j))); - - BinaryNode tmpi = (node.elementAt(i)); - BinaryNode tmpj = (node.elementAt(j)); - - findNewDistances(tmpi, tmpj, dist); - - tmpi.setParent(sn); - tmpj.setParent(sn); - - node.setElementAt(sn, i); - - /* - * move the members of cluster(j) to cluster(i) - * and mark cluster j as out of the game - */ - clusters.get(i).or(clusters.get(j)); - clusters.get(j).clear(); - done.set(j); - } - - /* - * Computes and stores new distances for nodei and nodej, given the previous - * distance between them - */ - protected abstract void findNewDistances(BinaryNode nodei, - BinaryNode nodej, double previousDistance); - - /** - * Calculates and saves the distance between the combination of cluster(i) and - * cluster(j) and all other clusters. The form of the calculation depends on - * the tree clustering method being used. - * - * @param i - * @param j - */ - protected abstract void findClusterDistance(int i, int j); - - /** * Start by making a cluster for each individual sequence */ void makeLeaves() diff --git a/src/jalview/analysis/TreeEngine.java b/src/jalview/analysis/TreeEngine.java new file mode 100644 index 0000000..daf7836 --- /dev/null +++ b/src/jalview/analysis/TreeEngine.java @@ -0,0 +1,317 @@ +/* + * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) + * Copyright (C) $$Year-Rel$$ The Jalview Authors + * + * This file is part of Jalview. + * + * Jalview is free software: you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, either version 3 + * of the License, or (at your option) any later version. + * + * Jalview is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR + * PURPOSE. See the GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Jalview. If not, see . + * The Jalview Authors are detailed in the 'AUTHORS' file. + */ +package jalview.analysis; + +import java.util.BitSet; +import java.util.Vector; + +import jalview.datamodel.BinaryNode; +import jalview.datamodel.SequenceNode; +import jalview.math.MatrixI; + +public abstract class TreeEngine +{ + + protected Vector clusters; + + protected BitSet done; + + protected int noseqs; + + protected int noClus; + + protected MatrixI distances; + + protected double ri; + + protected double rj; + + protected Vector node; + + BinaryNode maxdist; + + double maxDistValue; + + protected int mini; + + protected int minj; + + protected BinaryNode top; + + protected int ycount; + + double maxheight; + + /** + * Calculates and returns r, whatever that is + * + * @param i + * @param j + * + * @return + */ + protected double findr(int i, int j) + { + double tmp = 1; + + for (int k = 0; k < noseqs; k++) + { + if ((k != i) && (k != j) && (!done.get(k))) + { + tmp = tmp + distances.getValue(i, k); + } + } + + if (noClus > 2) + { + tmp = tmp / (noClus - 2); + } + + return tmp; + } + + /** + * Merges cluster(j) to cluster(i) and recalculates cluster and node distances + * + * @param i + * @param j + */ + protected void joinClusters(final int i, final int j) + { + double dist = distances.getValue(i, j); + + ri = findr(i, j); + rj = findr(j, i); + + findClusterDistance(i, j); + + BinaryNode sn = new BinaryNode(); + + sn.setLeft((node.elementAt(i))); + sn.setRight((node.elementAt(j))); + + BinaryNode tmpi = (node.elementAt(i)); + BinaryNode tmpj = (node.elementAt(j)); + + findNewDistances(tmpi, tmpj, dist); + + tmpi.setParent(sn); + tmpj.setParent(sn); + + node.setElementAt(sn, i); + + /* + * move the members of cluster(j) to cluster(i) + * and mark cluster j as out of the game + */ + clusters.get(i).or(clusters.get(j)); + clusters.get(j).clear(); + done.set(j); + } + + protected abstract void findNewDistances(BinaryNode nodei, + BinaryNode nodej, double previousDistance); + + /** + * Calculates and saves the distance between the combination of cluster(i) and + * cluster(j) and all other clusters. The form of the calculation depends on + * the tree clustering method being used. + * + * @param i + * @param j + */ + protected abstract void findClusterDistance(int i, int j); + + /** + * Finds the node, at or below the given node, with the maximum distance, and + * saves the node and the distance value + * + * @param nd + */ + protected void findMaxDist(BinaryNode nd) + { + if (nd == null) + { + return; + } + + if ((nd.left() == null) && (nd.right() == null)) + { + double dist = nd.dist; + + if (dist > maxDistValue) + { + maxdist = nd; + maxDistValue = dist; + } + } + else + { + findMaxDist((BinaryNode) nd.left()); + findMaxDist((BinaryNode) nd.right()); + } + } + + /** + * Form clusters by grouping sub-clusters, starting from one sequence per + * cluster, and finishing when only two clusters remain + */ + protected void cluster() + { + while (noClus > 2) + { + findMinDistance(); + + joinClusters(mini, minj); + + noClus--; + } + + int rightChild = done.nextClearBit(0); + int leftChild = done.nextClearBit(rightChild + 1); + + joinClusters(leftChild, rightChild); + top = (node.elementAt(leftChild)); + + reCount(top); + findHeight(top); + findMaxDist(top); + } + + /** + * Returns the minimum distance between two clusters, and also sets the + * indices of the clusters in fields mini and minj + * + * @return + */ + protected abstract double findMinDistance(); + + /** + * DOCUMENT ME! + * + * @param nd + * DOCUMENT ME! + */ + protected void _reCount(BinaryNode nd) + { + // if (_lycount<_lylimit) + // { + // System.err.println("Warning: depth of _recount greater than number of + // nodes."); + // } + if (nd == null) + { + return; + } + // _lycount++; + + if ((nd.left() != null) && (nd.right() != null)) + { + + _reCount(nd.left()); + _reCount((BinaryNode) nd.right()); + + BinaryNode l = nd.left(); + BinaryNode r = nd.right(); + + nd.count = l.count + r.count; + nd.ycount = (l.ycount + r.ycount) / 2; + } + else + { + nd.count = 1; + nd.ycount = ycount++; + } + // _lycount--; + } + + /** + * DOCUMENT ME! + * + * @param nd + * DOCUMENT ME! + * + * @return DOCUMENT ME! + */ + double findHeight(BinaryNode nd) + { + if (nd == null) + { + return maxheight; + } + + if ((nd.left() == null) && (nd.right() == null)) + { + nd.height = ((BinaryNode) nd.parent()).height + nd.dist; + + if (nd.height > maxheight) + { + return nd.height; + } + else + { + return maxheight; + } + } + else + { + if (nd.parent() != null) + { + nd.height = ((BinaryNode) nd.parent()).height + nd.dist; + } + else + { + maxheight = 0; + nd.height = (float) 0.0; + } + + maxheight = findHeight((BinaryNode) (nd.left())); + maxheight = findHeight((BinaryNode) (nd.right())); + } + + return maxheight; + } + + /** + * DOCUMENT ME! + * + * @param nd + * DOCUMENT ME! + */ + void reCount(BinaryNode nd) + { + ycount = 0; + // _lycount = 0; + // _lylimit = this.node.size(); + _reCount(nd); + } + + /** + * DOCUMENT ME! + * + * @return DOCUMENT ME! + */ + public BinaryNode getTopNode() + { + return top; + } + +} diff --git a/src/jalview/analysis/TreeModel.java b/src/jalview/analysis/TreeModel.java index 703702a..1725adc 100644 --- a/src/jalview/analysis/TreeModel.java +++ b/src/jalview/analysis/TreeModel.java @@ -51,7 +51,7 @@ public class TreeModel int noseqs; - SequenceNode top; + BinaryNode top; double maxDistValue; @@ -59,7 +59,7 @@ public class TreeModel int ycount; - Vector node; + Vector node; boolean hasDistances = true; // normal case for jalview trees @@ -81,7 +81,7 @@ public class TreeModel public TreeModel(SequenceI[] seqs, AlignmentView odata, NewickFile treefile) { - this(seqs, treefile.getTree(), treefile.HasDistances(), + this(seqs, (SequenceNode) treefile.getTree(), treefile.HasDistances(), treefile.HasBootstrap(), treefile.HasRootDistance()); seqData = odata; @@ -129,7 +129,7 @@ public class TreeModel { SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs); - Vector leaves = findLeaves(top); + Vector leaves = findLeaves(top); int i = 0; int namesleft = seqs.length; @@ -141,7 +141,8 @@ public class TreeModel // int countOne2Many = 0; while (i < leaves.size()) { - j = leaves.elementAt(i++); + // TODO - decide if we get rid of the polymorphism here ? + j = (SequenceNode)leaves.elementAt(i++); realnam = j.getName(); nam = null; @@ -206,7 +207,7 @@ public class TreeModel */ public void updatePlaceHolders(List list) { - Vector leaves = findLeaves(top); + Vector leaves = findLeaves(top); int sz = leaves.size(); SequenceIdMatcher seqmatcher = null; @@ -214,7 +215,7 @@ public class TreeModel while (i < sz) { - SequenceNode leaf = leaves.elementAt(i++); + SequenceNode leaf = (SequenceNode) leaves.elementAt(i++); if (list.contains(leaf.element())) { @@ -289,15 +290,15 @@ public class TreeModel /** * Search for leaf nodes below (or at) the given node * - * @param nd + * @param top2 * root node to search from * * @return */ - public Vector findLeaves(SequenceNode nd) + public Vector findLeaves(BinaryNode top2) { - Vector leaves = new Vector(); - findLeaves(nd, leaves); + Vector leaves = new Vector(); + findLeaves(top2, leaves); return leaves; } @@ -311,8 +312,8 @@ public class TreeModel * * @return Vector of leaf nodes on binary tree */ - Vector findLeaves(SequenceNode nd, - Vector leaves) + Vector findLeaves(BinaryNode nd, + Vector leaves) { if (nd == null) { @@ -388,14 +389,14 @@ public class TreeModel * @param threshold * @see #getGroups() */ - public List groupNodes(float threshold) + public List groupNodes(float threshold) { - List groups = new ArrayList(); + List groups = new ArrayList(); _groupNodes(groups, getTopNode(), threshold); return groups; } - protected void _groupNodes(List groups, SequenceNode nd, + protected void _groupNodes(List groups, BinaryNode nd, float threshold) { if (nd == null) @@ -630,7 +631,7 @@ public class TreeModel * * @return DOCUMENT ME! */ - public SequenceNode getTopNode() + public BinaryNode getTopNode() { return top; } @@ -665,7 +666,7 @@ public class TreeModel */ public void applyToNodes(NodeTransformI nodeTransformI) { - for (Enumeration nodes = node.elements(); nodes + for (Enumeration nodes = node.elements(); nodes .hasMoreElements(); nodeTransformI .transform(nodes.nextElement())) { diff --git a/src/jalview/appletgui/TreeCanvas.java b/src/jalview/appletgui/TreeCanvas.java index 1355916..8c3e39a 100755 --- a/src/jalview/appletgui/TreeCanvas.java +++ b/src/jalview/appletgui/TreeCanvas.java @@ -87,7 +87,7 @@ public class TreeCanvas extends Panel Hashtable nodeHash = new Hashtable(); - SequenceNode highlightNode; + BinaryNode highlightNode; AlignmentPanel ap; @@ -123,15 +123,15 @@ public class TreeCanvas extends Panel tree2.findHeight(tree2.getTopNode()); // Now have to calculate longest name based on the leaves - Vector leaves = tree2.findLeaves(tree2.getTopNode()); + Vector leaves = tree2.findLeaves(tree2.getTopNode()); boolean has_placeholders = false; longestName = ""; for (int i = 0; i < leaves.size(); i++) { - SequenceNode lf = leaves.elementAt(i); + BinaryNode lf = leaves.elementAt(i); - if (lf.isPlaceholder()) + if (lf instanceof SequenceNode && ((SequenceNode)lf).isPlaceholder()) { has_placeholders = true; } @@ -147,7 +147,7 @@ public class TreeCanvas extends Panel setMarkPlaceholders(has_placeholders); } - public void drawNode(Graphics g, SequenceNode node, float chunk, + public void drawNode(Graphics g, BinaryNode node, float chunk, double scale, int width, int offx, int offy) { if (node == null) @@ -211,7 +211,7 @@ public class TreeCanvas extends Panel g.drawString(nodeLabel, xstart + 2, ypos - 2); } - String name = (markPlaceholders && node.isPlaceholder()) + String name = (markPlaceholders && node instanceof SequenceNode && ((SequenceNode) node).isPlaceholder()) ? (PLACEHOLDER + node.getName()) : node.getName(); FontMetrics fm = g.getFontMetrics(font); @@ -238,9 +238,9 @@ public class TreeCanvas extends Panel } else { - drawNode(g, (SequenceNode) node.left(), chunk, scale, width, offx, + drawNode(g, (BinaryNode) node.left(), chunk, scale, width, offx, offy); - drawNode(g, (SequenceNode) node.right(), chunk, scale, width, offx, + drawNode(g, (BinaryNode) node.right(), chunk, scale, width, offx, offy); double height = node.height; @@ -528,7 +528,7 @@ public class TreeCanvas extends Panel } else { - Vector leaves = tree.findLeaves(highlightNode); + Vector leaves = tree.findLeaves(highlightNode); for (int i = 0; i < leaves.size(); i++) { @@ -555,9 +555,9 @@ public class TreeCanvas extends Panel Object ob = findElement(evt.getX(), evt.getY()); - if (ob instanceof SequenceNode) + if (ob instanceof BinaryNode) { - highlightNode = (SequenceNode) ob; + highlightNode = (BinaryNode) ob; repaint(); } else @@ -597,7 +597,7 @@ public class TreeCanvas extends Panel threshold = (float) (x - offx) / (float) (getSize().width - labelLength - 2 * offx); - List groups = tree.groupNodes(threshold); + List groups = tree.groupNodes(threshold); setColor(tree.getTopNode(), Color.black); av.setSelectionGroup(null); @@ -621,7 +621,7 @@ public class TreeCanvas extends Panel } - void colourGroups(List groups) + void colourGroups(List groups) { for (int i = 0; i < groups.size(); i++) { @@ -630,7 +630,7 @@ public class TreeCanvas extends Panel (int) (Math.random() * 255), (int) (Math.random() * 255)); setColor(groups.get(i), col.brighter()); - Vector l = tree.findLeaves(groups.get(i)); + Vector l = tree.findLeaves(groups.get(i)); Vector sequences = new Vector<>(); for (int j = 0; j < l.size(); j++) diff --git a/src/jalview/gui/TreeCanvas.java b/src/jalview/gui/TreeCanvas.java index a5f1ab9..a1bcebd 100755 --- a/src/jalview/gui/TreeCanvas.java +++ b/src/jalview/gui/TreeCanvas.java @@ -107,9 +107,9 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, Map nameHash = new Hashtable<>(); - Map nodeHash = new Hashtable<>(); + Map nodeHash = new Hashtable<>(); - SequenceNode highlightNode; + BinaryNode highlightNode; boolean applyToAllViews = false; @@ -174,15 +174,15 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, tree.findHeight(tree.getTopNode()); // Now have to calculate longest name based on the leaves - Vector leaves = tree.findLeaves(tree.getTopNode()); + Vector leaves = tree.findLeaves(tree.getTopNode()); boolean has_placeholders = false; longestName = ""; for (int i = 0; i < leaves.size(); i++) { - SequenceNode lf = leaves.elementAt(i); + BinaryNode lf = leaves.elementAt(i); - if (lf.isPlaceholder()) + if (lf instanceof SequenceNode && ((SequenceNode)lf).isPlaceholder()) { has_placeholders = true; } @@ -216,7 +216,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, * @param offy * DOCUMENT ME! */ - public void drawNode(Graphics g, SequenceNode node, float chunk, + public void drawNode(Graphics g, BinaryNode node, float chunk, double wscale, int width, int offx, int offy) { if (node == null) @@ -278,7 +278,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, g.drawString(nodeLabel, xstart + 2, ypos - 2); } - String name = (markPlaceholders && node.isPlaceholder()) + String name = (markPlaceholders && ((node instanceof SequenceNode && ((SequenceNode)node).isPlaceholder()))) ? (PLACEHOLDER + node.getName()) : node.getName(); @@ -307,9 +307,9 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, } else { - drawNode(g, (SequenceNode) node.left(), chunk, wscale, width, offx, + drawNode(g, (BinaryNode) node.left(), chunk, wscale, width, offx, offy); - drawNode(g, (SequenceNode) node.right(), chunk, wscale, width, offx, + drawNode(g, (BinaryNode) node.right(), chunk, wscale, width, offx, offy); double height = node.height; @@ -391,7 +391,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, } } - for (Entry entry : nodeHash.entrySet()) + for (Entry entry : nodeHash.entrySet()) { Rectangle rect = entry.getValue(); @@ -805,7 +805,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, } else { - Vector leaves = tree.findLeaves(highlightNode); + Vector leaves = tree.findLeaves(highlightNode); for (int i = 0; i < leaves.size(); i++) { @@ -848,9 +848,9 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, Object ob = findElement(evt.getX(), evt.getY()); - if (ob instanceof SequenceNode) + if (ob instanceof BinaryNode) { - highlightNode = (SequenceNode) ob; + highlightNode = (BinaryNode) ob; this.setToolTipText( "" + MessageManager.getString("label.highlightnode")); repaint(); @@ -923,7 +923,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, av.sendSelection(); return; } - else if (!(ob instanceof SequenceNode)) + else if (!(ob instanceof BinaryNode)) { // Find threshold if (tree.getMaxHeight() != 0) @@ -931,7 +931,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, threshold = (float) (x - offx) / (float) (getWidth() - labelLength - (2 * offx)); - List groups = tree.groupNodes(threshold); + List groups = tree.groupNodes(threshold); setColor(tree.getTopNode(), Color.black); AlignmentPanel[] aps = getAssociatedPanels(); @@ -971,7 +971,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, } - void colourGroups(List groups) + void colourGroups(List groups) { AlignmentPanel[] aps = getAssociatedPanels(); for (int i = 0; i < groups.size(); i++) @@ -980,7 +980,7 @@ public class TreeCanvas extends JPanel implements MouseListener, Runnable, (int) (Math.random() * 255), (int) (Math.random() * 255)); setColor(groups.get(i), col.brighter()); - Vector l = tree.findLeaves(groups.get(i)); + Vector l = tree.findLeaves(groups.get(i)); Vector sequences = new Vector<>(); diff --git a/src/jalview/io/NewickFile.java b/src/jalview/io/NewickFile.java index 879b7d4..269ffb3 100755 --- a/src/jalview/io/NewickFile.java +++ b/src/jalview/io/NewickFile.java @@ -79,7 +79,7 @@ import com.stevesoft.pat.Regex; */ public class NewickFile extends FileParse { - SequenceNode root; + BinaryNode root; private boolean HasBootstrap = false; @@ -146,7 +146,7 @@ public class NewickFile extends FileParse * @param newtree * DOCUMENT ME! */ - public NewickFile(SequenceNode newtree) + public NewickFile(BinaryNode newtree) { root = newtree; } @@ -175,7 +175,7 @@ public class NewickFile extends FileParse * @param distances * DOCUMENT ME! */ - public NewickFile(SequenceNode newtree, boolean bootstrap, + public NewickFile(BinaryNode newtree, boolean bootstrap, boolean distances) { root = newtree; @@ -195,7 +195,7 @@ public class NewickFile extends FileParse * @param rootdistance * DOCUMENT ME! */ - public NewickFile(SequenceNode newtree, boolean bootstrap, + public NewickFile(BinaryNode newtree, boolean bootstrap, boolean distances, boolean rootdistance) { root = newtree; @@ -679,7 +679,7 @@ public class NewickFile extends FileParse * * @return DOCUMENT ME! */ - public SequenceNode getTree() + public BinaryNode getTree() { return root; } @@ -865,7 +865,7 @@ public class NewickFile extends FileParse } // Non recursive call deals with root node properties - public void print(StringBuffer tf, SequenceNode root) + public void print(StringBuffer tf, BinaryNode root) { if (root != null) { @@ -877,20 +877,20 @@ public class NewickFile extends FileParse { if (root.isDummy()) { - _print(tf, (SequenceNode) root.right()); - _print(tf, (SequenceNode) root.left()); + _print(tf, root.right()); + _print(tf, root.left()); } else { tf.append("("); - _print(tf, (SequenceNode) root.right()); + _print(tf, root.right()); if (root.left() != null) { tf.append(","); } - _print(tf, (SequenceNode) root.left()); + _print(tf, root.left()); tf.append(")" + printRootField(root)); } } @@ -898,7 +898,7 @@ public class NewickFile extends FileParse } // Recursive call for non-root nodes - public void _print(StringBuffer tf, SequenceNode c) + public void _print(StringBuffer tf, BinaryNode c) { if (c != null) { @@ -910,24 +910,24 @@ public class NewickFile extends FileParse { if (c.isDummy()) { - _print(tf, (SequenceNode) c.left()); + _print(tf, c.left()); if (c.left() != null) { tf.append(","); } - _print(tf, (SequenceNode) c.right()); + _print(tf, c.right()); } else { tf.append("("); - _print(tf, (SequenceNode) c.right()); + _print(tf, c.right()); if (c.left() != null) { tf.append(","); } - _print(tf, (SequenceNode) c.left()); + _print(tf, c.left()); tf.append(")" + printNodeField(c)); } } diff --git a/src/jalview/io/vamsas/Tree.java b/src/jalview/io/vamsas/Tree.java index 260894d..c0d1774 100644 --- a/src/jalview/io/vamsas/Tree.java +++ b/src/jalview/io/vamsas/Tree.java @@ -322,7 +322,7 @@ public class Tree extends DatastoreItem Console.warn("Not updating SequenceTreeMap for " + tree.getVorbaId()); return; } - Vector leaves = tp.getTree() + Vector leaves = tp.getTree() .findLeaves(tp.getTree().getTopNode()); Treenode[] tn = tree.getTreenode(); // todo: select nodes for this // particular tree @@ -381,7 +381,7 @@ public class Tree extends DatastoreItem */ public Treenode[] makeTreeNodes(TreeModel treeModel, Newick newick) { - Vector leaves = treeModel + Vector leaves = treeModel .findLeaves(treeModel.getTopNode()); Vector tnv = new Vector(); Enumeration l = leaves.elements(); diff --git a/test/jalview/analysis/AverageDistanceEngineTest.java b/test/jalview/analysis/AverageDistanceEngineTest.java new file mode 100644 index 0000000..3697efd --- /dev/null +++ b/test/jalview/analysis/AverageDistanceEngineTest.java @@ -0,0 +1,68 @@ +package jalview.analysis; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.util.List; +import java.util.Map; + +import org.junit.Assert; +import org.testng.annotations.BeforeClass; +import org.testng.annotations.BeforeMethod; +import org.testng.annotations.Test; + +import jalview.bin.Cache; +import jalview.bin.Console; +import jalview.datamodel.AlignmentAnnotation; +import jalview.datamodel.AlignmentI; +import jalview.datamodel.ContactMatrixI; +import jalview.datamodel.SequenceI; +import jalview.gui.AlignFrame; +import jalview.gui.JvOptionPane; +import jalview.io.DataSourceType; +import jalview.io.FastaFile; +import jalview.io.FileLoader; +import jalview.io.FormatAdapter; +import jalview.util.Platform; +import jalview.ws.datamodel.alphafold.PAEContactMatrix; + +public class AverageDistanceEngineTest +{ + + @BeforeClass(alwaysRun = true) + public void setUpJvOptionPane() + { + JvOptionPane.setInteractiveMode(false); + JvOptionPane.setMockResponse(JvOptionPane.CANCEL_OPTION); + } + + @BeforeMethod(alwaysRun = true) + public void loadProperties() + { + Cache.loadProperties("test/jalview/bin/TestProps.jvprops"); + } + @Test + public void testUPGMAEngine() throws Exception + { + AlignFrame af = new FileLoader(false).LoadFileWaitTillLoaded("examples/test_fab41.result/sample.a3m",DataSourceType.FILE); + AlignmentI seqs = af.getViewport().getAlignment(); + SequenceI target = seqs.getSequenceAt(0); + File testPAE = new File("examples/test_fab41.result/test_fab41_predicted_aligned_error_v1.json"); + List pae_obj = (List) Platform.parseJSON(new FileInputStream(testPAE)); + if (pae_obj == null) + { + Assert.fail("JSON PAE file did not parse properly."); + } + ContactMatrixI matrix = new PAEContactMatrix(target, + (Map) pae_obj.get(0)); + AlignmentAnnotation aa = target.addContactList(matrix); + long start = System.currentTimeMillis(); + AverageDistanceEngine clusterer = new AverageDistanceEngine(af.getViewport(), null, matrix); + System.out.println("built a tree in "+(System.currentTimeMillis()-start)*0.001+" seconds."); + StringBuffer sb = new StringBuffer(); + System.out.println("Newick string\n"+ new jalview.io.NewickFile(clusterer.getTopNode(),true,true).print()); + + } + +} diff --git a/test/jalview/io/NewickFileTests.java b/test/jalview/io/NewickFileTests.java index 02c5ccd..466f218 100644 --- a/test/jalview/io/NewickFileTests.java +++ b/test/jalview/io/NewickFileTests.java @@ -106,7 +106,7 @@ public class NewickFileTests AssertJUnit.assertTrue( stage + "Invalid Tree '" + nf.getWarningMessage() + "'", nf.isValid()); - SequenceNode tree = nf.getTree(); + BinaryNode tree = nf.getTree(); AssertJUnit.assertTrue(stage + "Null Tree", tree != null); stage = "Creating newick file from testTree " + treename; String gentree = new NewickFile(tree).print(nf.HasBootstrap(), @@ -124,7 +124,7 @@ public class NewickFileTests AssertJUnit.assertTrue(stage + "Null Tree", tree_regen != null); stage = "Compare original and generated tree" + treename; - Vector oseqs, nseqs; + Vector oseqs, nseqs; oseqs = new TreeModel(new SequenceI[0], null, nf) .findLeaves(nf.getTree()); AssertJUnit.assertTrue(stage + "No nodes in original tree.", -- 1.7.10.2