Time complexity of proximity search in distance matrix
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.