1 package fr.orsay.lri.varna.models.treealign;
7 * Tree alignment algorithm.
8 * This class implements the tree alignment algorithm
9 * for ordered trees explained in article:
10 * T. Jiang, L. Wang, K. Zhang,
11 * Alignment of trees - an alternative to tree edit,
12 * Theoret. Comput. Sci. 143 (1995).
14 * - Claire Herrbach, Alain Denise and Serge Dulucq.
15 * Average complexity of the Jiang-Wang-Zhang pairwise tree alignment
16 * algorithm and of a RNA secondary structure alignment algorithm.
17 * Theoretical Computer Science 411 (2010) 2423-2432.
19 * Our implementation supposes that the trees will never have more
20 * than 32000 nodes and that the total distance will never require more
21 * significant digits that a float (single precision) has.
23 * @author Raphael Champeimont
24 * @param <ValueType1> The type of values on nodes in the first tree.
25 * @param <ValueType2> The type of values on nodes in the second tree.
27 public class TreeAlign<ValueType1, ValueType2> {
29 private class TreeData<ValueType> {
33 public Tree<ValueType> tree;
36 * The tree size (number of nodes).
41 * The number of children of a node is called the node degree.
42 * This variable is the maximum node degree in the tree.
44 public int degree = -1;
47 * The number of children of a node is called the node degree.
48 * degree[i] is the degree of node i, with i being an index in nodes.
53 * The trees as an array of its nodes (subtrees rooted at each node
54 * in fact), in postorder.
56 public Tree<ValueType>[] nodes;
59 * children[i] is the array of children (as indexes in nodes)
60 * of i (an index in nodes)
62 public int[][] children;
67 public ValueType[] values;
72 * The distance function between labels.
74 private TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist;
78 * Create a TreeAlignSymmetric object, which can align trees.
79 * The distance function will be called only once on every pair
80 * of nodes. The result is then kept in a matrix, so you need not manage
81 * yourself a cache of f(value1, value2).
82 * Note that it is permitted to have null values on nodes,
83 * so comparing a node with a non-null value with a node with a null
84 * value will give the same cost as to insert the first node.
85 * This can be useful if you tree has "fake" nodes.
86 * @param labelDist The label distance.
88 public TreeAlign(TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist) {
89 this.labelDist = labelDist;
94 private class ConvertTreeToArray<ValueType> {
95 private int nextNodeIndex = 0;
96 private TreeData<ValueType> treeData;
98 public ConvertTreeToArray(TreeData<ValueType> treeData) {
99 this.treeData = treeData;
102 private void convertTreeToArrayAux(
103 Tree<ValueType> subtree,
104 int[] siblingIndexes,
105 int siblingNumber) throws TreeAlignException {
106 // We want it in postorder, so first we put the children
107 List<Tree<ValueType>> children = subtree.getChildren();
108 int numberOfChildren = children.size();
109 int[] childrenIndexes = new int[numberOfChildren];
113 for (Tree<ValueType> child: children) {
114 convertTreeToArrayAux(child, childrenIndexes, i);
118 // Compute the maximum degree
119 if (numberOfChildren > treeData.degree) {
120 treeData.degree = numberOfChildren;
122 // Now we add the node (root of the given subtree).
123 myIndex = nextNodeIndex;
125 treeData.nodes[myIndex] = subtree;
126 // Record how many children I have
127 treeData.degrees[myIndex] = numberOfChildren;
128 // Store my value in an array
129 ValueType v = subtree.getValue();
130 treeData.values[myIndex] = v;
131 // Tell the caller my index
132 siblingIndexes[siblingNumber] = myIndex;
133 // Record my children indexes
134 treeData.children[myIndex] = childrenIndexes;
138 * Reads: treeData.tree
139 * Computes: treeData.nodes, treeData.degree, treeData.degrees
140 * treeData.fathers, treeData.children, treeData.size,
142 * Converts a tree to an array of nodes, in postorder.
143 * We also compute the maximum node degree in the tree.
144 * @throws TreeAlignException
146 @SuppressWarnings("unchecked")
147 public void convert() throws TreeAlignException {
149 treeData.size = treeData.tree.countNodes();
150 // we didn't write new Tree<ValueType>[treeData.size] because
151 // java does not support generics with arrays
152 treeData.nodes = new Tree[treeData.size];
153 treeData.children = new int[treeData.size][];
154 treeData.degrees = new int[treeData.size];
155 treeData.values = (ValueType[]) new Object[treeData.size];
156 int rootIndex[] = new int[1];
157 convertTreeToArrayAux(treeData.tree, rootIndex, 0);
163 * For arrays that take at least O(|T1|*|T2|) we take care
164 * not to use too big data types.
166 private class Aligner {
170 private TreeData<ValueType1> treeData1;
175 private TreeData<ValueType2> treeData2;
178 * DF1[i][j_t] is DFL for (i,j,s,t) with s=0.
179 * See description of DFL in Aligner.computeAlignmentP1().
180 * DF1 and DF2 are the "big" arrays, ie. those that may the space
181 * complexity what it is.
183 private float[][][][] DF1;
186 * DF2[j][i_s] is DFL for (i,j,s,t) with t=0.
187 * See description of DFL in Aligner.computeAlignmentP1().
189 private float[][][][] DF2;
192 * This arrays have the same shape as respectively DF1.
193 * They are used to remember which term in the minimum won, so that
194 * we can compute the alignment.
195 * Decision1 is a case number (< 10)
196 * and Decision2 is a child index, hence the types.
198 private byte[][][][] DF1Decisions1;
199 private short[][][][] DF1Decisions2;
202 * This arrays have the same shape as respectively DF2.
203 * They are used to remember which term in the minimum won, so that
204 * we can compute the alignment.
206 private byte[][][][] DF2Decisions1;
207 private short[][][][] DF2Decisions2;
210 * Distances between subtrees.
211 * DT[i][j] is the distance between the subtree rooted at i in the first tree
212 * and the subtree rooted at j in the second tree.
214 private float[][] DT;
217 * This array has the same shape as DT, but is used to remember which
218 * case gave the minimum, so that we can later compute the alignment.
220 private byte[][] DTDecisions1;
221 private short[][] DTDecisions2;
224 * Distances between labels.
225 * DL[i][j] is the distance labelDist.f(value(T1[i]), value(T2[i])).
226 * By convention, we say that value(T1[|T1|]) = null
227 * and value(T2[|T2|]) = null
229 private float[][] DL;
232 * DET1[i] is the distance between the empty tree and T1[i]
233 * (the subtree rooted at node i in the first tree).
235 private float[] DET1;
238 * Same as DET1, but for second tree.
240 private float[] DET2;
243 * DEF1[i] is the distance between the empty forest and F1[i]
244 * (the forest of children of node i in the first tree).
246 private float[] DEF1;
249 * Same as DEF1, but for second tree.
251 private float[] DEF2;
255 * @param i node in T1
256 * @param s number of first child of i to consider
257 * @param m_i degree of i
258 * @param j node in T2
259 * @param t number of first child of j to consider
260 * @param n_j degree of j
261 * @param DFx which array to fill (DF1 or DF2)
263 private void computeAlignmentP1(int i, int s, int m_i, int j, int t, int n_j, int DFx) {
265 * DFL[pr][qr] is D(F1[i_s, i_p], F2[j_t, j_q])
266 * where p=s+pr-1 and q=t+qr-1 (ie. pr=p-s+1 and qr=q-t+1)
267 * By convention, F1[i_s, i_{s-1}] and F2[j_t, j_{t-1}] are the
269 * Said differently, DFL[pr][qr] is the distance between the forest
270 * of the pr first children of i, starting with child s
271 * (first child is s = 0), and the forest of the qr first children
272 * of j, starting with child t (first child is t = 0).
273 * This array is allocated for a fixed value of (i,j,s,t).
278 * Same shape as DFL, but to remember which term gave the min,
279 * so that we can later compute the alignment.
281 byte[][] DFLDecisions1;
282 short[][] DFLDecisions2;
284 DFL = new float[m_i-s+2][n_j-t+2];
285 DFL[0][0] = 0; // D(empty forest, empty forest) = 0
287 DFLDecisions1 = new byte[m_i-s+2][n_j-t+2];
288 DFLDecisions2 = new short[m_i-s+2][n_j-t+2];
290 // Compute indexes of i_s and j_t because we will need them
291 int i_s = m_i != 0 ? treeData1.children[i][s] : -1;
292 int j_t = n_j != 0 ? treeData2.children[j][t] : -1;
294 for (int p=s; p<m_i; p++) {
295 DFL[p-s+1][0] = DFL[p-s][0] + DET1[treeData1.children[i][p]];
298 for (int q=t; q<n_j; q++) {
299 DFL[0][q-t+1] = DFL[0][q-t] + DET2[treeData2.children[j][q]];
302 for (int p=s; p<m_i; p++) {
303 int i_p = treeData1.children[i][p];
304 for (int q=t; q<n_j; q++) {
305 int j_q = treeData2.children[j][q];
307 float min = Float.POSITIVE_INFINITY;
311 // Lemma 3 - Case: We delete the rightmost tree of T1
313 float minCandidate = DFL[p-s][q-t+1] + DET1[i_p];
314 if (minCandidate < min) {
320 // Lemma 3 - Case: We insert the rightmost tree of T2 (symmetric of previous case)
322 float minCandidate = DFL[p-s+1][q-t] + DET2[j_q];
323 if (minCandidate < min) {
329 // Lemma 3 - Case: Align rightmost trees with each other
332 DFL[p-s][q-t] + DT [i_p] [j_q];
333 if (minCandidate < min) {
339 // Lemma 3 - Case: We cut the T1 forest and match the first part
340 // with the T2 forest except the rightmost tree, and we match the second
341 // part with the T2 rightmost tree's forest of children
343 float minCandidate = Float.POSITIVE_INFINITY;
345 for (int k=s; k<p; k++) {
346 float d = DFL[k-s][q-t]
347 + DF2 [j_q] [treeData1.children[i][k]] [p-k+1] [treeData2.degrees[j_q]];
348 if (d < minCandidate) {
353 minCandidate += DL[treeData1.size][j_q];
354 if (minCandidate < min) {
361 // Lemma 3 - Case: Syemmetric of preivous case
363 float minCandidate = Float.POSITIVE_INFINITY;
365 for (int k=t; k<q; k++) {
366 float d = DFL[p-s][k-t]
367 + DF1 [i_p] [treeData2.children[j][k]] [treeData1.degrees[i_p]] [q-k+1];
368 if (d < minCandidate) {
373 minCandidate += DL[i_p][treeData2.size];
374 if (minCandidate < min) {
381 DFL[p-s+1][q-t+1] = min;
382 DFLDecisions1[p-s+1][q-t+1] = (byte) decision1;
383 DFLDecisions2[p-s+1][q-t+1] = (short) decision2;
387 // Copy references to DFL to persistent arrays
390 DF2Decisions1[j][i_s] = DFLDecisions1;
391 DF2Decisions2[j][i_s] = DFLDecisions2;
394 DF1Decisions1[i][j_t] = DFLDecisions1;
395 DF1Decisions2[i][j_t] = DFLDecisions2;
400 public float align() throws TreeAlignException {
401 (new ConvertTreeToArray<ValueType1>(treeData1)).convert();
402 (new ConvertTreeToArray<ValueType2>(treeData2)).convert();
404 // Allocate necessary arrays
405 DT = new float[treeData1.size][treeData2.size];
406 DTDecisions1 = new byte[treeData1.size][treeData2.size];
407 DTDecisions2 = new short[treeData1.size][treeData2.size];
408 DL = new float[treeData1.size+1][treeData2.size+1];
409 DET1 = new float[treeData1.size];
410 DET2 = new float[treeData2.size];
411 DEF1 = new float[treeData1.size];
412 DEF2 = new float[treeData2.size];
413 DF1 = new float[treeData1.size][treeData2.size][][];
414 DF1Decisions1 = new byte[treeData1.size][treeData2.size][][];
415 DF1Decisions2 = new short[treeData1.size][treeData2.size][][];
416 DF2 = new float[treeData2.size][treeData1.size][][];
417 DF2Decisions1 = new byte[treeData2.size][treeData1.size][][];
418 DF2Decisions2 = new short[treeData2.size][treeData1.size][][];
420 DL[treeData1.size][treeData2.size] = (float) labelDist.f(null, null);
422 for (int i=0; i<treeData1.size; i++) {
423 int m_i = treeData1.degrees[i];
425 for (int k=0; k<m_i; k++) {
426 DEF1[i] += DET1[treeData1.children[i][k]];
428 DL[i][treeData2.size] = (float) labelDist.f((ValueType1) treeData1.values[i], null);
429 DET1[i] = DEF1[i] + DL[i][treeData2.size];
432 for (int j=0; j<treeData2.size; j++) {
433 int n_j = treeData2.degrees[j];
435 for (int k=0; k<n_j; k++) {
436 DEF2[j] += DET2[treeData2.children[j][k]];
438 DL[treeData1.size][j] = (float) labelDist.f(null, (ValueType2) treeData2.values[j]);
439 DET2[j] = DEF2[j] + DL[treeData1.size][j];
443 for (int i=0; i<treeData1.size; i++) {
444 int m_i = treeData1.degrees[i];
445 for (int j=0; j<treeData2.size; j++) {
446 int n_j = treeData2.degrees[j];
448 // Precompute f(value(i), value(j)) and keep the result
449 // to avoid calling f on the same values several times.
450 // This is important in case the computation of f takes
452 DL[i][j] = (float) labelDist.f((ValueType1) treeData1.values[i], (ValueType2) treeData2.values[j]);
454 for (int s=0; s<m_i; s++) {
455 computeAlignmentP1(i, s, m_i, j, 0, n_j, 2);
458 for (int t=0; t<n_j; t++) {
459 computeAlignmentP1(i, 0, m_i, j, t, n_j, 1);
462 DT[i][j] = Float.POSITIVE_INFINITY;
463 // Lemma 2 - Case: Root is (blank, j)
465 float minCandidate = Float.POSITIVE_INFINITY;
467 for (int r=0; r<n_j; r++) {
468 float d = DT[i][treeData2.children[j][r]] - DET2[treeData2.children[j][r]];
469 if (d < minCandidate) {
474 minCandidate += DET2[j];
475 if (minCandidate < DT[i][j]) {
476 DT[i][j] = minCandidate;
477 DTDecisions1[i][j] = 1;
478 DTDecisions2[i][j] = (short) best_r;
481 // Lemma 2 - Case: Root is (i, blank)
483 float minCandidate = Float.POSITIVE_INFINITY;
485 for (int r=0; r<m_i; r++) {
486 float d = DT[treeData1.children[i][r]][j] - DET1[treeData1.children[i][r]];
487 if (d < minCandidate) {
492 minCandidate += DET1[i];
493 if (minCandidate < DT[i][j]) {
494 DT[i][j] = minCandidate;
495 DTDecisions1[i][j] = 2;
496 DTDecisions2[i][j] = (short) best_r;
499 // Lemma 2 - Case: Root is (i,j)
503 minCandidate = DF1 [i] [treeData2.children[j][0]] [m_i] [n_j];
506 minCandidate = DF2 [j] [treeData1.children[i][0]] [m_i] [n_j];
508 minCandidate = 0; // D(empty forest, empty forest) = 0
511 minCandidate += DL[i][j];
512 if (minCandidate < DT[i][j]) {
513 DT[i][j] = minCandidate;
514 DTDecisions1[i][j] = 3;
523 // We return the distance beetween T1[root] and T2[root].
524 return DT[treeData1.size-1][treeData2.size-1];
527 public Aligner(Tree<ValueType1> T1, Tree<ValueType2> T2) {
528 treeData1 = new TreeData<ValueType1>();
530 treeData2 = new TreeData<ValueType2>();
534 /** Align F1[i_s,i_p] with F2[j_t,j_q].
535 * If p = s-1, by convention it means F1[i_s,i_p] = empty forest.
538 private List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i, int s, int p, int j, int t, int q) {
539 if (p == s-1) { // left forest is the empty forest
540 List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
541 for (int k=t; k<=q; k++) {
542 result.add(treeInserted(treeData2.children[j][k]));
546 if (q == t-1) { // right forest is the empty forest
547 List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
548 for (int k=s; k<=p; k++) {
549 result.add(treeDeleted(treeData1.children[i][k]));
552 } else { // both forests are non-empty
556 DF1Decisions1 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
558 DF1Decisions2 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
561 DF2Decisions1 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
563 DF2Decisions2 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
565 throw (new Error("TreeAlignSymmetric bug: both s and t are non-zero"));
570 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
571 result = computeForestAlignment(i, s, p-1, j, t, q);
572 result.add(treeDeleted(treeData1.children[i][p]));
577 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
578 result = computeForestAlignment(i, s, p, j, t, q-1);
579 result.add(treeInserted(treeData2.children[j][q]));
584 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
585 result = computeForestAlignment(i, s, p-1, j, t, q-1);
586 result.add(computeTreeAlignment(treeData1.children[i][p], treeData2.children[j][q]));
591 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
592 result = computeForestAlignment(i, s, k-1, j, t, q-1);
594 int j_q = treeData2.children[j][q];
595 Tree<AlignedNode<ValueType1,ValueType2>> insertedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
596 AlignedNode<ValueType1,ValueType2> insertedNodeValue = new AlignedNode<ValueType1,ValueType2>();
597 insertedNodeValue.setLeftNode(null);
598 insertedNodeValue.setRightNode((Tree<ValueType2>) treeData2.nodes[j_q]);
599 insertedNode.setValue(insertedNodeValue);
601 insertedNode.replaceChildrenListBy(computeForestAlignment(i, k, p, j_q, 0, treeData2.degrees[j_q]-1));
603 result.add(insertedNode);
609 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
610 result = computeForestAlignment(i, s, p-1, j, t, k-1);
612 int i_p = treeData1.children[i][p];
613 Tree<AlignedNode<ValueType1,ValueType2>> deletedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
614 AlignedNode<ValueType1,ValueType2> deletedNodeValue = new AlignedNode<ValueType1,ValueType2>();
615 deletedNodeValue.setLeftNode((Tree<ValueType1>) treeData1.nodes[i_p]);
616 deletedNodeValue.setRightNode(null);
617 deletedNode.setValue(deletedNodeValue);
619 deletedNode.replaceChildrenListBy(computeForestAlignment(i_p, 0, treeData1.degrees[i_p]-1, j, k, q));
621 result.add(deletedNode);
626 throw (new Error("TreeAlign: decision1 = " + decision1));
633 * Align T1[i] with the empty tree.
634 * @return the alignment
636 private Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i) {
637 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
638 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
639 alignedNode.setLeftNode(treeData1.nodes[i]);
640 alignedNode.setRightNode(null);
641 root.setValue(alignedNode);
642 for (int r = 0; r<treeData1.degrees[i]; r++) {
643 root.getChildren().add(treeDeleted(treeData1.children[i][r]));
649 * Align the empty tree with T2[j].
650 * @return the alignment
652 private Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j) {
653 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
654 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
655 alignedNode.setLeftNode(null);
656 alignedNode.setRightNode(treeData2.nodes[j]);
657 root.setValue(alignedNode);
658 for (int r = 0; r<treeData2.degrees[j]; r++) {
659 root.getChildren().add(treeInserted(treeData2.children[j][r]));
664 private Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i, int j) {
665 switch (DTDecisions1[i][j]) {
668 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
670 // Compute the value of the node
671 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
672 alignedNode.setLeftNode(null);
673 alignedNode.setRightNode(treeData2.nodes[j]);
674 root.setValue(alignedNode);
676 // Compute the children
677 for (int r = 0; r<treeData2.degrees[j]; r++) {
678 if (r == DTDecisions2[i][j]) {
679 root.getChildren().add(computeTreeAlignment(i, treeData2.children[j][r]));
681 root.getChildren().add(treeInserted(treeData2.children[j][r]));
688 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
690 // Compute the value of the node
691 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
692 alignedNode.setLeftNode(treeData1.nodes[i]);
693 alignedNode.setRightNode(null);
694 root.setValue(alignedNode);
696 // Compute the children
697 for (int r = 0; r<treeData1.degrees[i]; r++) {
698 if (r == DTDecisions2[i][j]) {
699 root.getChildren().add(computeTreeAlignment(treeData1.children[i][r], j));
701 root.getChildren().add(treeDeleted(treeData1.children[i][r]));
708 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
710 // Compute the value of the node
711 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
712 alignedNode.setLeftNode(treeData1.nodes[i]);
713 alignedNode.setRightNode(treeData2.nodes[j]);
714 root.setValue(alignedNode);
716 // Compute the children
717 List<Tree<AlignedNode<ValueType1,ValueType2>>> children =
718 computeForestAlignment(i, 0, treeData1.degrees[i]-1, j, 0, treeData2.degrees[j]-1);
719 root.replaceChildrenListBy(children);
724 throw (new Error("TreeAlign: DTDecisions1[i][j] = " + DTDecisions1[i][j]));
728 public Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment() {
729 return computeTreeAlignment(treeData1.size-1, treeData2.size-1);
736 * Align T1 with T2, computing both the distance and the alignment.
737 * Time: O(|T1|*|T2|*(deg(T1)+deg(T2))^2)
738 * Space: O(|T1|*|T2|*(deg(T1)+deg(T2)))
739 * Average (over possible trees) time: O(|T1|*|T2|)
740 * @param T1 The first tree.
741 * @param T2 The second tree.
742 * @return The distance and the alignment.
743 * @throws TreeAlignException
745 public TreeAlignResult<ValueType1, ValueType2> align(Tree<ValueType1> T1, Tree<ValueType2> T2) throws TreeAlignException {
746 TreeAlignResult<ValueType1, ValueType2> result = new TreeAlignResult<ValueType1, ValueType2>();
747 Aligner aligner = new Aligner(T1, T2);
748 result.setDistance(aligner.align());
749 result.setAlignment(aligner.computeAlignment());
755 * Takes a alignment, and compute the distance between the two
756 * original trees. If you have called align(), the result object already
757 * contains the distance D and the alignment A. If you call
758 * distanceFromAlignment on the alignment A it will compute the distance D.
760 public float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment) {
761 Tree<ValueType1> originalT1Node;
762 Tree<ValueType2> originalT2Node;
763 originalT1Node = alignment.getValue().getLeftNode();
764 originalT2Node = alignment.getValue().getRightNode();
765 float d = (float) labelDist.f(
766 originalT1Node != null ? originalT1Node.getValue() : null,
767 originalT2Node != null ? originalT2Node.getValue() : null);
768 for (Tree<AlignedNode<ValueType1,ValueType2>> child: alignment.getChildren()) {
769 d += distanceFromAlignment(child);