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 [math]\displaystyle{ S }[/math] and an edit distance function [math]\displaystyle{ d }[/math] between sequences,
Output: A tree [math]\displaystyle{ T }[/math] leaf-labeled by [math]\displaystyle{ S }[/math] and labeled with sequences at the internal nodes, such that [math]\displaystyle{ \Sigma_{e \in T} d(e) }[/math] is minimized, where [math]\displaystyle{ d(e) }[/math] is the edit distance between the endpoints of [math]\displaystyle{ e }[/math].[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. https://books.google.com/books?id=3Ss-ws2Zm6IC&pg=SA19-PA27.
 |  |
