如何在3D域中检测特定序列的结束位置(x，y，z)

Question

我有一个蛋白质3DCREO-EM扫描，它包含一个可以弯曲和扭曲的链-并且在3维空间中有2个链末端(就像连续的绳子)。我需要在给定的两个立方体空间中检测(x，y，z)位置，或者可能是两个结尾的乘数。扫描的立方体空间由扫描EM显微镜提供的每个体素中的密度(在0到1的范围内)表示，因此“现有物质”给出的值更接近1，而“不管”给出的密度值更接近0。我需要一种检测蛋白质“绳索”边缘的方法(可能的“绳索末端”定义是在某些纠结的方向上缺乏连续性。直觉上，我认为至少有两种方法: 1)图论中的某些方法(我不能准确地指定-如果你知道一种-请命名或描述它。2)来自分析代数的导数-但我同样不能指定具体的态度-所以请说出或解释其中一个。请详细说明建议方法的计算复杂度。我的项目是用Python实现的。请帮帮忙。提前谢谢。

Answer 1

一种方法是选择阈值密度，将低于该阈值的所有体素转换为0，将高于该阈值的所有体素转换为1，然后在所有1体素对中查找最短路径最长的1体素对。这两个体素应该接近最长的“绳索”的末端，而不管绳索的确切形状。

您可以定义一个图，其中每个1体素都有一个顶点，每个1体素与其6个(或可能14个)相邻体素之间有一条边。然后，您可以使用广度优先搜索在O(|V|)时间和空间中计算给定顶点u和其他顶点之间的最短路径的长度(这里我们不需要Dijkstra或Floyd-Warshall，因为每条边的权重都为1)。对每个可能的起始顶点u重复此操作，得到O(|V|^2)-time算法。在执行此操作时，请跟踪到目前为止最远的一对。

如果你的体素空间有w*h*d个单元，图中可能有w*h*d个顶点(如果每个体素都是一个1-体素)，所以在最坏的情况下这可能需要O(w^2*h^2*d^2)时间，这可能是相当多的时间。幸运的是，如果你能提供一个稍微不准确的答案，有很多方法可以加快速度：

• 仅计算从边界上的起始顶点开始的最短路径-即那些相邻顶点少于6(或14)的顶点。(我相信这不会牺牲最优的solution.)
• Alternatively，优先“骨架”图，通过重复删除所有这样的边界顶点不会断开图的连接。
• 选择起始顶点的好顺序是首先选择任何顶点，然后总是选择与上一个顶点距离最大的顶点(当然，这还没有尝试过)。这将使您在迭代3次后得到最长最短路径的一个非常好的近似值:距离起始顶点最远的顶点将靠近两个绳索末端之一，而距离该顶点最远的顶点将靠近另一端！

注意:如果绳子上由于弯曲而彼此靠近的远点之间没有全体素间隙，那么最短路径将“短路”通过这些错误的连接，并可能降低准确性。您也许可以通过增加阈值来改善这一点。OTOH，如果阈值太高，那么绳子可能会断开连接。我希望你选择最高的阈值，只产生1个连接的组件。

Answer 2

如果要在3D扫描中枚举每条连续路径(从而获得每条路径的末端)，可以对每个位置应用基本的深度优先搜索，例如：

//applied at some voxel
dfs(...)
    for each surrounding voxel 
        dfs(...)

或详细说明：

class coordinate{
    x
    y
    z
    visited
}

initialize pathList
initialize coords

add all coordinates which contain "matter" to coords

dfs(coordinate,path)
    coordinate.visited = TRUE
    isEnd = TRUE
    FOR each coordinate
        //check each of the 26 possible locations (total 26 conditionals)
        IF coordinate.get(x-1,y-1,z+1) IN coords AND 
           NOT coordinate.get(x-1,y-1,z+1).visited THEN
            isEnd = FALSE
            path += coordinate.get(x-1,y-1,z+1)
            dfs(coordinate.get(x-1,y-1,z+1),path)
        ...
        IF coordinate.get(x+1,y+1,z-1) IN coords AND 
           NOT coordinate.get(x+1,y+1,z-1).visited THEN 
            isEnd = FALSE
            path += coordinate.get(x+1,y+1,z-1) 
            dfs(coordinate.get(x+1,y+1,z-1),path)
    IF isEnd THEN
        add path to pathList
    remove coordinate from coords

WHILE coords isn't empty
    dfs(coords.get(0),"")

通用过程(dfs)在其他几十个站点上都有很好的文档记录，但如果你想测试它，这里有一些简单的java (我不太熟悉python)，它反映了上面的内容：

public class C {

    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<String> paths = new ArrayList<>();



    static class Coordinate {
        int x, y, z;
        boolean visited;
        Coordinate(int x,int y,int z){
            this.x = x;
            this.y = y;
            this.z = z;
            visited = false;
        }

        public String toString() {
            return "("+x+","+y+","+z+")";
        }
    }



    void dfs(Coordinate c,String path) {
        c.visited=true;
        path+=c.toString();
        boolean isEnd = true;
        //apply dfs to 26 possible neighbors
        for(int x = c.x-1; x <= c.x+1; x++) {
            for (int y = c.y-1; y <= c.y+1; y++) {
                for (int z = c.z+1; z >= c.z-1; z--) {
                    Coordinate coord = getCoordinate(x,y,z);
                    //if coord exists and it's not been visited
                    if(coord!=null && !coord.visited && !coord.equals(c)) {
                        isEnd = false;
                        dfs(coord, path);
                    }
                }
            }
        }
        if(isEnd) paths.add(path);

        coords.remove(c);
    }

    Coordinate getCoordinate(int x,int y,int z){
        for(Coordinate b: coords){
            if(x==b.x && y==b.y && z==b.z) return b;
        }
        return null;
    }


    void search(){
        //while there are points in 3d space extend a path from one
        while(!coords.isEmpty()){
            dfs(coords.get(0),"");
        }
    }




    public static void main(String[] args) {

        C coord = new C();

        //for each place where there exists matter
        //create a coordinate object and add to coords
        // for example:
        coord.coords.add(new Coordinate(0,0,0));
        coord.coords.add(new Coordinate(-1,1,1));
        coord.coords.add(new Coordinate(1,1,1));
        coord.coords.add(new Coordinate(-1,2,2));
        coord.coords.add(new Coordinate(-1,0,2));
        coord.coords.add(new Coordinate(1,2,2));
        coord.coords.add(new Coordinate(1,0,2));

        coord.search();
        //print out each path on separate line, 
        //the path endings can easily be obtained from this 
        for(String s:coord.paths) System.out.println(s);

    }
}