blog/2019/05/10/constructing-trees-from-a-distance-matrix

[giscus[bot]]

blog/2019/05/10/constructing-trees-from-a-distance-matrix

NP-Incompleteness:

https://www.kuniga.me/blog/2019/05/10/constructing-trees-from-a-distance-matrix.html

[balvisio]

Great post Guilherme!

I was reading the Bioinformatics Algorithms book and I was thinking about one of the "Exercise Breaks" written in that book that reads: "The proposed algorithm computes LIMBLENGTH(j) in O(n^2) time (for an n x n distance matrix). Design an algorithm that computes LIMBLENGTH(j) in O(n) time"

As you mention in you post, the running time for limblength is O(n^2) which I thought too is the best that can be done. Wondering if you have any thoughts on the problem above? From my point of view O(n^2) comparisons are always needed since we need to compute all combinations of i and k.

[kunigami]

Thanks for the comment! I can't think of a way of doing it in O(n). We probably need to leverage the fact that matrix is additive but not sure how. I'll keep thinking about this some more :)

[balvisio]

Hello Guilherme,
I actually thought a little bit more and realized that it is not necessary to iterate over all pairs of i and k . It is possible to fix the value of i (to something different from j) and then iterate only through k and the algorithm will still find the minimum. Although I don't have a formal proof the intuition of why it works is the following:
When i is fixed to a particular leaf, the minimum is obtained when we pick the k that is the neighboring leaf of j since that is when the formula gives the limb length. The special case is when we pick i to be the neighboring node of j in which case all the iterations will give the minimum. The algo in python looks like this:

def limb_length(matrix, n, j):
    minDistance = float("inf")
                  
    i = 1 if j == 0 else j - 1                                                            

    for k in range(n):
        distance = (matrix[i][j] + matrix[j][k] - matrix[i][k])/2
        if k != i and k != j and distance < minDistance:
            minDistance = distance
    return int(minDistance)

As a small fix to the Runtime Complexity section you could change it to O(n) and the total runtime complexity to O(n^2)
Hope I was clear and it helps.

[kunigami]

Cool, I think this makes sense. Maybe from here:

The idea behind the theorem is that if we remove parent(j) from the unknown tree, it will divide it into at least 3 subtrees (one being leaf j on its own). This means that there exists leaves i and k that are in different subtrees

So by picking a random i, we're choosing one of the subtrees, we then need to find any k that exists in the other subtree.

I'll update the post. Thanks for the contribution!

[kunigami]

major edits: Added contribution, converted to Latex