In computational phylogenetics, tree alignment is the problem of producing a multiple sequence alignment on a set of sequences over a fixed tree.
Formally, tree alignment is the following optimization problem.
Input: A set of sequences, a phylogenetic tree leaf-labeled by and an edit distance function between sequences,
Output: A labeling of the internal vertices of such that is minimized, where is the edit distance between the endpoints of .
The task is NP-hard
Read more about Tree Alignment: See Also
Famous quotes containing the word tree:
“What signify a few lives lost in a century or two? The tree of liberty must be refreshed from time to time with the blood of patriots and tyrants. It is its natural manure.”
—Thomas Jefferson (1743–1826)