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:
“Like to the tree of Tantalus she fled,
And seeming lavish, sav’de her maydenhead.
Ne’re king more sought to keepe his diademe;
Than Hero this inestimable gemme.”
—Christopher Marlowe (1564–1593)