();
if (seqView != null)
{
this.seqData = seqView;
}
else
{
SeqCigar[] seqs = new SeqCigar[sequences.length];
for (int i = 0; i < sequences.length; i++)
{
seqs[i] = new SeqCigar(sequences[i], start, end);
}
CigarArray sdata = new CigarArray(seqs);
sdata.addOperation(CigarArray.M, end - start + 1);
this.seqData = new AlignmentView(sdata, start);
}
/*
* count the non-null sequences
*/
noseqs = 0;
done = new int[sequences.length];
for (SequenceI seq : sequences)
{
if (seq != null)
{
noseqs++;
}
}
}
/**
* Calculates the tree using the given score model and parameters, and the
* configured tree type
*
* If the score model computes pairwise distance scores, then these are used
* directly to derive the tree
*
* If the score model computes similarity scores, then the range of the scores
* is reversed to give a distance measure, and this is used to derive the tree
*
* @param sm
* @param scoreOptions
*/
protected void computeTree(ScoreModelI sm, SimilarityParamsI scoreOptions)
{
if (sm instanceof DistanceScoreModelI)
{
distances = ((DistanceScoreModelI) sm).findDistances(seqData,
scoreOptions);
}
else if (sm instanceof SimilarityScoreModelI)
{
/*
* compute similarity and invert it to give a distance measure
*/
MatrixI result = ((SimilarityScoreModelI) sm).findSimilarities(
seqData, SimilarityParams.Jalview);
result.reverseRange(true);
distances = result;
}
makeLeaves();
noClus = cluster.size();
cluster();
}
/**
* Generate a string representation of the Tree
*
* @return Newick File with all tree data available
*/
@Override
public String toString()
{
jalview.io.NewickFile fout = new jalview.io.NewickFile(getTopNode());
return fout.print(hasBootstrap(), hasDistances(),
hasRootDistance()); // output all data available for tree
}
/**
*
* used when the alignment associated to a tree has changed.
*
* @param list
* Sequence set to be associated with tree nodes
*/
public void updatePlaceHolders(List list)
{
Vector leaves = findLeaves(top);
int sz = leaves.size();
SequenceIdMatcher seqmatcher = null;
int i = 0;
while (i < sz)
{
SequenceNode leaf = leaves.elementAt(i++);
if (list.contains(leaf.element()))
{
leaf.setPlaceholder(false);
}
else
{
if (seqmatcher == null)
{
// Only create this the first time we need it
SequenceI[] seqs = new SequenceI[list.size()];
for (int j = 0; j < seqs.length; j++)
{
seqs[j] = list.get(j);
}
seqmatcher = new SequenceIdMatcher(seqs);
}
SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
if (nam != null)
{
if (!leaf.isPlaceholder())
{
// remapping the node to a new sequenceI - should remove any refs to
// old one.
// TODO - make many sequenceI to one leaf mappings possible!
// (JBPNote)
}
leaf.setPlaceholder(false);
leaf.setElement(nam);
}
else
{
if (!leaf.isPlaceholder())
{
// Construct a new placeholder sequence object for this leaf
leaf.setElement(new Sequence(leaf.getName(),
"THISISAPLACEHLDER"));
}
leaf.setPlaceholder(true);
}
}
}
}
/**
* rename any nodes according to their associated sequence. This will modify
* the tree's metadata! (ie the original NewickFile or newly generated
* BinaryTree's label data)
*/
public void renameAssociatedNodes()
{
applyToNodes(new NodeTransformI()
{
@Override
public void transform(BinaryNode nd)
{
Object el = nd.element();
if (el != null && el instanceof SequenceI)
{
nd.setName(((SequenceI) el).getName());
}
}
});
}
/**
* DOCUMENT ME!
*/
void cluster()
{
while (noClus > 2)
{
if (type.equals(NEIGHBOUR_JOINING))
{
findMinNJDistance();
}
else
{
findMinDistance();
}
Cluster c = joinClusters(mini, minj);
done[minj] = 1;
cluster.setElementAt(null, minj);
cluster.setElementAt(c, mini);
noClus--;
}
boolean onefound = false;
int one = -1;
int two = -1;
for (int i = 0; i < noseqs; i++)
{
if (done[i] != 1)
{
if (onefound == false)
{
two = i;
onefound = true;
}
else
{
one = i;
}
}
}
joinClusters(one, two);
top = (node.elementAt(one));
reCount(top);
findHeight(top);
findMaxDist(top);
}
/**
* DOCUMENT ME!
*
* @param i
* DOCUMENT ME!
* @param j
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
Cluster joinClusters(int i, int j)
{
double dist = distances.getValue(i, j);
int noi = cluster.elementAt(i).value.length;
int noj = cluster.elementAt(j).value.length;
int[] value = new int[noi + noj];
for (int ii = 0; ii < noi; ii++)
{
value[ii] = cluster.elementAt(i).value[ii];
}
for (int ii = noi; ii < (noi + noj); ii++)
{
value[ii] = cluster.elementAt(j).value[ii - noi];
}
Cluster c = new Cluster(value);
ri = findr(i, j);
rj = findr(j, i);
if (type.equals(NEIGHBOUR_JOINING))
{
findClusterNJDistance(i, j);
}
else
{
findClusterDistance(i, j);
}
SequenceNode sn = new SequenceNode();
sn.setLeft((node.elementAt(i)));
sn.setRight((node.elementAt(j)));
SequenceNode tmpi = (node.elementAt(i));
SequenceNode tmpj = (node.elementAt(j));
if (type.equals(NEIGHBOUR_JOINING))
{
findNewNJDistances(tmpi, tmpj, dist);
}
else
{
findNewDistances(tmpi, tmpj, dist);
}
tmpi.setParent(sn);
tmpj.setParent(sn);
node.setElementAt(sn, i);
return c;
}
/**
* DOCUMENT ME!
*
* @param tmpi
* DOCUMENT ME!
* @param tmpj
* DOCUMENT ME!
* @param dist
* DOCUMENT ME!
*/
void findNewNJDistances(SequenceNode tmpi, SequenceNode tmpj,
double dist)
{
tmpi.dist = ((dist + ri) - rj) / 2;
tmpj.dist = (dist - tmpi.dist);
if (tmpi.dist < 0)
{
tmpi.dist = 0;
}
if (tmpj.dist < 0)
{
tmpj.dist = 0;
}
}
/**
* DOCUMENT ME!
*
* @param tmpi
* DOCUMENT ME!
* @param tmpj
* DOCUMENT ME!
* @param dist
* DOCUMENT ME!
*/
void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
double dist)
{
double ih = 0;
double jh = 0;
SequenceNode sni = tmpi;
SequenceNode snj = tmpj;
while (sni != null)
{
ih = ih + sni.dist;
sni = (SequenceNode) sni.left();
}
while (snj != null)
{
jh = jh + snj.dist;
snj = (SequenceNode) snj.left();
}
tmpi.dist = ((dist / 2) - ih);
tmpj.dist = ((dist / 2) - jh);
}
/**
* DOCUMENT ME!
*
* @param i
* DOCUMENT ME!
* @param j
* DOCUMENT ME!
*/
void findClusterDistance(int i, int j)
{
int noi = cluster.elementAt(i).value.length;
int noj = cluster.elementAt(j).value.length;
// New distances from cluster to others
double[] newdist = new double[noseqs];
for (int l = 0; l < noseqs; l++)
{
if ((l != i) && (l != j))
{
// newdist[l] = ((distance[i][l] * noi) + (distance[j][l] * noj))
// / (noi + noj);
newdist[l] = ((distances.getValue(i, l) * noi) + (distances.getValue(
j, l) * noj))
/ (noi + noj);
}
else
{
newdist[l] = 0;
}
}
for (int ii = 0; ii < noseqs; ii++)
{
// distance[i][ii] = newdist[ii];
// distance[ii][i] = newdist[ii];
distances.setValue(i, ii, newdist[ii]);
distances.setValue(ii, i, newdist[ii]);
}
}
/**
* DOCUMENT ME!
*
* @param i
* DOCUMENT ME!
* @param j
* DOCUMENT ME!
*/
void findClusterNJDistance(int i, int j)
{
// New distances from cluster to others
double[] newdist = new double[noseqs];
for (int l = 0; l < noseqs; l++)
{
if ((l != i) && (l != j))
{
// newdist[l] = ((distance[i][l] + distance[j][l]) - distance[i][j]) /
// 2;
newdist[l] = (distances.getValue(i, l) + distances.getValue(j, l) - distances
.getValue(i, j)) / 2;
}
else
{
newdist[l] = 0;
}
}
for (int ii = 0; ii < noseqs; ii++)
{
// distance[i][ii] = newdist[ii];
// distance[ii][i] = newdist[ii];
distances.setValue(i, ii, newdist[ii]);
distances.setValue(ii, i, newdist[ii]);
}
}
/**
* DOCUMENT ME!
*
* @param i
* DOCUMENT ME!
* @param j
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
double findr(int i, int j)
{
double tmp = 1;
for (int k = 0; k < noseqs; k++)
{
if ((k != i) && (k != j) && (done[k] != 1))
{
// tmp = tmp + distance[i][k];
tmp = tmp + distances.getValue(i, k);
}
}
if (noClus > 2)
{
tmp = tmp / (noClus - 2);
}
return tmp;
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
double findMinNJDistance()
{
double min = Double.MAX_VALUE;
for (int i = 0; i < (noseqs - 1); i++)
{
for (int j = i + 1; j < noseqs; j++)
{
if ((done[i] != 1) && (done[j] != 1))
{
// float tmp = distance[i][j] - (findr(i, j) + findr(j, i));
double tmp = distances.getValue(i, j)
- (findr(i, j) + findr(j, i));
if (tmp < min)
{
mini = i;
minj = j;
min = tmp;
}
}
}
}
return min;
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
double findMinDistance()
{
double min = Double.MAX_VALUE;
for (int i = 0; i < (noseqs - 1); i++)
{
for (int j = i + 1; j < noseqs; j++)
{
if ((done[i] != 1) && (done[j] != 1))
{
// if (distance[i][j] < min)
if (distances.getValue(i, j) < min)
{
mini = i;
minj = j;
// min = distance[i][j];
min = distances.getValue(i, j);
}
}
}
}
return min;
}
/**
* DOCUMENT ME!
*/
void makeLeaves()
{
cluster = new Vector();
for (int i = 0; i < noseqs; i++)
{
SequenceNode sn = new SequenceNode();
sn.setElement(sequences[i]);
sn.setName(sequences[i].getName());
node.addElement(sn);
int[] value = new int[1];
value[0] = i;
Cluster c = new Cluster(value);
cluster.addElement(c);
}
}
/**
* Search for leaf nodes below (or at) the given node
*
* @param nd
* root node to search from
*
* @return
*/
public Vector findLeaves(SequenceNode nd)
{
Vector leaves = new Vector();
findLeaves(nd, 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(SequenceNode 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((SequenceNode) nd.left(), leaves);
findLeaves((SequenceNode) nd.right(), leaves);
}
return leaves;
}
/**
* printNode is mainly for debugging purposes.
*
* @param nd
* SequenceNode
*/
void printNode(SequenceNode nd)
{
if (nd == null)
{
return;
}
if ((nd.left() == null) && (nd.right() == null))
{
System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
System.out.println("Dist " + nd.dist);
System.out.println("Boot " + nd.getBootstrap());
}
else
{
System.out.println("Dist " + nd.dist);
printNode((SequenceNode) nd.left());
printNode((SequenceNode) nd.right());
}
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*/
void findMaxDist(SequenceNode 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((SequenceNode) nd.left());
findMaxDist((SequenceNode) nd.right());
}
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public Vector getGroups()
{
return groups;
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public double getMaxHeight()
{
return maxheight;
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
* @param threshold
* DOCUMENT ME!
*/
public void groupNodes(SequenceNode nd, float threshold)
{
if (nd == null)
{
return;
}
if ((nd.height / maxheight) > threshold)
{
groups.addElement(nd);
}
else
{
groupNodes((SequenceNode) nd.left(), threshold);
groupNodes((SequenceNode) nd.right(), threshold);
}
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public double findHeight(SequenceNode nd)
{
if (nd == null)
{
return maxheight;
}
if ((nd.left() == null) && (nd.right() == null))
{
nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
if (nd.height > maxheight)
{
return nd.height;
}
else
{
return maxheight;
}
}
else
{
if (nd.parent() != null)
{
nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
}
else
{
maxheight = 0;
nd.height = (float) 0.0;
}
maxheight = findHeight((SequenceNode) (nd.left()));
maxheight = findHeight((SequenceNode) (nd.right()));
}
return maxheight;
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
SequenceNode reRoot()
{
// TODO not used - remove?
if (maxdist != null)
{
ycount = 0;
double tmpdist = maxdist.dist;
// New top
SequenceNode sn = new SequenceNode();
sn.setParent(null);
// New right hand of top
SequenceNode snr = (SequenceNode) maxdist.parent();
changeDirection(snr, maxdist);
System.out.println("Printing reversed tree");
printN(snr);
snr.dist = tmpdist / 2;
maxdist.dist = tmpdist / 2;
snr.setParent(sn);
maxdist.setParent(sn);
sn.setRight(snr);
sn.setLeft(maxdist);
top = sn;
ycount = 0;
reCount(top);
findHeight(top);
}
return top;
}
/**
*
* @return true if original sequence data can be recovered
*/
public boolean hasOriginalSequenceData()
{
return seqData != null;
}
/**
* Returns original alignment data used for calculation - or null where not
* available.
*
* @return null or cut'n'pasteable alignment
*/
public String printOriginalSequenceData(char gapChar)
{
if (seqData == null)
{
return null;
}
StringBuffer sb = new StringBuffer();
String[] seqdatas = seqData.getSequenceStrings(gapChar);
for (int i = 0; i < seqdatas.length; i++)
{
sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequences[i]
.getName()));
sb.append(" " + seqdatas[i] + "\n");
}
return sb.toString();
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*/
void printN(SequenceNode nd)
{
if (nd == null)
{
return;
}
if ((nd.left() != null) && (nd.right() != null))
{
printN((SequenceNode) nd.left());
printN((SequenceNode) nd.right());
}
else
{
System.out.println(" name = " + ((SequenceI) nd.element()).getName());
}
System.out.println(" dist = " + nd.dist + " " + nd.count + " "
+ nd.height);
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*/
public void reCount(SequenceNode nd)
{
ycount = 0;
_lycount = 0;
// _lylimit = this.node.size();
_reCount(nd);
}
private long _lycount = 0, _lylimit = 0;
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
*/
void _reCount(SequenceNode 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((SequenceNode) nd.left());
_reCount((SequenceNode) nd.right());
SequenceNode l = (SequenceNode) nd.left();
SequenceNode r = (SequenceNode) 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!
*/
public void swapNodes(SequenceNode nd)
{
if (nd == null)
{
return;
}
SequenceNode tmp = (SequenceNode) nd.left();
nd.setLeft(nd.right());
nd.setRight(tmp);
}
/**
* DOCUMENT ME!
*
* @param nd
* DOCUMENT ME!
* @param dir
* DOCUMENT ME!
*/
void changeDirection(SequenceNode nd, SequenceNode dir)
{
if (nd == null)
{
return;
}
if (nd.parent() != top)
{
changeDirection((SequenceNode) nd.parent(), nd);
SequenceNode tmp = (SequenceNode) nd.parent();
if (dir == nd.left())
{
nd.setParent(dir);
nd.setLeft(tmp);
}
else if (dir == nd.right())
{
nd.setParent(dir);
nd.setRight(tmp);
}
}
else
{
if (dir == nd.left())
{
nd.setParent(nd.left());
if (top.left() == nd)
{
nd.setRight(top.right());
}
else
{
nd.setRight(top.left());
}
}
else
{
nd.setParent(nd.right());
if (top.left() == nd)
{
nd.setLeft(top.right());
}
else
{
nd.setLeft(top.left());
}
}
}
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public SequenceNode getMaxDist()
{
return maxdist;
}
/**
* DOCUMENT ME!
*
* @return DOCUMENT ME!
*/
public SequenceNode getTopNode()
{
return top;
}
/**
*
* @return true if tree has real distances
*/
public boolean hasDistances()
{
return hasDistances;
}
/**
*
* @return true if tree has real bootstrap values
*/
public boolean hasBootstrap()
{
return hasBootstrap;
}
public boolean hasRootDistance()
{
return hasRootDistance;
}
/**
* apply the given transform to all the nodes in the tree.
*
* @param nodeTransformI
*/
public void applyToNodes(NodeTransformI nodeTransformI)
{
for (Enumeration nodes = node.elements(); nodes
.hasMoreElements(); nodeTransformI.transform(nodes
.nextElement()))
{
;
}
}
}
/**
* DOCUMENT ME!
*
* @author $author$
* @version $Revision$
*/
// TODO what does this class have that int[] doesn't have already?
class Cluster
{
int[] value;
/**
* Creates a new Cluster object.
*
* @param value
* DOCUMENT ME!
*/
public Cluster(int[] value)
{
this.value = value;
}
}