- INSTANCE:
Finite set of strings
over a given finite alphabet,
arborescence
, bijection
between
and the set
of leaves of
,
scoring scheme
- SOLUTION:
An assignment
such that for each internal node
of
,
is an alignment of the strings
assigned to all the children
of
in
- COST FUNCTION:
- OBJECTIVE:
Minimize.
*Approx.:*Admits a PTAS when the cost function given by the scoring scheme is a metric [104].*Hardness:*NP-hard. In the case of general scoring schemes, the problem becomes APX-hard [104].*Comment:*Augmenting the construction with a local optimization technique, for each , has a performance ratio [104].

2015-04-27 Revision: 288 PDF version