Tree alignment

From Wikipedia, the free encyclopedia

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 S of sequences, a phylogenetic tree T leaf-labeled by S and an edit distance function d between sequences,

Output: A labeling of the internal vertices of T such that is minimized, where d(e) is the edit distance between the endpoints of e.