Time complexity of proximity search in distance matrix

Question

I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same time ― loci are different stops on a 3D-winding DNA chain.

The best way to understand the 3D structure is by gathering what are basically distances between loci.

Now I have an $n\times n$ ($n$ = number of loci studied) matrix where the $(i,j)$ entry is the distance between locus $i$ and locus $j$. I also have a (somewhat miraculous) 3-dimensional of the same chromosome that maps each locus to a certain point in a 3D $(x,y,z)$ coordinate system.

My task is to find all of the loci within a certain radius of locus $L$. With the matrix, I would have to go to $L$ and traverse many nearby locus-distance chains, possibly for a long time, before being any bit certain that I had everything I wanted (i.e. brute force). With the spatial model, I would only have to conduct a simple search within that radius.

Here is my question. What is the complexity of finding nearby loci in the 3D model and the 2D matrix with respect to loci count and radius size (whichever you think is more complex)? (Compare the two complexities and give both.)

I am not very studied in CS, but here is what I guess:

$$C_\text{2D search best-case} = O(n^2)$$ $$C_\text{2D search worst-case} = O(2^n)$$

Best-case is what you'd expect, and worst-case would be going through every permutation of the distance.

$$ C_\text{3D search any case} = O(n) $$

This is just my rather fallible intuition.

Answer 1

There are a number of candidate techniques you could use.

The simplest is just naive search. Given a locus $L$, just scan over all $n$ loci and see how close each one is to $L$. You might measure "close" as Euclidean distance in the 3D coordinate system. Naive search takes $O(n)$ time, since you have to examine each locus and you do $O(1)$ work for each locus you examine. In your example, it appears that $n=40,000$, so this might be perfectly efficient, given your miraculous mapping to 3D space.

If you want to do this task many times, you can preprocess the data you have to make subsequent queries faster. For instance, one candidate is to use the techniques described in the following question: Find all neighbors at a certain distance, in 3 dimensions Basically, you have the 3D coordinates for each locus, so you store those 3D points in a k-d tree or octree. Now given the 3D coordinates of a locus $L$, you can quickly scan the tree to find all neighbors that are near $L$ in 3D space. The asymptotic running time of these algorithms is hard to analyze, but it might be something like $O(\lg n)$ times the number of loci that are close to $L$.

---

If you didn't have the miraculous map to 3D coordinates, there are alternative approaches that use just the $n \times n$ matrix of edit distances, but they will be slower. For instance, if you have precomputed the $n\times n$ matrix, then you can use naive search: given a locus $L$, scan over all $n$ loci and see how close each one is to $L$ using the edit distance matrix. This will take $O(n)$ time, since you have to consider all $n$ loci and it takes $O(1)$ work for each look-up in the matrix.

Unfortunately, precomputing the $n \times n$ matrix of edit distances will probably take $O(n^2)$ time, or maybe even slower. (Therefore, unless you're going to do many queries, it is not clear that precomputing the matrix of edit distances is worthwhile.)

Anyway, even if you have the precomputed distance matrix, I don't know of any way to use nearest-neighbor search techniques to get the running time below $O(n)$ time. This is a significant difference from the case where you have the miraculous 3D map: if you have the miraculous map to 3D coordinates, it looks like you can make search much faster.