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:
“A tree there is that from its topmost bough
Is half all glittering flame and half all green
Abounding foliage moistened with the dew;
And half is half and yet is all the scene;
And half and half consume what they renew....”
—William Butler Yeats (1865–1939)