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:
“The wind had seized the tree and ha, and ha,
It held the shivering, the shaken limbs,
Then bathed its body in the leaping lake.”
—Wallace Stevens (1879–1955)