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.{{Cite journal |last=Schwikowski |first=Benno |last2=Vingron |first2=Martin |year=1997 |title=The Deferred Path Heuristic for the Generalized Tree Alignment Problem |journal=Journal of Computational Biology |volume=4 |issue=3 |pages=415–431 |doi=10.1089/cmb.1997.4.415 |issn=1066-5277 |pmid=9278068}}

Formally, Generalized tree alignment is the following optimization problem.

Input: A set $S$ and an edit distance function $d$ between sequences,

Output: A tree $T$ leaf-labeled by $S$ and labeled with sequences at the internal nodes, such that $\backslash Sigma\_\{e\; \backslash in\; T\}\; d(e)$ is minimized, where $d(e)$ is the edit distance between the endpoints of $e$.{{Cite book |last=Srinivas Aluru |author-link=Srinivas Aluru |url=https://books.google.com/books?id=3Ss-ws2Zm6IC&pg=SA19-PA27 |title=Handbook of Computational Molecular Biology |date=21 December 2005 |publisher=CRC Press |isbn=978-1-4200-3627-5 |pages=19–26}}

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