+++ /dev/null
-package fr.orsay.lri.varna.models.treealign;
-
-import java.util.*;
-
-
-/**
- * Tree alignment algorithm.
- * This class implements the tree alignment algorithm
- * for ordered trees explained in article:
- * T. Jiang, L. Wang, K. Zhang,
- * Alignment of trees - an alternative to tree edit,
- * Theoret. Comput. Sci. 143 (1995).
- * Other references:
- * - Claire Herrbach, Alain Denise and Serge Dulucq.
- * Average complexity of the Jiang-Wang-Zhang pairwise tree alignment
- * algorithm and of a RNA secondary structure alignment algorithm.
- * Theoretical Computer Science 411 (2010) 2423-2432.
- *
- * Our implementation supposes that the trees will never have more
- * than 32000 nodes and that the total distance will never require more
- * significant digits that a float (single precision) has.
- *
- * @author Raphael Champeimont
- * @param <ValueType1> The type of values on nodes in the first tree.
- * @param <ValueType2> The type of values on nodes in the second tree.
- */
-public class TreeAlign<ValueType1, ValueType2> {
-
- private class TreeData<ValueType> {
- /**
- * The tree.
- */
- public Tree<ValueType> tree;
-
- /**
- * The tree size (number of nodes).
- */
- public int size = -1;
-
- /**
- * The number of children of a node is called the node degree.
- * This variable is the maximum node degree in the tree.
- */
- public int degree = -1;
-
- /**
- * The number of children of a node is called the node degree.
- * degree[i] is the degree of node i, with i being an index in nodes.
- */
- public int[] degrees;
-
- /**
- * The trees as an array of its nodes (subtrees rooted at each node
- * in fact), in postorder.
- */
- public Tree<ValueType>[] nodes;
-
- /**
- * children[i] is the array of children (as indexes in nodes)
- * of i (an index in nodes)
- */
- public int[][] children;
-
- /**
- * Values of nodes.
- */
- public ValueType[] values;
- }
-
-
- /**
- * The distance function between labels.
- */
- private TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist;
-
-
- /**
- * Create a TreeAlignSymmetric object, which can align trees.
- * The distance function will be called only once on every pair
- * of nodes. The result is then kept in a matrix, so you need not manage
- * yourself a cache of f(value1, value2).
- * Note that it is permitted to have null values on nodes,
- * so comparing a node with a non-null value with a node with a null
- * value will give the same cost as to insert the first node.
- * This can be useful if you tree has "fake" nodes.
- * @param labelDist The label distance.
- */
- public TreeAlign(TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist) {
- this.labelDist = labelDist;
- }
-
-
-
- private class ConvertTreeToArray<ValueType> {
- private int nextNodeIndex = 0;
- private TreeData<ValueType> treeData;
-
- public ConvertTreeToArray(TreeData<ValueType> treeData) {
- this.treeData = treeData;
- }
-
- private void convertTreeToArrayAux(
- Tree<ValueType> subtree,
- int[] siblingIndexes,
- int siblingNumber) throws TreeAlignException {
- // We want it in postorder, so first we put the children
- List<Tree<ValueType>> children = subtree.getChildren();
- int numberOfChildren = children.size();
- int[] childrenIndexes = new int[numberOfChildren];
- int myIndex = -1;
- {
- int i = 0;
- for (Tree<ValueType> child: children) {
- convertTreeToArrayAux(child, childrenIndexes, i);
- i++;
- }
- }
- // Compute the maximum degree
- if (numberOfChildren > treeData.degree) {
- treeData.degree = numberOfChildren;
- }
- // Now we add the node (root of the given subtree).
- myIndex = nextNodeIndex;
- nextNodeIndex++;
- treeData.nodes[myIndex] = subtree;
- // Record how many children I have
- treeData.degrees[myIndex] = numberOfChildren;
- // Store my value in an array
- ValueType v = subtree.getValue();
- treeData.values[myIndex] = v;
- // Tell the caller my index
- siblingIndexes[siblingNumber] = myIndex;
- // Record my children indexes
- treeData.children[myIndex] = childrenIndexes;
- }
-
- /**
- * Reads: treeData.tree
- * Computes: treeData.nodes, treeData.degree, treeData.degrees
- * treeData.fathers, treeData.children, treeData.size,
- * treeData.values
- * Converts a tree to an array of nodes, in postorder.
- * We also compute the maximum node degree in the tree.
- * @throws TreeAlignException
- */
- @SuppressWarnings("unchecked")
- public void convert() throws TreeAlignException {
- treeData.degree = 0;
- treeData.size = treeData.tree.countNodes();
- // we didn't write new Tree<ValueType>[treeData.size] because
- // java does not support generics with arrays
- treeData.nodes = new Tree[treeData.size];
- treeData.children = new int[treeData.size][];
- treeData.degrees = new int[treeData.size];
- treeData.values = (ValueType[]) new Object[treeData.size];
- int rootIndex[] = new int[1];
- convertTreeToArrayAux(treeData.tree, rootIndex, 0);
- }
- }
-
-
- /**
- * For arrays that take at least O(|T1|*|T2|) we take care
- * not to use too big data types.
- */
- private class Aligner {
- /**
- * The first tree.
- */
- private TreeData<ValueType1> treeData1;
-
- /**
- * The second tree.
- */
- private TreeData<ValueType2> treeData2;
-
- /**
- * DF1[i][j_t] is DFL for (i,j,s,t) with s=0.
- * See description of DFL in Aligner.computeAlignmentP1().
- * DF1 and DF2 are the "big" arrays, ie. those that may the space
- * complexity what it is.
- */
- private float[][][][] DF1;
-
- /**
- * DF2[j][i_s] is DFL for (i,j,s,t) with t=0.
- * See description of DFL in Aligner.computeAlignmentP1().
- */
- private float[][][][] DF2;
-
- /**
- * This arrays have the same shape as respectively DF1.
- * They are used to remember which term in the minimum won, so that
- * we can compute the alignment.
- * Decision1 is a case number (< 10)
- * and Decision2 is a child index, hence the types.
- */
- private byte[][][][] DF1Decisions1;
- private short[][][][] DF1Decisions2;
-
- /**
- * This arrays have the same shape as respectively DF2.
- * They are used to remember which term in the minimum won, so that
- * we can compute the alignment.
- */
- private byte[][][][] DF2Decisions1;
- private short[][][][] DF2Decisions2;
-
- /**
- * Distances between subtrees.
- * DT[i][j] is the distance between the subtree rooted at i in the first tree
- * and the subtree rooted at j in the second tree.
- */
- private float[][] DT;
-
- /**
- * This array has the same shape as DT, but is used to remember which
- * case gave the minimum, so that we can later compute the alignment.
- */
- private byte[][] DTDecisions1;
- private short[][] DTDecisions2;
-
- /**
- * Distances between labels.
- * DL[i][j] is the distance labelDist.f(value(T1[i]), value(T2[i])).
- * By convention, we say that value(T1[|T1|]) = null
- * and value(T2[|T2|]) = null
- */
- private float[][] DL;
-
- /**
- * DET1[i] is the distance between the empty tree and T1[i]
- * (the subtree rooted at node i in the first tree).
- */
- private float[] DET1;
-
- /**
- * Same as DET1, but for second tree.
- */
- private float[] DET2;
-
- /**
- * DEF1[i] is the distance between the empty forest and F1[i]
- * (the forest of children of node i in the first tree).
- */
- private float[] DEF1;
-
- /**
- * Same as DEF1, but for second tree.
- */
- private float[] DEF2;
-
-
- /**
- * @param i node in T1
- * @param s number of first child of i to consider
- * @param m_i degree of i
- * @param j node in T2
- * @param t number of first child of j to consider
- * @param n_j degree of j
- * @param DFx which array to fill (DF1 or DF2)
- */
- private void computeAlignmentP1(int i, int s, int m_i, int j, int t, int n_j, int DFx) {
- /**
- * DFL[pr][qr] is D(F1[i_s, i_p], F2[j_t, j_q])
- * where p=s+pr-1 and q=t+qr-1 (ie. pr=p-s+1 and qr=q-t+1)
- * By convention, F1[i_s, i_{s-1}] and F2[j_t, j_{t-1}] are the
- * empty forests.
- * Said differently, DFL[pr][qr] is the distance between the forest
- * of the pr first children of i, starting with child s
- * (first child is s = 0), and the forest of the qr first children
- * of j, starting with child t (first child is t = 0).
- * This array is allocated for a fixed value of (i,j,s,t).
- */
- float[][] DFL;
-
- /**
- * Same shape as DFL, but to remember which term gave the min,
- * so that we can later compute the alignment.
- */
- byte[][] DFLDecisions1;
- short[][] DFLDecisions2;
-
- DFL = new float[m_i-s+2][n_j-t+2];
- DFL[0][0] = 0; // D(empty forest, empty forest) = 0
-
- DFLDecisions1 = new byte[m_i-s+2][n_j-t+2];
- DFLDecisions2 = new short[m_i-s+2][n_j-t+2];
-
- // Compute indexes of i_s and j_t because we will need them
- int i_s = m_i != 0 ? treeData1.children[i][s] : -1;
- int j_t = n_j != 0 ? treeData2.children[j][t] : -1;
-
- for (int p=s; p<m_i; p++) {
- DFL[p-s+1][0] = DFL[p-s][0] + DET1[treeData1.children[i][p]];
- }
-
- for (int q=t; q<n_j; q++) {
- DFL[0][q-t+1] = DFL[0][q-t] + DET2[treeData2.children[j][q]];
- }
-
- for (int p=s; p<m_i; p++) {
- int i_p = treeData1.children[i][p];
- for (int q=t; q<n_j; q++) {
- int j_q = treeData2.children[j][q];
-
- float min = Float.POSITIVE_INFINITY;
- int decision1 = -1;
- int decision2 = -1;
-
- // Lemma 3 - Case: We delete the rightmost tree of T1
- {
- float minCandidate = DFL[p-s][q-t+1] + DET1[i_p];
- if (minCandidate < min) {
- min = minCandidate;
- decision1 = 1;
- }
- }
-
- // Lemma 3 - Case: We insert the rightmost tree of T2 (symmetric of previous case)
- {
- float minCandidate = DFL[p-s+1][q-t] + DET2[j_q];
- if (minCandidate < min) {
- min = minCandidate;
- decision1 = 2;
- }
- }
-
- // Lemma 3 - Case: Align rightmost trees with each other
- {
- float minCandidate =
- DFL[p-s][q-t] + DT [i_p] [j_q];
- if (minCandidate < min) {
- min = minCandidate;
- decision1 = 3;
- }
- }
-
- // Lemma 3 - Case: We cut the T1 forest and match the first part
- // with the T2 forest except the rightmost tree, and we match the second
- // part with the T2 rightmost tree's forest of children
- {
- float minCandidate = Float.POSITIVE_INFINITY;
- int best_k = -1;
- for (int k=s; k<p; k++) {
- float d = DFL[k-s][q-t]
- + DF2 [j_q] [treeData1.children[i][k]] [p-k+1] [treeData2.degrees[j_q]];
- if (d < minCandidate) {
- minCandidate = d;
- best_k = k;
- }
- }
- minCandidate += DL[treeData1.size][j_q];
- if (minCandidate < min) {
- min = minCandidate;
- decision1 = 4;
- decision2 = best_k;
- }
- }
-
- // Lemma 3 - Case: Syemmetric of preivous case
- {
- float minCandidate = Float.POSITIVE_INFINITY;
- int best_k = -1;
- for (int k=t; k<q; k++) {
- float d = DFL[p-s][k-t]
- + DF1 [i_p] [treeData2.children[j][k]] [treeData1.degrees[i_p]] [q-k+1];
- if (d < minCandidate) {
- minCandidate = d;
- best_k = k;
- }
- }
- minCandidate += DL[i_p][treeData2.size];
- if (minCandidate < min) {
- min = minCandidate;
- decision1 = 5;
- decision2 = best_k;
- }
- }
-
- DFL[p-s+1][q-t+1] = min;
- DFLDecisions1[p-s+1][q-t+1] = (byte) decision1;
- DFLDecisions2[p-s+1][q-t+1] = (short) decision2;
- }
- }
-
- // Copy references to DFL to persistent arrays
- if (DFx == 2) {
- DF2[j][i_s] = DFL;
- DF2Decisions1[j][i_s] = DFLDecisions1;
- DF2Decisions2[j][i_s] = DFLDecisions2;
- } else {
- DF1[i][j_t] = DFL;
- DF1Decisions1[i][j_t] = DFLDecisions1;
- DF1Decisions2[i][j_t] = DFLDecisions2;
- }
-
- }
-
- public float align() throws TreeAlignException {
- (new ConvertTreeToArray<ValueType1>(treeData1)).convert();
- (new ConvertTreeToArray<ValueType2>(treeData2)).convert();
-
- // Allocate necessary arrays
- DT = new float[treeData1.size][treeData2.size];
- DTDecisions1 = new byte[treeData1.size][treeData2.size];
- DTDecisions2 = new short[treeData1.size][treeData2.size];
- DL = new float[treeData1.size+1][treeData2.size+1];
- DET1 = new float[treeData1.size];
- DET2 = new float[treeData2.size];
- DEF1 = new float[treeData1.size];
- DEF2 = new float[treeData2.size];
- DF1 = new float[treeData1.size][treeData2.size][][];
- DF1Decisions1 = new byte[treeData1.size][treeData2.size][][];
- DF1Decisions2 = new short[treeData1.size][treeData2.size][][];
- DF2 = new float[treeData2.size][treeData1.size][][];
- DF2Decisions1 = new byte[treeData2.size][treeData1.size][][];
- DF2Decisions2 = new short[treeData2.size][treeData1.size][][];
-
- DL[treeData1.size][treeData2.size] = (float) labelDist.f(null, null);
-
- for (int i=0; i<treeData1.size; i++) {
- int m_i = treeData1.degrees[i];
- DEF1[i] = 0;
- for (int k=0; k<m_i; k++) {
- DEF1[i] += DET1[treeData1.children[i][k]];
- }
- DL[i][treeData2.size] = (float) labelDist.f((ValueType1) treeData1.values[i], null);
- DET1[i] = DEF1[i] + DL[i][treeData2.size];
- }
-
- for (int j=0; j<treeData2.size; j++) {
- int n_j = treeData2.degrees[j];
- DEF2[j] = 0;
- for (int k=0; k<n_j; k++) {
- DEF2[j] += DET2[treeData2.children[j][k]];
- }
- DL[treeData1.size][j] = (float) labelDist.f(null, (ValueType2) treeData2.values[j]);
- DET2[j] = DEF2[j] + DL[treeData1.size][j];
- }
-
-
- for (int i=0; i<treeData1.size; i++) {
- int m_i = treeData1.degrees[i];
- for (int j=0; j<treeData2.size; j++) {
- int n_j = treeData2.degrees[j];
-
- // Precompute f(value(i), value(j)) and keep the result
- // to avoid calling f on the same values several times.
- // This is important in case the computation of f takes
- // long.
- DL[i][j] = (float) labelDist.f((ValueType1) treeData1.values[i], (ValueType2) treeData2.values[j]);
-
- for (int s=0; s<m_i; s++) {
- computeAlignmentP1(i, s, m_i, j, 0, n_j, 2);
- }
-
- for (int t=0; t<n_j; t++) {
- computeAlignmentP1(i, 0, m_i, j, t, n_j, 1);
- }
-
- DT[i][j] = Float.POSITIVE_INFINITY;
- // Lemma 2 - Case: Root is (blank, j)
- {
- float minCandidate = Float.POSITIVE_INFINITY;
- int best_r = -1;
- for (int r=0; r<n_j; r++) {
- float d = DT[i][treeData2.children[j][r]] - DET2[treeData2.children[j][r]];
- if (d < minCandidate) {
- minCandidate = d;
- best_r = r;
- }
- }
- minCandidate += DET2[j];
- if (minCandidate < DT[i][j]) {
- DT[i][j] = minCandidate;
- DTDecisions1[i][j] = 1;
- DTDecisions2[i][j] = (short) best_r;
- }
- }
- // Lemma 2 - Case: Root is (i, blank)
- {
- float minCandidate = Float.POSITIVE_INFINITY;
- int best_r = -1;
- for (int r=0; r<m_i; r++) {
- float d = DT[treeData1.children[i][r]][j] - DET1[treeData1.children[i][r]];
- if (d < minCandidate) {
- minCandidate = d;
- best_r = r;
- }
- }
- minCandidate += DET1[i];
- if (minCandidate < DT[i][j]) {
- DT[i][j] = minCandidate;
- DTDecisions1[i][j] = 2;
- DTDecisions2[i][j] = (short) best_r;
- }
- }
- // Lemma 2 - Case: Root is (i,j)
- {
- float minCandidate;
- if (n_j != 0) {
- minCandidate = DF1 [i] [treeData2.children[j][0]] [m_i] [n_j];
- } else {
- if (m_i != 0) {
- minCandidate = DF2 [j] [treeData1.children[i][0]] [m_i] [n_j];
- } else {
- minCandidate = 0; // D(empty forest, empty forest) = 0
- }
- }
- minCandidate += DL[i][j];
- if (minCandidate < DT[i][j]) {
- DT[i][j] = minCandidate;
- DTDecisions1[i][j] = 3;
- }
- }
-
-
- }
- }
-
-
- // We return the distance beetween T1[root] and T2[root].
- return DT[treeData1.size-1][treeData2.size-1];
- }
-
- public Aligner(Tree<ValueType1> T1, Tree<ValueType2> T2) {
- treeData1 = new TreeData<ValueType1>();
- treeData1.tree = T1;
- treeData2 = new TreeData<ValueType2>();
- treeData2.tree = T2;
- }
-
- /** Align F1[i_s,i_p] with F2[j_t,j_q].
- * If p = s-1, by convention it means F1[i_s,i_p] = empty forest.
- * Idem for q=t-1.
- */
- private List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i, int s, int p, int j, int t, int q) {
- if (p == s-1) { // left forest is the empty forest
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
- for (int k=t; k<=q; k++) {
- result.add(treeInserted(treeData2.children[j][k]));
- }
- return result;
- } else {
- if (q == t-1) { // right forest is the empty forest
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
- for (int k=s; k<=p; k++) {
- result.add(treeDeleted(treeData1.children[i][k]));
- }
- return result;
- } else { // both forests are non-empty
- int decision1, k;
- if (s == 0) {
- decision1 =
- DF1Decisions1 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
- k =
- DF1Decisions2 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
- } else if (t == 0) {
- decision1 =
- DF2Decisions1 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
- k =
- DF2Decisions2 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
- } else {
- throw (new Error("TreeAlignSymmetric bug: both s and t are non-zero"));
- }
- switch (decision1) {
- case 1:
- {
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
- result = computeForestAlignment(i, s, p-1, j, t, q);
- result.add(treeDeleted(treeData1.children[i][p]));
- return result;
- }
- case 2:
- {
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
- result = computeForestAlignment(i, s, p, j, t, q-1);
- result.add(treeInserted(treeData2.children[j][q]));
- return result;
- }
- case 3:
- {
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
- result = computeForestAlignment(i, s, p-1, j, t, q-1);
- result.add(computeTreeAlignment(treeData1.children[i][p], treeData2.children[j][q]));
- return result;
- }
- case 4:
- {
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
- result = computeForestAlignment(i, s, k-1, j, t, q-1);
-
- int j_q = treeData2.children[j][q];
- Tree<AlignedNode<ValueType1,ValueType2>> insertedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
- AlignedNode<ValueType1,ValueType2> insertedNodeValue = new AlignedNode<ValueType1,ValueType2>();
- insertedNodeValue.setLeftNode(null);
- insertedNodeValue.setRightNode((Tree<ValueType2>) treeData2.nodes[j_q]);
- insertedNode.setValue(insertedNodeValue);
-
- insertedNode.replaceChildrenListBy(computeForestAlignment(i, k, p, j_q, 0, treeData2.degrees[j_q]-1));
-
- result.add(insertedNode);
-
- return result;
- }
- case 5:
- {
- List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
- result = computeForestAlignment(i, s, p-1, j, t, k-1);
-
- int i_p = treeData1.children[i][p];
- Tree<AlignedNode<ValueType1,ValueType2>> deletedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
- AlignedNode<ValueType1,ValueType2> deletedNodeValue = new AlignedNode<ValueType1,ValueType2>();
- deletedNodeValue.setLeftNode((Tree<ValueType1>) treeData1.nodes[i_p]);
- deletedNodeValue.setRightNode(null);
- deletedNode.setValue(deletedNodeValue);
-
- deletedNode.replaceChildrenListBy(computeForestAlignment(i_p, 0, treeData1.degrees[i_p]-1, j, k, q));
-
- result.add(deletedNode);
-
- return result;
- }
- default:
- throw (new Error("TreeAlign: decision1 = " + decision1));
- }
- }
- }
- }
-
- /**
- * Align T1[i] with the empty tree.
- * @return the alignment
- */
- private Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i) {
- Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
- AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
- alignedNode.setLeftNode(treeData1.nodes[i]);
- alignedNode.setRightNode(null);
- root.setValue(alignedNode);
- for (int r = 0; r<treeData1.degrees[i]; r++) {
- root.getChildren().add(treeDeleted(treeData1.children[i][r]));
- }
- return root;
- }
-
- /**
- * Align the empty tree with T2[j].
- * @return the alignment
- */
- private Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j) {
- Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
- AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
- alignedNode.setLeftNode(null);
- alignedNode.setRightNode(treeData2.nodes[j]);
- root.setValue(alignedNode);
- for (int r = 0; r<treeData2.degrees[j]; r++) {
- root.getChildren().add(treeInserted(treeData2.children[j][r]));
- }
- return root;
- }
-
- private Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i, int j) {
- switch (DTDecisions1[i][j]) {
- case 1:
- {
- Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
-
- // Compute the value of the node
- AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
- alignedNode.setLeftNode(null);
- alignedNode.setRightNode(treeData2.nodes[j]);
- root.setValue(alignedNode);
-
- // Compute the children
- for (int r = 0; r<treeData2.degrees[j]; r++) {
- if (r == DTDecisions2[i][j]) {
- root.getChildren().add(computeTreeAlignment(i, treeData2.children[j][r]));
- } else {
- root.getChildren().add(treeInserted(treeData2.children[j][r]));
- }
- }
- return root;
- }
- case 2:
- {
- Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
-
- // Compute the value of the node
- AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
- alignedNode.setLeftNode(treeData1.nodes[i]);
- alignedNode.setRightNode(null);
- root.setValue(alignedNode);
-
- // Compute the children
- for (int r = 0; r<treeData1.degrees[i]; r++) {
- if (r == DTDecisions2[i][j]) {
- root.getChildren().add(computeTreeAlignment(treeData1.children[i][r], j));
- } else {
- root.getChildren().add(treeDeleted(treeData1.children[i][r]));
- }
- }
- return root;
- }
- case 3:
- {
- Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
-
- // Compute the value of the node
- AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
- alignedNode.setLeftNode(treeData1.nodes[i]);
- alignedNode.setRightNode(treeData2.nodes[j]);
- root.setValue(alignedNode);
-
- // Compute the children
- List<Tree<AlignedNode<ValueType1,ValueType2>>> children =
- computeForestAlignment(i, 0, treeData1.degrees[i]-1, j, 0, treeData2.degrees[j]-1);
- root.replaceChildrenListBy(children);
-
- return root;
- }
- default:
- throw (new Error("TreeAlign: DTDecisions1[i][j] = " + DTDecisions1[i][j]));
- }
- }
-
- public Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment() {
- return computeTreeAlignment(treeData1.size-1, treeData2.size-1);
- }
-
- }
-
-
- /**
- * Align T1 with T2, computing both the distance and the alignment.
- * Time: O(|T1|*|T2|*(deg(T1)+deg(T2))^2)
- * Space: O(|T1|*|T2|*(deg(T1)+deg(T2)))
- * Average (over possible trees) time: O(|T1|*|T2|)
- * @param T1 The first tree.
- * @param T2 The second tree.
- * @return The distance and the alignment.
- * @throws TreeAlignException
- */
- public TreeAlignResult<ValueType1, ValueType2> align(Tree<ValueType1> T1, Tree<ValueType2> T2) throws TreeAlignException {
- TreeAlignResult<ValueType1, ValueType2> result = new TreeAlignResult<ValueType1, ValueType2>();
- Aligner aligner = new Aligner(T1, T2);
- result.setDistance(aligner.align());
- result.setAlignment(aligner.computeAlignment());
- return result;
- }
-
-
- /**
- * Takes a alignment, and compute the distance between the two
- * original trees. If you have called align(), the result object already
- * contains the distance D and the alignment A. If you call
- * distanceFromAlignment on the alignment A it will compute the distance D.
- */
- public float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment) {
- Tree<ValueType1> originalT1Node;
- Tree<ValueType2> originalT2Node;
- originalT1Node = alignment.getValue().getLeftNode();
- originalT2Node = alignment.getValue().getRightNode();
- float d = (float) labelDist.f(
- originalT1Node != null ? originalT1Node.getValue() : null,
- originalT2Node != null ? originalT2Node.getValue() : null);
- for (Tree<AlignedNode<ValueType1,ValueType2>> child: alignment.getChildren()) {
- d += distanceFromAlignment(child);
- }
- return d;
- }
-
-
-}
git://source.jalview.org / jalview.git / blobdiff