NCBI C++ ToolKit
gme.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: gme.cpp 33815 2007-05-04 17:18:18Z kazimird $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Richard Desper
27 *
28 * File Description: gme.cpp
29 *
30 * A part of the Miminum Evolution algorithm
31 *
32 */
33 
34 #include <ncbi_pch.hpp>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <math.h>
38 #include "graph.h"
39 #include "fastme.h"
40 
42 BEGIN_SCOPE(fastme)
43 
45 boolean leaf(meNode *v);
48 
49 /*from NNI.c*/
50 void fillTableUp(meEdge *e, meEdge *f, double **A, double **D, meTree *T);
51 
52 /*from graph.c*/
53 void updateSizes(meEdge *e, int direction);
54 
55 /*OLSint and OLSext use the average distance array to calculate weights
56  instead of using the meEdge average weight fields*/
57 
58 void OLSext(meEdge *e, double **A)
59 {
60  meEdge *f, *g;
61  if(leaf(e->head))
62  {
63  f = siblingEdge(e);
64  e->distance = 0.5*(A[e->head->index][e->tail->index]
65  + A[e->head->index][f->head->index]
66  - A[f->head->index][e->tail->index]);
67  }
68  else
69  {
70  f = e->head->leftEdge;
71  g = e->head->rightEdge;
72  e->distance = 0.5*(A[e->head->index][f->head->index]
73  + A[e->head->index][g->head->index]
74  - A[f->head->index][g->head->index]);
75  }
76 }
77 
78 double wf(double lambda, double D_LR, double D_LU, double D_LD,
79  double D_RU, double D_RD, double D_DU)
80 {
81  double weight;
82  weight = 0.5*(lambda*(D_LU + D_RD) + (1 -lambda)*(D_LD + D_RU)
83  - (D_LR + D_DU));
84  return(weight);
85 }
86 
87 void OLSint(meEdge *e, double **A)
88 {
89  double lambda;
90  meEdge *left, *right, *sib;
91  left = e->head->leftEdge;
92  right = e->head->rightEdge;
93  sib = siblingEdge(e);
94  lambda = ((double) sib->bottomsize*left->bottomsize +
95  right->bottomsize*e->tail->parentEdge->topsize) /
96  (e->bottomsize*e->topsize);
97  e->distance = wf(lambda,A[left->head->index][right->head->index],
98  A[left->head->index][e->tail->index],
99  A[left->head->index][sib->head->index],
100  A[right->head->index][e->tail->index],
101  A[right->head->index][sib->head->index],
102  A[sib->head->index][e->tail->index]);
103 }
104 
105 
106 void assignOLSWeights(meTree *T, double **A)
107 {
108  meEdge *e;
110  while (NULL != e) {
111  if ((leaf(e->head)) || (leaf(e->tail)))
112  OLSext(e,A);
113  else
114  OLSint(e,A);
115  e = depthFirstTraverse(T,e);
116  }
117 }
118 
119 /*makes table of average distances from scratch*/
120 void makeOLSAveragesTable(meTree *T, double **D, double **A)
121 {
122  meEdge *e, *f, *g, *h;
123  meEdge *exclude;
124  e = f = NULL;
125  e = depthFirstTraverse(T,e);
126  while (NULL != e)
127  {
128  f = e;
129  exclude = e->tail->parentEdge;
130  /*we want to calculate A[e->head][f->head] for all edges
131  except those edges which are ancestral to e. For those
132  edges, we will calculate A[e->head][f->head] to have a
133  different meaning, later*/
134  if(leaf(e->head))
135  while (NULL != f)
136  {
137  if (exclude != f)
138  {
139  if (leaf(f->head))
140  A[e->head->index][f->head->index] = A[f->head->index][e->head->index] = D[e->head->index2][f->head->index2];
141  else
142  {
143  g = f->head->leftEdge;
144  h = f->head->rightEdge;
145  A[e->head->index][f->head->index] = A[f->head->index][e->head->index] = (g->bottomsize*A[e->head->index][g->head->index] + h->bottomsize*A[e->head->index][h->head->index])/f->bottomsize;
146  }
147  }
148  else /*exclude == f*/
149  exclude = exclude->tail->parentEdge;
150  f = depthFirstTraverse(T,f);
151  }
152  else
153  /*e->head is not a leaf, so we go recursively to values calculated for
154  the nodes below e*/
155  while(NULL !=f )
156  {
157  if (exclude != f)
158  {
159  g = e->head->leftEdge;
160  h = e->head->rightEdge;
161  A[e->head->index][f->head->index] = A[f->head->index][e->head->index] = (g->bottomsize*A[f->head->index][g->head->index] + h->bottomsize*A[f->head->index][h->head->index])/e->bottomsize;
162  }
163  else
164  exclude = exclude->tail->parentEdge;
165  f = depthFirstTraverse(T,f);
166  }
167 
168  /*now we move to fill up the rest of the table: we want
169  A[e->head->index][f->head->index] for those cases where e is an
170  ancestor of f, or vice versa. We'll do this by choosing e via a
171  depth first-search, and the recursing for f up the path to the
172  root*/
173  f = e->tail->parentEdge;
174  if (NULL != f)
175  fillTableUp(e,f,A,D,T);
176  e = depthFirstTraverse(T,e);
177  }
178 
179  /*we are indexing this table by vertex indices, but really the
180  underlying object is the meEdge set. Thus, the array is one element
181  too big in each direction, but we'll ignore the entries involving the root,
182  and instead refer to each meEdge by the head of that edge. The head of
183  the root points to the meEdge ancestral to the rest of the tree, so
184  we'll keep track of up distances by pointing to that head*/
185 
186  /*10/13/2001: collapsed three depth-first searces into 1*/
187 }
188 
189 
190 void GMEcalcDownAverage(meNode *v, meEdge *e, double **D, double **A)
191 {
192  meEdge *left, *right;
193  if (leaf(e->head))
194  A[e->head->index][v->index] = D[v->index2][e->head->index2];
195  else
196  {
197  left = e->head->leftEdge;
198  right = e->head->rightEdge;
199  A[e->head->index][v->index] =
200  ( left->bottomsize * A[left->head->index][v->index] +
201  right->bottomsize * A[right->head->index][v->index])
202  / e->bottomsize;
203  }
204 }
205 
206 void GMEcalcUpAverage(meNode *v, meEdge *e, double **D, double **A)
207 {
208  meEdge *up, *down;
209  if (NULL == e->tail->parentEdge)
210  A[v->index][e->head->index] = D[v->index2][e->tail->index2];
211  else
212  {
213  up = e->tail->parentEdge;
214  down = siblingEdge(e);
215  A[v->index][e->head->index] =
216  (up->topsize * A[v->index][up->head->index] +
217  down->bottomsize * A[down->head->index][v->index])
218  / e->topsize;
219  }
220 }
221 
222 /*this function calculates average distance D_Xv for each X which is
223  a meSet of leaves of an induced submeTree of T*/
224 void GMEcalcNewvAverages(meTree *T, meNode *v, double **D, double **A)
225 {
226  /*loop over edges*/
227  /*depth-first search*/
228  meEdge *e;
229  e = NULL;
230  e = depthFirstTraverse(T,e); /*the downward averages need to be
231  calculated from bottom to top */
232  while(NULL != e)
233  {
234  GMEcalcDownAverage(v,e,D,A);
235  e = depthFirstTraverse(T,e);
236  }
237 
238  e = topFirstTraverse(T,e); /*the upward averages need to be calculated
239  from top to bottom */
240  while(NULL != e)
241  {
242  GMEcalcUpAverage(v,e,D,A);
243  e = topFirstTraverse(T,e);
244  }
245 }
246 
247 double wf4(double lambda, double lambda2, double D_AB, double D_AC,
248  double D_BC, double D_Av, double D_Bv, double D_Cv)
249 {
250  return(((1 - lambda) * (D_AC + D_Bv) + (lambda2 - 1)*(D_AB + D_Cv)
251  + (lambda - lambda2)*(D_BC + D_Av)));
252 }
253 
254 
255 /*testEdge cacluates what the OLS weight would be if v were inserted into
256  T along e. Compare against known values for inserting along
257  f = e->parentEdge */
258 /*edges are tested by a top-first, left-first scheme. we presume
259  all distances are fixed to the correct weight for
260  e->parentEdge, if e is a left-oriented edge*/
261 void testEdge(meEdge *e, meNode *v, double **A)
262 {
263  double lambda, lambda2;
264  meEdge *par, *sib;
265  sib = siblingEdge(e);
266  par = e->tail->parentEdge;
267  /*C is meSet above e->tail, B is meSet below e, and A is meSet below sib*/
268  /*following the nomenclature of Desper & Gascuel*/
269  lambda = (((double) (sib->bottomsize + e->bottomsize*par->topsize))
270  / ((1 + par->topsize)*(par->bottomsize)));
271  lambda2 = (((double) (sib->bottomsize + e->bottomsize*par->topsize))
272  / ((1 + e->bottomsize)*(e->topsize)));
273  e->totalweight = par->totalweight
274  + wf4(lambda,lambda2,A[e->head->index][sib->head->index],
275  A[sib->head->index][e->tail->index],
276  A[e->head->index][e->tail->index],
277  A[sib->head->index][v->index],A[e->head->index][v->index],
278  A[v->index][e->tail->index]);
279 }
280 
281 void printDoubleTable(double **A, int d)
282 {
283  int i,j;
284  for(i=0;i<d;i++)
285  {
286  for(j=0;j<d;j++)
287  printf("%lf ", A[i][j]);
288  printf("\n");
289  }
290 }
291 
292 void GMEsplitEdge(meTree *T, meNode *v, meEdge *e, double **A);
293 
294 meTree *GMEaddSpecies(meTree *T,meNode *v, double **D, double **A)
295  /*the key function of the program addSpeices inserts
296  the meNode v to the meTree T. It uses testEdge to see what the
297  weight would be if v split a particular edge. Weights are assigned by
298  OLS formula*/
299 {
300  meTree *T_e;
301  meEdge *e; /*loop variable*/
302  meEdge *e_min; /*points to best meEdge seen thus far*/
303  double w_min = 0.0; /*used to keep track of meTree weights*/
304 
305  if (verbose)
306  printf("Adding %s.\n",v->label);
307 
308  /*initialize variables as necessary*/
309  /*CASE 1: T is empty, v is the first node*/
310  if (NULL == T) /*create a meTree with v as only vertex, no edges*/
311  {
312  T_e = newTree();
313  T_e->root = v;
314  /*note that we are rooting T arbitrarily at a leaf.
315  T->root is not the phylogenetic root*/
316  v->index = 0;
317  T_e->size = 1;
318  return(T_e);
319  }
320  /*CASE 2: T is a single-vertex tree*/
321  if (1 == T->size)
322  {
323  v->index = 1;
324  e = makeEdge("",T->root,v,0.0);
325  sprintf(e->label,"E1");
326  e->topsize = 1;
327  e->bottomsize = 1;
328  A[v->index][v->index] = D[v->index2][T->root->index2];
329  T->root->leftEdge = v->parentEdge = e;
330  T->size = 2;
331  return(T);
332  }
333  /*CASE 3: T has at least two nodes and an edge. Insert new node
334  by breaking one of the edges*/
335 
336  v->index = T->size;
337  /*if (!(T->size % 100))
338  printf("T->size is %d\n",T->size);*/
339  GMEcalcNewvAverages(T,v,D,A);
340  /*calcNewvAverges will assign values to all the meEdge averages of T which
341  include the meNode v. Will do so using pre-existing averages in T and
342  information from A,D*/
343  e_min = T->root->leftEdge;
344  e = e_min->head->leftEdge;
345  while (NULL != e)
346  {
347  testEdge(e,v,A);
348  /*testEdge tests weight of meTree if loop variable
349  e is the meEdge split, places this weight in e->totalweight field */
350  if (e->totalweight < w_min)
351  {
352  e_min = e;
353  w_min = e->totalweight;
354  }
355  e = topFirstTraverse(T,e);
356  }
357  /*e_min now points at the meEdge we want to split*/
358  GMEsplitEdge(T,v,e_min,A);
359  return(T);
360 }
361 
362 void updateSubTreeAverages(double **A, meEdge *e, meNode *v, int direction);
363 
364 /*the ME version of updateAveragesMatrix does not update the entire matrix
365  A, but updates A[v->index][w->index] whenever this represents an average
366  of 1-distant or 2-distant subtrees*/
367 
368 void GMEupdateAveragesMatrix(double **A, meEdge *e, meNode *v, meNode *newNode)
369 {
370  meEdge *sib, *par, *left, *right;
371  sib = siblingEdge(e);
372  left = e->head->leftEdge;
373  right = e->head->rightEdge;
374  par = e->tail->parentEdge;
375 
376  /*we need to update the matrix A so all 1-distant, 2-distant, and
377  3-distant averages are correct*/
378 
379  /*first, initialize the newNode entries*/
380  /*1-distant*/
381  A[newNode->index][newNode->index] =
382  (e->bottomsize*A[e->head->index][e->head->index]
383  + A[v->index][e->head->index])
384  / (e->bottomsize + 1);
385  /*1-distant for v*/
386  A[v->index][v->index] =
387  (e->bottomsize*A[e->head->index][v->index]
388  + e->topsize*A[v->index][e->head->index])
389  / (e->bottomsize + e->topsize);
390 
391  /*2-distant for v,newNode*/
392  A[v->index][newNode->index] = A[newNode->index][v->index] =
393  A[v->index][e->head->index];
394 
395  /*second 2-distant for newNode*/
396  A[newNode->index][e->tail->index] = A[e->tail->index][newNode->index]
397  = (e->bottomsize*A[e->head->index][e->tail->index]
398  + A[v->index][e->tail->index])/(e->bottomsize + 1);
399  /*third 2-distant for newNode*/
400  A[newNode->index][e->head->index] = A[e->head->index][newNode->index]
401  = A[e->head->index][e->head->index];
402 
403  if (NULL != sib)
404  {
405  /*fourth and last 2-distant for newNode*/
406  A[newNode->index][sib->head->index] =
407  A[sib->head->index][newNode->index] =
408  (e->bottomsize*A[sib->head->index][e->head->index]
409  + A[sib->head->index][v->index]) / (e->bottomsize + 1);
410  updateSubTreeAverages(A,sib,v,SKEW); /*updates sib and below*/
411  }
412  if (NULL != par)
413  {
414  if (e->tail->leftEdge == e)
415  updateSubTreeAverages(A,par,v,LEFT); /*updates par and above*/
416  else
417  updateSubTreeAverages(A,par,v,RIGHT);
418  }
419  if (NULL != left)
420  updateSubTreeAverages(A,left,v,UP); /*updates left and below*/
421  if (NULL != right)
422  updateSubTreeAverages(A,right,v,UP); /*updates right and below*/
423 
424  /*1-dist for e->head*/
425  A[e->head->index][e->head->index] =
426  (e->topsize*A[e->head->index][e->head->index]
427  + A[e->head->index][v->index]) / (e->topsize+1);
428  /*2-dist for e->head (v,newNode,left,right)
429  taken care of elsewhere*/
430  /*3-dist with e->head either taken care of elsewhere (below)
431  or unchanged (sib,e->tail)*/
432 
433  /*symmetrize the matrix (at least for distant-2 subtrees) */
434  A[v->index][e->head->index] = A[e->head->index][v->index];
435  /*and distant-3 subtrees*/
436  A[e->tail->index][v->index] = A[v->index][e->tail->index];
437  if (NULL != left)
438  A[v->index][left->head->index] = A[left->head->index][v->index];
439  if (NULL != right)
440  A[v->index][right->head->index] = A[right->head->index][v->index];
441  if (NULL != sib)
442  A[v->index][sib->head->index] = A[sib->head->index][v->index];
443 
444 }
445 
446 void GMEsplitEdge(meTree *T, meNode *v, meEdge *e, double **A)
447 {
448  char nodelabel[NODE_LABEL_LENGTH];
449  char edgelabel[EDGE_LABEL_LENGTH];
450  meEdge *newPendantEdge;
451  meEdge *newInternalEdge;
452  meNode *newNode;
453 
454  sprintf(nodelabel,"I%d",T->size+1);
455  newNode = makeNewNode(nodelabel,T->size + 1);
456 
457  sprintf(edgelabel,"E%d",T->size);
458  newPendantEdge = makeEdge(edgelabel,newNode,v,0.0);
459 
460  sprintf(edgelabel,"E%d",T->size+1);
461  newInternalEdge = makeEdge(edgelabel,newNode,e->head,0.0);
462 
463  if (verbose)
464  printf("Inserting meNode %s on meEdge %s between nodes %s and %s.\n",
465  v->label,e->label,e->tail->label,e->head->label);
466  /*update the matrix of average distances*/
467  /*also updates the bottomsize, topsize fields*/
468 
469  GMEupdateAveragesMatrix(A,e,v,newNode);
470 
471  newNode->parentEdge = e;
472  e->head->parentEdge = newInternalEdge;
473  v->parentEdge = newPendantEdge;
474  e->head = newNode;
475 
476  T->size = T->size + 2;
477 
478  if (e->tail->leftEdge == e)
479  {
480  newNode->leftEdge = newInternalEdge;
481  newNode->rightEdge = newPendantEdge;
482  }
483  else
484  {
485  newNode->leftEdge = newInternalEdge;
486  newNode->rightEdge = newPendantEdge;
487  }
488 
489  /*assign proper topsize, bottomsize values to the two new Edges*/
490 
491  newPendantEdge->bottomsize = 1;
492  newPendantEdge->topsize = e->bottomsize + e->topsize;
493 
494  newInternalEdge->bottomsize = e->bottomsize;
495  newInternalEdge->topsize = e->topsize; /*off by one, but we adjust
496  that below*/
497 
498  /*and increment these fields for all other edges*/
499  updateSizes(newInternalEdge,UP);
500  updateSizes(e,DOWN);
501 }
502 
503 void updateSubTreeAverages(double **A, meEdge *e, meNode *v, int direction)
504  /*the monster function of this program*/
505 {
506  meEdge *sib, *left, *right, *par;
507  left = e->head->leftEdge;
508  right = e->head->rightEdge;
509  sib = siblingEdge(e);
510  par = e->tail->parentEdge;
511  switch(direction)
512  {
513  /*want to preserve correctness of
514  all 1-distant, 2-distant, and 3-distant averages*/
515  /*1-distant updated at meEdge splitting the two trees*/
516  /*2-distant updated:
517  (left->head,right->head) and (head,tail) updated at
518  a given edge. Note, NOT updating (head,sib->head)!
519  (That would lead to multiple updating).*/
520  /*3-distant updated: at meEdge in center of quartet*/
521  case UP: /*point of insertion is above e*/
522  /*1-distant average of nodes below e to
523  nodes above e*/
524  A[e->head->index][e->head->index] =
525  (e->topsize*A[e->head->index][e->head->index] +
526  A[e->head->index][v->index])/(e->topsize + 1);
527  /*2-distant average of nodes below e to
528  nodes above parent of e*/
529  A[e->head->index][par->head->index] =
530  A[par->head->index][e->head->index] =
531  (par->topsize*A[par->head->index][e->head->index]
532  + A[e->head->index][v->index]) / (par->topsize + 1);
533  /*must do both 3-distant averages involving par*/
534  if (NULL != left)
535  {
536  updateSubTreeAverages(A, left, v, UP); /*and recursive call*/
537  /*3-distant average*/
538  A[par->head->index][left->head->index]
539  = A[left->head->index][par->head->index]
540  = (par->topsize*A[par->head->index][left->head->index]
541  + A[left->head->index][v->index]) / (par->topsize + 1);
542  }
543  if (NULL != right)
544  {
545  updateSubTreeAverages(A, right, v, UP);
546  A[par->head->index][right->head->index]
547  = A[right->head->index][par->head->index]
548  = (par->topsize*A[par->head->index][right->head->index]
549  + A[right->head->index][v->index]) / (par->topsize + 1);
550  }
551  break;
552  case SKEW: /*point of insertion is skew to e*/
553  /*1-distant average of nodes below e to
554  nodes above e*/
555  A[e->head->index][e->head->index] =
556  (e->topsize*A[e->head->index][e->head->index] +
557  A[e->head->index][v->index])/(e->topsize + 1);
558  /*no 2-distant averages to update in this case*/
559  /*updating 3-distant averages involving sib*/
560  if (NULL != left)
561  {
562  updateSubTreeAverages(A, left, v, UP);
563  A[sib->head->index][left->head->index]
564  = A[left->head->index][sib->head->index]
565  = (sib->bottomsize*A[sib->head->index][left->head->index]
566  + A[left->head->index][v->index]) / (sib->bottomsize + 1);
567  }
568  if (NULL != right)
569  {
570  updateSubTreeAverages(A, right, v, UP);
571  A[sib->head->index][right->head->index]
572  = A[right->head->index][sib->head->index]
573  = (sib->bottomsize*A[par->head->index][right->head->index]
574  + A[right->head->index][v->index]) / (sib->bottomsize + 1);
575  }
576  break;
577 
578 
579  case LEFT: /*point of insertion is below the meEdge left*/
580  /*1-distant average*/
581  A[e->head->index][e->head->index] =
582  (e->bottomsize*A[e->head->index][e->head->index] +
583  A[v->index][e->head->index])/(e->bottomsize + 1);
584  /*2-distant averages*/
585  A[e->head->index][e->tail->index] =
586  A[e->tail->index][e->head->index] =
587  (e->bottomsize*A[e->head->index][e->tail->index] +
588  A[v->index][e->tail->index])/(e->bottomsize + 1);
589  A[left->head->index][right->head->index] =
590  A[right->head->index][left->head->index] =
591  (left->bottomsize*A[right->head->index][left->head->index]
592  + A[right->head->index][v->index]) / (left->bottomsize+1);
593  /*3-distant avereages involving left*/
594  if (NULL != sib)
595  {
596  updateSubTreeAverages(A, sib, v, SKEW);
597  A[left->head->index][sib->head->index]
598  = A[sib->head->index][left->head->index]
599  = (left->bottomsize*A[left->head->index][sib->head->index]
600  + A[sib->head->index][v->index]) / (left->bottomsize + 1);
601  }
602  if (NULL != par)
603  {
604  if (e->tail->leftEdge == e)
605  updateSubTreeAverages(A, par, v, LEFT);
606  else
607  updateSubTreeAverages(A, par, v, RIGHT);
608  A[left->head->index][par->head->index]
609  = A[par->head->index][left->head->index]
610  = (left->bottomsize*A[left->head->index][par->head->index]
611  + A[v->index][par->head->index]) / (left->bottomsize + 1);
612  }
613  break;
614  case RIGHT: /*point of insertion is below the meEdge right*/
615  /*1-distant average*/
616  A[e->head->index][e->head->index] =
617  (e->bottomsize*A[e->head->index][e->head->index] +
618  A[v->index][e->head->index])/(e->bottomsize + 1);
619  /*2-distant averages*/
620  A[e->head->index][e->tail->index] =
621  A[e->tail->index][e->head->index] =
622  (e->bottomsize*A[e->head->index][e->tail->index] +
623  A[v->index][e->tail->index])/(e->bottomsize + 1);
624  A[left->head->index][right->head->index] =
625  A[right->head->index][left->head->index] =
626  (right->bottomsize*A[right->head->index][left->head->index]
627  + A[left->head->index][v->index]) / (right->bottomsize+1);
628  /*3-distant avereages involving right*/
629  if (NULL != sib)
630  {
631  updateSubTreeAverages(A, sib, v, SKEW);
632  A[right->head->index][sib->head->index]
633  = A[sib->head->index][right->head->index]
634  = (right->bottomsize*A[right->head->index][sib->head->index]
635  + A[sib->head->index][v->index]) / (right->bottomsize + 1);
636  }
637  if (NULL != par)
638  {
639  if (e->tail->leftEdge == e)
640  updateSubTreeAverages(A, par, v, LEFT);
641  else
642  updateSubTreeAverages(A, par, v, RIGHT);
643  A[right->head->index][par->head->index]
644  = A[par->head->index][right->head->index]
645  = (right->bottomsize*A[right->head->index][par->head->index]
646  + A[v->index][par->head->index]) / (right->bottomsize + 1);
647  }
648 
649  break;
650  }
651 }
652 
654 {
655  if (leaf(e->head))
656  e->bottomsize = 1;
657  else
658  {
662  + e->head->rightEdge->bottomsize;
663  }
664 }
665 
666 void assignTopsize(meEdge *e, int numLeaves)
667 {
668  if (NULL != e)
669  {
670  e->topsize = numLeaves - e->bottomsize;
671  assignTopsize(e->head->leftEdge,numLeaves);
672  assignTopsize(e->head->rightEdge,numLeaves);
673  }
674 }
675 
677 {
678  assignBottomsize(T->root->leftEdge);
679  assignTopsize(T->root->leftEdge,T->size/2 + 1);
680 }
681 
682 
683 END_SCOPE(fastme)
#define T(s)
Definition: common.h:230
#define UP
Definition: fastme.h:50
#define SKEW
Definition: fastme.h:54
#define DOWN
Definition: fastme.h:51
#define LEFT
Definition: fastme.h:52
#define RIGHT
Definition: fastme.h:53
void printDoubleTable(double **A, int d)
Definition: gme.cpp:281
void assignAllSizeFields(meTree *T)
Definition: gme.cpp:676
double wf4(double lambda, double lambda2, double D_AB, double D_AC, double D_BC, double D_Av, double D_Bv, double D_Cv)
Definition: gme.cpp:247
void GMEsplitEdge(meTree *T, meNode *v, meEdge *e, double **A)
Definition: gme.cpp:446
void OLSint(meEdge *e, double **A)
Definition: gme.cpp:87
void assignTopsize(meEdge *e, int numLeaves)
Definition: gme.cpp:666
boolean leaf(meNode *v)
Definition: graph.cpp:44
meEdge * siblingEdge(meEdge *e)
Definition: graph.cpp:210
void updateSubTreeAverages(double **A, meEdge *e, meNode *v, int direction)
Definition: gme.cpp:503
void GMEupdateAveragesMatrix(double **A, meEdge *e, meNode *v, meNode *newNode)
Definition: gme.cpp:368
void testEdge(meEdge *e, meNode *v, double **A)
Definition: gme.cpp:261
void GMEcalcNewvAverages(meTree *T, meNode *v, double **D, double **A)
Definition: gme.cpp:224
double wf(double lambda, double D_LR, double D_LU, double D_LD, double D_RU, double D_RD, double D_DU)
Definition: gme.cpp:78
void GMEcalcDownAverage(meNode *v, meEdge *e, double **D, double **A)
Definition: gme.cpp:190
void assignBottomsize(meEdge *e)
Definition: gme.cpp:653
meTree * GMEaddSpecies(meTree *T, meNode *v, double **D, double **A)
Definition: gme.cpp:294
void GMEcalcUpAverage(meNode *v, meEdge *e, double **D, double **A)
Definition: gme.cpp:206
meEdge * depthFirstTraverse(meTree *T, meEdge *e)
Definition: traverse.cpp:65
meEdge * topFirstTraverse(meTree *T, meEdge *e)
Definition: traverse.cpp:107
void assignOLSWeights(meTree *T, double **A)
Definition: gme.cpp:106
void updateSizes(meEdge *e, int direction)
Definition: graph.cpp:218
void makeOLSAveragesTable(meTree *T, double **D, double **A)
Definition: gme.cpp:120
void OLSext(meEdge *e, double **A)
Definition: gme.cpp:58
void fillTableUp(meEdge *e, meEdge *f, double **A, double **D, meTree *T)
Definition: NNI.cpp:56
meTree * newTree()
Definition: graph.cpp:102
meEdge * makeEdge(const char *label, meNode *tail, meNode *head, double weight)
Definition: graph.cpp:90
meNode * makeNewNode(const char *label, int i)
Definition: graph.cpp:164
#define NODE_LABEL_LENGTH
Definition: graph.h:43
#define EDGE_LABEL_LENGTH
Definition: graph.h:44
#define NULL
Definition: ncbistd.hpp:225
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define END_SCOPE(ns)
End the previously defined scope.
Definition: ncbistl.hpp:75
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
#define BEGIN_SCOPE(ns)
Define a new scope.
Definition: ncbistl.hpp:72
n font weight
int i
double lambda(size_t dimMatrix_, const Int4 *const *scoreMatrix_, const double *q_)
double f(double x_, const double &y_)
Definition: njn_root.hpp:188
true_type verbose
Definition: processing.cpp:890
Definition: graph.h:84
struct meNode * tail
Definition: graph.h:86
int topsize
Definition: graph.h:89
double distance
Definition: graph.h:90
char label[50]
Definition: graph.h:85
struct meNode * head
Definition: graph.h:87
int bottomsize
Definition: graph.h:88
double totalweight
Definition: graph.h:91
Definition: graph.h:74
struct meEdge * rightEdge
Definition: graph.h:79
struct meEdge * parentEdge
Definition: graph.h:76
int index2
Definition: graph.h:81
char label[50]
Definition: graph.h:75
struct meEdge * leftEdge
Definition: graph.h:77
int index
Definition: graph.h:80
Definition: graph.h:94
int size
Definition: graph.h:97
struct meNode * root
Definition: graph.h:96
int g(Seg_Gsm *spe, Seq_Mtf *psm, Thd_Gsm *tdg)
Definition: thrddgri.c:44
Modified on Sat Jun 15 11:51:59 2024 by modify_doxy.py rev. 669887