/*
* 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.ArrayList;
import java.util.BitSet;
import java.util.List;
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 groupNodes(float threshold)
{
List groups = new ArrayList();
_groupNodes(groups, getTopNode(), threshold);
return groups;
}
protected void _groupNodes(List groups, BinaryNode nd,
float threshold)
{
if (nd == null)
{
return;
}
if ((nd.height / maxheight) > threshold)
{
groups.add(nd);
}
else
{
_groupNodes(groups, nd.left(), threshold);
_groupNodes(groups, nd.right(), threshold);
}
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public 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;
}
/**
* Search for leaf nodes below (or at) the given node
*
* @param top2
* root node to search from
*
* @return
*/
public Vector findLeaves(BinaryNode top2)
{
Vector leaves = new Vector();
findLeaves(top2, leaves);
return leaves;
}
/**
* Search for leaf nodes.
*
* @param nd
* root node to search from
* @param leaves
* Vector of leaves to add leaf node objects too.
*
* @return Vector of leaf nodes on binary tree
*/
Vector findLeaves(BinaryNode nd,
Vector leaves)
{
if (nd == null)
{
return leaves;
}
if ((nd.left() == null) && (nd.right() == null)) // Interior node
// detection
{
leaves.addElement(nd);
return leaves;
}
else
{
/*
* TODO: Identify internal nodes... if (node.isSequenceLabel()) {
* leaves.addElement(node); }
*/
findLeaves( nd.left(), leaves);
findLeaves( nd.right(), leaves);
}
return leaves;
}
}