private void computeUPMATree(Taxa taxa,Distances dist,PhyloTree tree){
  tree.clear();
  int ntax=dist.getNtax();
  Node[] subtrees=new Node[ntax + 1];
  int[] sizes=new int[ntax + 1];
  double[] heights=new double[ntax + 1];
  for (int i=1; i <= ntax; i++) {
    subtrees[i]=tree.newNode();
    tree.setLabel(subtrees[i],taxa.getLabel(i));
    sizes[i]=1;
  }
  double d[][]=new double[ntax + 1][ntax + 1];
  for (int i=1; i <= ntax; i++) {
    for (int j=i + 1; j <= ntax; j++) {
      double dij=(dist.get(i,j) + dist.get(j,i)) / 2.0;
      d[i][j]=d[j][i]=dij;
    }
  }
  for (int actual=ntax; actual > 2; actual--) {
    int i_min=0, j_min=0;
    double d_min=Double.MAX_VALUE;
    for (int i=1; i <= actual; i++) {
      for (int j=i + 1; j <= actual; j++) {
        double dij=d[i][j];
        if (i_min == 0 || dij < d_min) {
          i_min=i;
          j_min=j;
          d_min=dij;
        }
      }
    }
    double height=d_min / 2.0;
    Node v=tree.newNode();
    Edge e=tree.newEdge(v,subtrees[i_min]);
    tree.setWeight(e,Math.max(height - heights[i_min],0.0));
    Edge f=tree.newEdge(v,subtrees[j_min]);
    tree.setWeight(f,Math.max(height - heights[j_min],0.0));
    subtrees[i_min]=v;
    subtrees[j_min]=null;
    heights[i_min]=height;
    int size_i=sizes[i_min];
    int size_j=sizes[j_min];
    sizes[i_min]=size_i + size_j;
    for (int k=1; k <= ntax; k++) {
      if ((k == i_min) || k == j_min)       continue;
      double dki=(d[k][i_min] * size_i + d[k][j_min] * size_j) / ((double)(size_i + size_j));
      d[k][i_min]=d[i_min][k]=dki;
    }
    if (j_min < actual) {
      for (int k=1; k <= actual; k++) {
        d[j_min][k]=d[k][j_min]=d[actual][k];
      }
      d[j_min][j_min]=0.0;
      subtrees[j_min]=subtrees[actual];
      sizes[j_min]=sizes[actual];
      heights[j_min]=heights[actual];
    }
  }
  int sister=2;
  while (subtrees[sister] == null)   sister++;
  Node root=tree.newNode();
  tree.setRoot(root);
  double w1, w2;
  double delta=Math.abs(heights[1] - heights[sister]);
  double distance=d[1][sister] - delta;
  if (heights[1] <= heights[sister]) {
    w1=0.5 * distance + delta;
    w2=0.5 * distance;
  }
 else {
    w1=0.5 * distance;
    w2=0.5 * distance + delta;
  }
  Edge e1=tree.newEdge(root,subtrees[1]);
  tree.setWeight(e1,w1);
  Edge e2=tree.newEdge(root,subtrees[sister]);
  tree.setWeight(e2,w2);
}

private void computeUPMATree ( Taxa taxa , Distances dist , PhyloTree tree ) { tree . clear ( ) ; int ntax = dist . getNtax ( ) ; Node [ ] subtrees = new Node [ ntax + 1 ] ; int [ ] sizes = new int [ ntax + 1 ] ; double [ ] heights = new double [ ntax + 1 ] ; for ( int i = 1 ; i <= ntax ; i ++ ) { subtrees [ i ] = tree . newNode ( ) ; tree . setLabel ( subtrees [ i ] , taxa . getLabel ( i ) ) ; sizes [ i ] = 1 ; } double d [ ] [ ] = new double [ ntax + 1 ] [ ntax + 1 ] ; for ( int i = 1 ; i <= ntax ; i ++ ) { for ( int j = i + 1 ; j <= ntax ; j ++ ) { double dij = ( dist . get ( i , j ) + dist . get ( j , i ) ) / 2.0 ; d [ i ] [ j ] = d [ j ] [ i ] = dij ; } } for ( int actual = ntax ; actual > 2 ; actual -- ) { int i_min = 0 , j_min = 0 ; double d_min = Double . MAX_VALUE ; for ( int i = 1 ; i <= actual ; i ++ ) { for ( int j = i + 1 ; j <= actual ; j ++ ) { double dij = d [ i ] [ j ] ; if ( i_min == 0 || dij < d_min ) { i_min = i ; j_min = j ; d_min = dij ; } } } double height = d_min / 2.0 ; Node v = tree . newNode ( ) ; Edge e = tree . newEdge ( v , subtrees [ i_min ] ) ; tree . setWeight ( e , Math . max ( height - heights [ i_min ] , 0.0 ) ) ; Edge f = tree . newEdge ( v , subtrees [ j_min ] ) ; tree . setWeight ( f , Math . max ( height - heights [ j_min ] , 0.0 ) ) ; subtrees [ i_min ] = v ; subtrees [ j_min ] = null ; heights [ i_min ] = height ; int size_i = sizes [ i_min ] ; int size_j = sizes [ j_min ] ; sizes [ i_min ] = size_i + size_j ; for ( int k = 1 ; k <= ntax ; k ++ ) { if ( ( k == i_min ) || k == j_min ) continue ; double dki = ( d [ k ] [ i_min ] * size_i + d [ k ] [ j_min ] * size_j ) / ( ( double ) ( size_i + size_j ) ) ; d [ k ] [ i_min ] = d [ i_min ] [ k ] = dki ; } if ( j_min < actual ) { for ( int k = 1 ; k <= actual ; k ++ ) { d [ j_min ] [ k ] = d [ k ] [ j_min ] = d [ actual ] [ k ] ; } d [ j_min ] [ j_min ] = 0.0 ; subtrees [ j_min ] = subtrees [ actual ] ; sizes [ j_min ] = sizes [ actual ] ; heights [ j_min ] = heights [ actual ] ; } } int sister = 2 ; while ( subtrees [ sister ] == null ) sister ++ ; Node root = tree . newNode ( ) ; tree . setRoot ( root ) ; double w1 , w2 ; double delta = Math . abs ( heights [ 1 ] - heights [ sister ] ) ; double distance = d [ 1 ] [ sister ] - delta ; if ( heights [ 1 ] <= heights [ sister ] ) { w1 = 0.5 * distance + delta ; w2 = 0.5 * distance ; } else { w1 = 0.5 * distance ; w2 = 0.5 * distance + delta ; } Edge e1 = tree . newEdge ( root , subtrees [ 1 ] ) ; tree . setWeight ( e1 , w1 ) ; Edge e2 = tree . newEdge ( root , subtrees [ sister ] ) ; tree . setWeight ( e2 , w2 ) ; }
run the upgma algorithm
