Tree alignment

In computational tree alignment is the problem of producing a multiple sequence alignment and on a set of sequences over a fixed tree.

Formally, tree alignment is the following optimization problem.

Input: A set $S$, a tree $T$ leaf-labeled by $S$ and an edit distance function $d$ between sequences,

Output: A labeling of the internal vertices of $T$ such that $\Sigma _{e\in T}d(e)$ is minimized, where $d(e)$ is the edit distance between the endpoints of $e$.

Note that this is in contrast to tree alignment, where the tree is provided as input.