The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem.

Suppose that we are given a set of species $S$ and a symmetric function $\delta : S \times S \rightarrow \mathbb{R}^+$ such that $\delta(i,j)$ is an estimate of the evolutionary distance between species $i$ and $j$. The 'tree fitting' problem consists of finding a weighted tree $\hat{T}$ leaf-labeled by $S$, such that the induced metric $d_{\hat{T}}$ is a good estimation of $\delta$. Here $d_{\hat{T}}(i,j)$ is defined as the length of the unique path of $\hat{T}$ joining $i$ and $j$. If $T$ is unweighted, we denote by $p_T(i,j)$ the number of edges of this path.

Now, given an unweighted tree $T$ and a matrix $\delta$, we may then define the following quantity:

$L_T(\delta) = \sum_{\{i,j\} \subseteq X} 2^{1-p_T(i,j)} \delta(i,j)$

It is known that $L_T(\delta)$ computes the total length $l(\hat{T})$ of a weighted tree $\hat{T}$ with topology $T$ that best fits $\delta$ (in some precise sense that I won't explain). In particular, when $\delta$ is obtained from some weighted tree $\hat{U}$, we have the property that $L_U(\delta) = l(\hat{U})$ and that $L_T(\delta) \geq l(\hat{U})$ for every $T \neq U$. That is to say, in that case the 'right tree' can be obtained by a parsimony principle.

The BME problem consists, given the function $\delta$, to recover an unweighted tree $T$ minimizing $L_T(\delta)$. By the above remark, the problem is easy when $\delta$ is a tree metric, whereas it is $\sf{NP}$-hard for arbitrary metrics (and probably even for $\ell_p$ metrics of small dimension, although I don't have a formal proof of this fact). Mainly for theoretical reasons, I am looking for other classes of metrics for which the problem is polynomial. An analogy with the TSP problem suggests that circular metrics are possible candidates, as they're known to be among the few tractable cases for TSP.

Thus, to the experts in the field I'd like to ask if (1) they have literature to recommend about circular metrics, (2) they have suggestions of other candidate metrics that are known to be tractable for TSP.

  • $\begingroup$ Bounded dimensional normed spaces, and more generally metrics with bounded doubling dimension, admit a PTAS for TSP. I don't know if that helps you. $\endgroup$ Apr 6 '14 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.