ParaTree: Parametric alignment of trees

Similar to sequence alignment, there is often disagreement on how to weight match, mismatch, indel and gap of tree alignment. Parametric alignment attempts to avoid the problem of choosing fixed parameter settings by computing the optimal alignment as a function of variable parameters for weights and penalties. The goal is to partition the parameter space into regions such that in each region one alignment is optimal. ParaTree is a parametric tool for aligning two ordered trees. There are two versoins depending on whether gap penalty is considered.

  • no gap penalty: in this case, the default value for match is set to be 1. User has to provide ranges for mismatch and indel as well as the two ordered trees.
  • gap penalty: the default values for match and indel are set to be 1 and 0.5, respectively. User can reset the values for match and indel. The ranges of mismatch and gap penalty must be provided, too.

After starting ParaTree, windows will pop up to direct the user to input trees and set parameters. ParaTree generates a graphical output of the final polygonal decomposition. If you click on a point in the polygonal decomposition, ParaTree can compute and output an optimal alignment based on the setting of this point.

Click here to start ParaTree

Click here to download the related paper

Another software: SEGID