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.^[1]

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 $\Sigma _{e\in T}d(e)$ is minimized, where $d(e)$ is the edit distance between the endpoints of $e$ .^[2]

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

References

^ Schwikowski, Benno; Vingron, Martin (1997). "The Deferred Path Heuristic for the Generalized Tree Alignment Problem". Journal of Computational Biology. 4 (3): 415–431. doi:10.1089/cmb.1997.4.415. ISSN 1066-5277. PMID 9278068.
^ Srinivas Aluru (21 December 2005). Handbook of Computational Molecular Biology. CRC Press. pp. 19–26. ISBN 978-1-4200-3627-5.

[SchwikowskiVingron1997-1] Schwikowski, Benno; Vingron, Martin (1997). "The Deferred Path Heuristic for the Generalized Tree Alignment Problem". Journal of Computational Biology. 4 (3): 415–431. doi:10.1089/cmb.1997.4.415. ISSN 1066-5277. PMID 9278068.

[Aluru2005-2] Srinivas Aluru (21 December 2005). Handbook of Computational Molecular Biology. CRC Press. pp. 19–26. ISBN 978-1-4200-3627-5.

[1]

[2]