Next:
MS4 MINIMUM ATTRACTION
Up:
Miscellaneous
Previous:
MS2 NEAREST CODEWORD
-
I
NSTANCE
:
Set
S
of sequences over an alphabet
, a score scheme
satisfying the triangle inequality, and a tree
T
of bounded degree
whose leafs are labeled with the sequences
S
.
-
S
OLUTION
:
A sequence labeling of the interior nodes of the tree
T
.
-
M
EASURE
:
The total alignment cost of the labeled tree, i.e., the sum over all
edges
(x,y)
in the tree of the edit distance
d(x,y)
between the
labels of the endpoints of the edge. The edit distance is the minimum
alignment cost
over all possible alignments
x'
and
y'
of
x
and
y
. An alignment is obtained by inserting
spaces (denoted by
) into the original sequence, either between
two characters or in the beginning or at the end.
x'
and
y'
must have
the same length.
-
Good News:
Admits a PTAS [
190
].
-
Comment:
Variation in which the tree is not given as an input and the objective
is to find the tree with the minimum total alignment cost is called
Minimum Generalized Tree Alignment
or
Minimum Evolutionary Tree
and is A
PX
-hard [
190
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997