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:
“Every tree sends its fibres forth in search of the Wild. The cities import it at any price. Men plow and sail for it. From the forest and wilderness come the tonics and barks which brace mankind.”
—Henry David Thoreau (1817–1862)