Generalized tree alignment

In computational phylogenetics, generalized tree alignment is the problem of producing a multiple sequence alignment and a phylogenetic tree on a set of sequences simultaneously, as opposed to separately.

Formally, Generalized tree alignment is the following optimization problem.

Input: A set ${\displaystyle S}$and an edit distance function ${\displaystyle d}$between sequences,

Output: A tree ${\displaystyle T}$leaf-labeled by ${\displaystyle S}$and labeled with sequences at the internal nodes, such that ${\displaystyle \Sigma _{e\in T}d(e)}$is minimized, where ${\displaystyle d(e)}$is the edit distance between the endpoints of ${\displaystyle e}$.

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