Generalized tree alignment

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.

This bioinformatics-related article is a stub. You can help Wikipedia by expanding it.

[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]