fr.orsay.lri.varna.models.treealign
Class TreeAlign<ValueType1,ValueType2>

java.lang.Object
  extended by fr.orsay.lri.varna.models.treealign.TreeAlign<ValueType1,ValueType2>
Type Parameters:
ValueType1 - The type of values on nodes in the first tree.
ValueType2 - The type of values on nodes in the second tree.

public class TreeAlign<ValueType1,ValueType2>
extends Object

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

Nested Class Summary
private  class TreeAlign.Aligner
          For arrays that take at least O(|T1|*|T2|) we take care not to use too big data types.
private  class TreeAlign.ConvertTreeToArray<ValueType>
           
private  class TreeAlign.TreeData<ValueType>
           
 
Field Summary
private  TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist
          The distance function between labels.
 
Constructor Summary
TreeAlign(TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist)
          Create a TreeAlignSymmetric object, which can align trees.
 
Method Summary
 TreeAlignResult<ValueType1,ValueType2> align(Tree<ValueType1> T1, Tree<ValueType2> T2)
          Align T1 with T2, computing both the distance and the alignment.
 float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment)
          Takes a alignment, and compute the distance between the two original trees.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

labelDist

private TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist
The distance function between labels.

Constructor Detail

TreeAlign

public TreeAlign(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.

Parameters:
labelDist - The label distance.
Method Detail

align

public TreeAlignResult<ValueType1,ValueType2> align(Tree<ValueType1> T1,
                                                    Tree<ValueType2> T2)
                                             throws TreeAlignException
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|)

Parameters:
T1 - The first tree.
T2 - The second tree.
Returns:
The distance and the alignment.
Throws:
TreeAlignException

distanceFromAlignment

public float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment)
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.