Tree Alignment with a Given Phylogeny

• INSTANCE: Finite set of strings $S\subset\Sigma^*$ over a given finite alphabet, arborescence $T$ , bijection $\lambda\colon S\to L(T)$ between $S$ and the set $L(T)$ of leaves of $T$ , scoring scheme $\mu\colon (\Sigma\cup\{-\})^2\to {\mathbb{R}}$

• SOLUTION: An assignment $a\colon V(T)\setminus L(T)\to (\Sigma\cup\{-\})^*$ such that for each internal node $u$ of $T$ , $a(u)$ is an alignment of the strings $a(v)$ assigned to all the children $v$ of $u$ in $T$

• COST FUNCTION: ${\displaystyle\sum_{e = {u,v} \in E_T}}\mu (a(u),a(v))$

• OBJECTIVE: Minimize.

• Approx.: Admits a PTAS when the cost function given by the scoring scheme $\mu$ 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 $t > 1$ , has a performance ratio $1 + 3/t$ [104].